theory on Mersenne primes ?

[science_man_88]

Originally Posted by Batalov

Homework for you:
1. Re-read http://mersenne.org/various/math.php#lucas-lehmer
2. Pop-quiz: write the definition of Sn in Lucas-Lehmer iteration
3. For bonus points: determine the first n at which lift(Sn)^2-2 > 2^p-1 and modulo will apply.

1) done
2) if you only consider this page it's a modular residue mod the mersenne number of a sequence and can't be said to be used like Si is on the wikipedia page about it.

3) as Si is very roughly 2^(2i) we can say i<(p/2) but that's all I know, as to you saying it's grade three math I didn't learn algebra until grade nine.

[axn]

Originally Posted by science_man_88

3) as Si is very roughly 2^(2i) we can say i<(p/2) but that's all I know, as to you saying it's grade three math I didn't learn algebra until grade nine.

This is how 2^(2i) grows:

4
16
64
256
1024
4096
16384
65536
262144
1048576

Does that look even remotely like LL sequence?

[science_man_88]

Originally Posted by axn

This is how 2^(2i) grows:

4
16
64
256
1024
4096
16384
65536
262144
1048576

Does that look even remotely like LL sequence?

sorry I realize now it's roughly 2^(2^i)

[axn]

Originally Posted by science_man_88

sorry I realize now it's roughly 2^(2^i)

Right. So then, the answer to #3 is?

[science_man_88]

Originally Posted by axn

Right. So then, the answer to #3 is?

i= roughly log2(p)

[science_man_88]

I'm guessing if an easy way to use one result of the LL test to figure another it would already be in use, but is there a way to figure out using the multinomial theorem the multinomial connecting two values in the LL sequence separated by a certain difference if so y->a*x+b where y is in the LL sequence and x is the previous mersenne you're jumping from I'm thinking about the result formed when the multinomial is divided by the form z=wp+n; 2^p-1=x; 2^z-1 = 2^n*((x+1)^w)-1 ( yes I eliminated part of a term). I'm guessing it's too complicated or some other flaw has come up ?

[science_man_88]

4x^2+y^2-1 = 2kp
y= odd
4x^2+(2a+1)^2-1 = 2kp
4x^2+4a^2+4a = 2kp
2x^2+2a^2+2a = kp; k is even
x^2+a^2+a = bp
if( b=odd and x=odd , a = either,if(b==odd and x=even, a= impossible))
if(b= even and x=odd,a=impossible, if(b==even and x=even, a= either))

aka:

if (k mod 4=2 and x mod 4 = 1 or 3 , y mod 4 = 1 or 3)
if(k mod 4 =0 and x mod 4 = 2 or 0, y mod 4 = 1 or 3)


3x^2+y^2-1 = 2kp
1) x=even -> y=odd
2)x=odd -> y=even

1) 3x^2+(2a+1)^2-1= 2kp
3x^2+4a^2+4a = 2kp
6c^2+2a^2+2a = kp; k is even
3c^2+a^2+a = bp
if( b=odd and c=odd , a = either,if(b==odd and c=even, a= impossible));
( aka (2=x=k)mod 4; y^2=1 mod 4)
if(b= even and c=odd,a=impossible, if(b==even and c=even, a= either))
( aka (0=x=k)mod 4; y^2=1 mod 4;)

2) 3(2a+1)^2+4b^2-1 = 2kp
6a^2+6a+2b^2+1 =kp ; k=odd
6a^2+6a+2b^2+1=(2c+1)(2d+1)
6a^2+6a+2b^2+1 = 4cd+2c+2d+1
3a^2+3a+b^2 = 2cd+c+d
3a^2+3a+b^2 = (2d+1)c+d
if((b=c) mod 2, d=even;a=either)
if((b=d) mod 2, c=even;a=either)
if(a= (c or d) mod 2, (d or c) = b mod 2)

aka:

if((y=0 mod 4 && (k or p) mod 4 = 1) || ( y=2 mod 4 && (k or p)=3 mod 4) , (p or k)=1 mod 4 && x=1 or 3 mod 4)

etc.



3x^2-(y^2+1) = 2kp
1) x=even -> y=odd
2)x=odd -> y=even
1) 3x^2-((2a+1)^2+1)= 2kp
3x^2-4a^2-4a-2 = 2kp
6b^2-2a^2-2a-1 = kp; k is odd
6b^2-2a^2-2a-2+1 = (2c+1)(2d+1)
6b^2-2a^2-2a-2 = 4cd+2c+2d
3b^2-a^2-a-1 = 2cd+c+d
3b^2-a^2-a-1= (2d+1)c+d
if((b=c) mod 2, d=odd; a= either)
if((b=d) mod 2, c=odd; a= either)
if((a=(c or d)= even,(d or c)!=b mod 2)

2) 3(2a+1)^2-(4b^2+1) = 2kp
6a^2+6a-2b^2+1 =kp ; k is odd
3a^2+3a-b^2 = 2cd+c+d
(3a+3)a-b^2 = (2d+1)c+d
if( a=(c or d)=odd, ((d or c)!=b mod 2))
if(a=(c or d)=even, ((d or c)=b mod2))

I haven't completed working around on them but I'd like to see what people think and see if this can be turned into something fast to eliminate k.

[science_man_88]

I started off with the sieve of sundaram using the form of value that created a composite and said well if a mersenne is composite the next one has such and such a form and tried to equate form there I was hoping this would lead me to a property of some sort to look for the exponent or a form to solve into simpler terms that I could evaluate easy for a prime exponent. and yes I went through multiple steps but only show one and mix * and not leaving a space again.

2(4ij+2j+2i+1)+1
4ij+2j+2i+1 = 2kl+k+l
1 = (2l+1)*k+l-2*(2ij+j+i)
1=(3*k+1)*l+(2*k*l+k)*k-((4k-4)*i*j+(2k-2)*j+(2k-2)*i) /// assume 2k-2 is a variable m
1=(m+k+3)*l +(2*k^2*l+k^2)-(2*m*i*j+m*j+m*i)
1=(k+3)*l+(2*k^2*l+k^2) - m*(2*i*j+j+i -l)
m*(2*i*j+j+i -l)+1=(k+3)*l+(2*k^2*l+k^2)
2*m*i*j+m*j+m*i-m*l+1= k*l+3*l+2*k^2*l+k^2
-k^2 = k*l+3*l+2*k^2*l-2*m*i*j-m*j-m*i+m*l-1
-(2*l+1)*k^2= -(4k-4)*i*j-(2k-2)*j-(2k-2)*i+(3k+1)*l-1
(2l+1)*k^2 = 4*k*i*j-4*i*j +2*k*j-2*j +2*k*i-2*i-3kl-l+1
(2*k*l+k-4*i*j-2*j-2*i+3*l)*k+l = -4*i*j-2*j-2*i+1 /// assume 4*i*j+2*j+2*i-1 is a variable n
(2*k*l+k-4*i*j-2*j-2*i+3*l)*k+l = -n+2

[science_man_88]

I got to:

k^2-7 +3*k = r*l /// r*l must be odd regardless of what parity k is and therefore so is l;

before noting something in A002808

An integer is composite if and only if it is the sum of strictly positive integers in arithmetic progression with common difference 2: 4 = 1 + 3, 6 = 2 + 4, 8 = 3 + 5, 9 = 1 + 3 + 5, etc. - Jean-Christophe Hervé, Oct 02 2014

which when you show that 2*k*p+1 is just a subset of 2n+1 you can eliminate all k that are certain polite numbers( those that are a sum of (2*j*p+1) numbers) + j in theory because those k happen when you sum up 2*j*p+1 consecutive 2*k*p+1 values. I'm always so slow to catch on to simple things.

[science_man_88]

I know I've talked about the original non-reduced LL tests with x^2-2 and the difference a bit to people but I can't remember if I've talked about how the reduced form using 2*x^2-1 matches up to within a sum that I believe is mostly powers of two must equal to 1 mod 2^p-1 , p obviously being prime ( by convention only) for 2^p-1 to be prime. I guess I would have to figure out the formula for the sum to be of any use, anyone else interested ? edit: I realize now it's 2 mod 2^p-1 the reason this came to mind is outside the -1 this resembles the trail factoring example on the GIMPS math page. edit: 2 I keep thinking I would have to tack a 1 on the begging but I don't in the case of the one starting with 2 because it's already like it's done the first 1 in the binary.

[science_man_88]

I just thought I'd back this up with code ( prettied up after pasting):

Mcode(p,{flag=1},{modulus=[p<<1+1,1<<p-1][flag]},{zerocode=x^2},{onecode=[zerocode<<1,zerocode<<1-1][flag]},{bin=[p,1<<(p-2)-1][flag]},{result=[1,0][flag]},{x=[1,2][flag]})={
a=binary(bin);
for(y=1,#a,
     if(a[y],
        x=eval(onecode)%modulus,
        x=eval(zerocode)%modulus
       )
    );
if(x==result,
   if(flag==1,
      print("M"p" has a factor "modulus),
      if(flag==2,
         print("M"p" is prime")
        )
     )
  )
}

here's an addhelp:

addhelp(Mcode," if flag=1 proceed with checking if modulus is a divisor of Mp, if flag=2 proceeed with LL test of Mp")