Observation about Mersenne exponents

[paulunderwood]

? V=[2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457 ,32582657,37156667,42643801,43112609,57885161,74207281]

? f(p)=n=2^p-1;x=Mod(3,n);c=0;while(lift(gcd(x-1,n))==1,x=x^lift(-x);c=c+1;if(c>4,break));if(gcd(x-1,n)!=1,print(p" "lift(gcd(x-1,n))" "c))

? for(k=1,#V,p=V[k];f(p))
2 0 1
3 0 2
5 0 4
7 0 3
13 0 2
31 0 4
61 0 2
127 0 3
607 0 3
1279 0 4
3217 0 4
4423 0 4
23209 0 2
132049 0 4
^C

I really should extend this table with GWNUM.

The real questions are: Why do the resulting exponents have those values? And can the calculation be speeded up?

[science_man_88]

Originally Posted by paulunderwood

I really should extend this table with GWNUM.

The real questions are: Why do the resulting exponents have those values? And can the calculation be speeded up?

(21:19) gp > for(P=1,1000000,f(P))
2 0 1
3 0 2
5 0 4
7 0 3
13 0 2
25 0 3
31 0 4
61 0 2
127 0 3
607 0 3
1279 0 4

so it works to show 0 when it's not an exponent as well and no I haven't finished it yet and may not, but i do have to think about you're doing.

[paulunderwood]

Originally Posted by science_man_88

(21:19) gp > for(P=1,1000000,f(P))
2 0 1
3 0 2
5 0 4
7 0 3
13 0 2
25 0 3
31 0 4
61 0 2
127 0 3
607 0 3
1279 0 4

so it works to show 0 when it's not an exponent as well and no I haven't finished it yet and may not, but i do have to think about you're doing.

Hmm. 25 is not prime.

The right hand value is the number of iterations to get a 0. My quest is really to understand why such exponents occur, and, with that understanding, see if there is a way to speed up the program using mathematics, so it is faster than LL and therefore predict the next big Mersenne

[science_man_88]

Originally Posted by paulunderwood

Hmm. 25 is not prime.

The right hand value is the number of iterations to get a 0. My quest is really to understand why such exponents occur, and, with that understanding, see if there is a way to speed up the program using mathematics, so it is faster than LL and therefore predict the next big Mersenne

well are while loops that much faster than for loops for you because you have a loop counter and a limit like a for loop would so you could convert the while loop into a for loop if the for loop is faster and maybe that would provide the speedup maybe even parfor with the thing to test on one part of it and the x^lift(-x) on the other? just a thought.

[paulunderwood]

Originally Posted by science_man_88

well are while loops that much faster than for loops for you because you have a loop counter and a limit like a for loop would so you could convert the while loop into a for loop if the for loop is faster and maybe that would provide the speedup maybe even parfor with the thing to test on one part of it and the x^lift(-x) on the other? just a thought.

Yes, yes: That will speed up Pari/GP, but I could write it with GWNUM which would p*** all over Pari.

What I am really after is understanding why those exponents (and later ones presumably) occur

[science_man_88]

Originally Posted by paulunderwood

Yes, yes: That will speed up Pari/GP, but I could write it with GWNUM which would p*** all over Pari.

What I am really after is understanding why those exponents (and later ones presumably) occur

well we know the LL test shows us Sn =A*Mp maybe something irregular happens starting at these points and working forward the math with the mersennes is probably ordered quite well regardless so I would think would allow for too much regularity however maybe one of them works out the equation to 0 mod the larger Mp's that may help ?

[paulunderwood]

? f(p)=n=2^p-1;x=Mod(3,n);c=0;while(gcd(x-1,n)==1,c=c+1;if(c>4,break);x=(1/x)^lift(x-1));if(gcd(x-1,n)!=1,print(p" "lift(gcd(x-1,n))" "c))

This is quicker code than my original post, quicker than a 3-PRP test.

Is there a bug in Pari/GP here? I replaced x^lift(-x) with (1/x)^lift(x-1) which is wrong!

? version()
[2, 7, 2]

[science_man_88]

Originally Posted by paulunderwood

? f(p)=n=2^p-1;x=Mod(3,n);c=0;while(gcd(x-1,n)==1,c=c+1;if(c>4,break);x=(1/x)^lift(x-1));if(gcd(x-1,n)!=1,print(p" "lift(gcd(x-1,n))" "c))

This is quicker code than my original post, quicker than a 3-PRP test.

Is there a bug in Pari/GP here? I replaced x^lift(-x) with (1/x)^lift(x-1) which is wrong!

your code is faster than the one I could come up with that's good if c always equals at least 1 could we not try an until loop and only test the condition like, until(gcd(x-1,n)!=1,...) ? then you can get rid of the second if statement outside the loop. edit: never mind the forcing to c=1 makes it slower overall. okay I realized one mistake I made while making it still not caught up in the speed yet. edit2: I keep messing up these conditions I guess. ah our different version fo PARI may not help things I'm using

GP/PARI CALCULATOR Version 2.8.0 (development 18332-50485cf)

[paulunderwood]

I am sure I was taught from an early age that a^(-x) = (1/a)^x. However here is more on what Pari/GP gives:

? x=Mod(3, 170141183460469231731687303715884105727);x^lift(-x)
Mod(151236607520417094872610936636341427313, 170141183460469231731687303715884105727)
? x=Mod(3, 170141183460469231731687303715884105727);(1/x)^lift(x)
Mod(163839658147118519445328514689369879589, 170141183460469231731687303715884105727)
? x=Mod(3, 170141183460469231731687303715884105727);(1/x)^lift(x-1)
Mod(151236607520417094872610936636341427313, 170141183460469231731687303715884105727)

(The claim that my test is faster than a 3-PRP test occurs only for those mersennes that have a "2" in my original post:

? n=2^23209-1;Mod(3,n)^n;gettime()
1273
? f(23209);gettime()
23209 0 2
1268

Until the bug is fixed, I am reluctant to carry on with code development )

[science_man_88]

Originally Posted by paulunderwood

I am sure I was taught from an early age that a^(-x) = (1/a)^x. However here is more on what Pari/GP gives:

really I thought a^-x =1/(a^x) at least in non modular math it does. doh I see that they work out the same. also gettime needs to be before and after the code you do to test the time it's in the code otherwise it times the time between calls of gettime and may time how long it takes you to type/find code I think. the claim is still true in theory of course just pointing something out.

[CRGreathouse]

Originally Posted by paulunderwood

I am sure I was taught from an early age that a^(-x) = (1/a)^x. However here is more on what Pari/GP gives:

? x=Mod(3, 170141183460469231731687303715884105727);x^lift(-x)
Mod(151236607520417094872610936636341427313, 170141183460469231731687303715884105727)
? x=Mod(3, 170141183460469231731687303715884105727);(1/x)^lift(x)
Mod(163839658147118519445328514689369879589, 170141183460469231731687303715884105727)
? x=Mod(3, 170141183460469231731687303715884105727);(1/x)^lift(x-1)
Mod(151236607520417094872610936636341427313, 170141183460469231731687303715884105727)

(The claim that my test is faster than a 3-PRP test occurs only for those mersennes that have a "2" in my original post:

? n=2^23209-1;Mod(3,n)^n;gettime()
1273
? f(23209);gettime()
23209 0 2
1268

Until the bug is fixed, I am reluctant to carry on with code development )

Are you sure this is a bug?

x=Mod(3, 170141183460469231731687303715884105727);
(1/x)^lift(x)==x^-lift(x)
(1/x)^lift(-x)==x^-lift(-x)

I don't see why a^b should be equal to x^(p-b).

Edit: The exponent should really be taken mod phi(P) not mod P, and in this case phi(P) = P-1 since P = 170141183460469231731687303715884105727 is prime. So I don't think there is a bug.