mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2006-05-17, 22:00   #1
K Ramsey
 
May 2006

716 Posts
Default Is this of any merit?

I think the following test for Mersenne Primes works but I dont have the ability to check it. My Excel macro works but it is limited to small numbers.
I only tested it for 2<p<27 but it gives correct results in that range.

Conjecture If and only if M(p) = 2^(p) - 1 is prime then for any non trivial integer sequence having the formula S_n = 6*S_(n-1) - S_(n-2), the following relation always holds S_n = S_(2^(p-1) + n - 1) mod M(p) regardless of the index value n.

I am just an amature and have little background in math. I know that there are other tests out there that may be more useful, However I would appreciate it if any one would check it out for higher values of p and give any insight as to it merit. One advantage that I see is that to check the primeness of M(p) no number bigger than 6M(p) need be evaluated.

Note that Mersenne Primes are related to perfect numbers which are in fact triangular numbers and that the integer sequence in question has terms that when squared are always a separated from a triangular number by a constant value k, i.e. (S_n)^2 - k = m(m+1)/2 for some integer m regard less of the index n. For S_0 = 0 and S_1 = 1, k = 0 since (S_n)^2 is in fact always a square triangular number.
K Ramsey is offline   Reply With Quote
Old 2006-05-18, 01:25   #2
K Ramsey
 
May 2006

7 Posts
Default

Quote:
Originally Posted by K Ramsey
Conjecture If and only if M(p) = 2^(p) - 1 is prime then for any non trivial integer sequence having the formula S_n = 6*S_(n-1) - S_(n-2), the following relation always holds S_n = S_(2^(p-1) + n - 1) mod M(p) regardless of the index value n.
I mean by non trivial, for example that S_n is always prime to S_(n+1), and particularly that at most only one of S_n and S_(n+1) are divisible by the Mersenne prime M(p)

Last fiddled with by K Ramsey on 2006-05-18 at 01:26
K Ramsey is offline   Reply With Quote
Old 2006-05-18, 13:33   #3
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2·193 Posts
Default

Talking rubbish, let me fix it..

Last fiddled with by Greenbank on 2006-05-18 at 13:48
Greenbank is offline   Reply With Quote
Old 2006-05-18, 13:42   #4
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2·193 Posts
Default

The problem with using this for primality tests is that it requires calculating a very large number of terms. Usually M(p)/2.

Compare this with the Lucas-Lehmer primality test

S_0 = 4
S_n = (S_(n-1))^2 - 2 (mod M(p))

M(p) is prime iff S_(p-2) = 0 (mod M(p))

where only p-1 terms in the series need to be calculated, rather than M(p)/2

Also, there is no need to store any intermediate terms to check whether any condition still holds.
Greenbank is offline   Reply With Quote
Old 2006-05-18, 14:01   #5
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2·193 Posts
Default

S_n = S_(2^(p-1) + n - 1) mod M

If M(p) is a Mersenne Prime then the Multiplicative Order of 2,M(p) is M(p-1).

Then:-

2^x = 2^(x+M(p-1)) mod M(p)

Note how this affects your relation.

By checking individual terms as possible divisors your method is similar to that of Pollard's Rho method.
Greenbank is offline   Reply With Quote
Old 2006-05-19, 02:23   #6
K Ramsey
 
May 2006

7 Posts
Default

Quote:
Originally Posted by Greenbank
The problem with using this for primality tests is that it requires calculating a very large number of terms. Usually M(p)/2.

Compare this with the Lucas-Lehmer primality test

S_0 = 4
S_n = (S_(n-1))^2 - 2 (mod M(p))

M(p) is prime iff S_(p-2) = 0 (mod M(p))

where only p-1 terms in the series need to be calculated, rather than M(p)/2

Also, there is no need to store any intermediate terms to check whether any condition still holds.
Thanks
After considering your comment, I realized that it is not necessary to store more than one term and that my test can be refined so that there are only p-1 terms that need to be calculated.
Here is my test

S_0 = 1
C = p
Do
S_0 = (4*S_0)*(8*S_0 + 1) Mod M(p)
C = C - 1
Loop until C = 1
If S_0 = 1 Then
Print "M(" & p & ") is prime"
Else
Print "M(" & p & ") is not prime"
End If.

Although this test involves more steps, it basically involves almost the same complexity as the Lucus-Lehmer Test since the additional steps are register shifts and the addition of 1
It is based upon the fact that 1 is the 2nd square triangular number and that The new S_0's follow the sequence ST(2),ST(3),ST(5),ST(9),ST(17).... i.e. ST(2^n+1) in the sequence of square triangular numbers (modulus M(p) of course). I checked it for p = 3 to 28. It doesn't work for p = 2 since 3 is a factor of 6.

Any comments?
K Ramsey is offline   Reply With Quote
Old 2006-05-20, 11:30   #7
K Ramsey
 
May 2006

7 Posts
Default

Quote:
Originally Posted by K Ramsey
Thanks
After considering your comment, I realized that it is not necessary to store more than one term and that my test can be refined so that there are only p-1 terms that need to be calculated.
Here is my test

S_0 = 1
C = p
Do
S_0 = (4*S_0)*(8*S_0 + 1) Mod M(p)
C = C - 1
Loop until C = 1
If S_0 = 1 Then
Print "M(" & p & ") is prime"
Else
Print "M(" & p & ") is not prime"
End If.

Although this test involves more steps, it basically involves almost the same complexity as the Lucus-Lehmer Test since the additional steps are register shifts and the addition of 1
It is based upon the fact that 1 is the 2nd square triangular number and that The new S_0's follow the sequence ST(2),ST(3),ST(5),ST(9),ST(17).... i.e. ST(2^n+1) in the sequence of square triangular numbers (modulus M(p) of course). I checked it for p = 3 to 28. It doesn't work for p = 2 since 3 is a factor of 6.

Any comments?
I have downloaded Pari but am new to it. Anyone care to write a Pari version of my test so I can work with larger numbers? I am using windows XP

PS the sequence S_0 = 0, S__1= 1 S_n = 6S_(n-1)-S(n-2) gives S_n where S_n = a(n)*b(n),
a_0=a_1 = 1, a_n = 2*a_(n-1) + a(n-2);
b_0 = 0, b_1 = 1, b_n = 2*b_(n-1)+ b_(n-2)

I did a quick check and the factors m(p) appear to divide the a_(2^(p-1)) terms and not the b_(2^(p-1)) terms. All three series appear in Sloans online encyclopedia of integer sequences and have formulas for directy computing the nth term. I only know a algorithm for computing S_(2^(p-1)) in p-1 iterations at the present time. There should be a similar algorithm for a_(2^(p-1)) since it involves raising the a_n generator to the
2^(p-1) power. Got to leave for a couple of days now.

Last fiddled with by K Ramsey on 2006-05-20 at 11:33
K Ramsey is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 09:34.


Sat Nov 27 09:34:48 UTC 2021 up 127 days, 4:03, 0 users, load averages: 1.46, 1.25, 1.15

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.