mersenneforum.org Is this of any merit?
 Register FAQ Search Today's Posts Mark Forums Read

 2006-05-17, 22:00 #1 K Ramsey   May 2006 710 Posts 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
2006-05-18, 01:25   #2
K Ramsey

May 2006

7 Posts

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

 2006-05-18, 13:33 #3 Greenbank     Jul 2005 18216 Posts Talking rubbish, let me fix it.. Last fiddled with by Greenbank on 2006-05-18 at 13:48
 2006-05-18, 13:42 #4 Greenbank     Jul 2005 38610 Posts 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.
 2006-05-18, 14:01 #5 Greenbank     Jul 2005 18216 Posts 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.
2006-05-19, 02:23   #6
K Ramsey

May 2006

7 Posts

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.

2006-05-20, 11:30   #7
K Ramsey

May 2006

7 Posts

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

All times are UTC. The time now is 12:45.

Sat May 21 12:45:48 UTC 2022 up 37 days, 10:47, 0 users, load averages: 1.32, 1.48, 1.46