20060517, 22:00  #1 
May 2006
7_{16} 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<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_(n1)  S_(n2), the following relation always holds S_n = S_(2^(p1) + 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. 
20060518, 01:25  #2  
May 2006
7 Posts 
Quote:
Last fiddled with by K Ramsey on 20060518 at 01:26 

20060518, 13:33  #3 
Jul 2005
2·193 Posts 
Talking rubbish, let me fix it..
Last fiddled with by Greenbank on 20060518 at 13:48 
20060518, 13:42  #4 
Jul 2005
2·193 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 LucasLehmer primality test S_0 = 4 S_n = (S_(n1))^2  2 (mod M(p)) M(p) is prime iff S_(p2) = 0 (mod M(p)) where only p1 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. 
20060518, 14:01  #5 
Jul 2005
2·193 Posts 
S_n = S_(2^(p1) + n  1) mod M
If M(p) is a Mersenne Prime then the Multiplicative Order of 2,M(p) is M(p1). Then: 2^x = 2^(x+M(p1)) 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. 
20060519, 02:23  #6  
May 2006
7 Posts 
Quote:
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 p1 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 LucusLehmer 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? 

20060520, 11:30  #7  
May 2006
7 Posts 
Quote:
PS the sequence S_0 = 0, S__1= 1 S_n = 6S_(n1)S(n2) gives S_n where S_n = a(n)*b(n), a_0=a_1 = 1, a_n = 2*a_(n1) + a(n2); b_0 = 0, b_1 = 1, b_n = 2*b_(n1)+ b_(n2) I did a quick check and the factors m(p) appear to divide the a_(2^(p1)) terms and not the b_(2^(p1)) 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^(p1)) in p1 iterations at the present time. There should be a similar algorithm for a_(2^(p1)) since it involves raising the a_n generator to the 2^(p1) power. Got to leave for a couple of days now. Last fiddled with by K Ramsey on 20060520 at 11:33 
