Register FAQ Search Today's Posts Mark Forums Read

 2016-01-23, 01:02 #1 paulunderwood     Sep 2002 Database er0rr 106028 Posts Observation about Mersenne exponents Code: ? 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] Code: ? 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)) Code: ? 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? Last fiddled with by paulunderwood on 2016-01-23 at 01:10
2016-01-23, 01:21   #2
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 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?
Code:
(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.

Last fiddled with by science_man_88 on 2016-01-23 at 01:23

2016-01-23, 01:27   #3
paulunderwood

Sep 2002
Database er0rr

118216 Posts

Quote:
 Originally Posted by science_man_88 Code: (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

2016-01-23, 01:34   #4
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

203428 Posts

Quote:
 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.

2016-01-23, 01:40   #5
paulunderwood

Sep 2002
Database er0rr

2×33×83 Posts

Quote:
 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

2016-01-23, 01:45   #6
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 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 ?

Last fiddled with by science_man_88 on 2016-01-23 at 01:51

 2016-01-23, 14:46 #7 paulunderwood     Sep 2002 Database er0rr 2·33·83 Posts Code: ? 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! Code: ? version() [2, 7, 2] Last fiddled with by paulunderwood on 2016-01-23 at 15:12
2016-01-23, 15:03   #8
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts

Quote:
 Originally Posted by paulunderwood Code: ? 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
Quote:
 GP/PARI CALCULATOR Version 2.8.0 (development 18332-50485cf)

Last fiddled with by science_man_88 on 2016-01-23 at 15:24

 2016-01-23, 17:42 #9 paulunderwood     Sep 2002 Database er0rr 118216 Posts 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: Code: ? 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: Code: ? 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 )
2016-01-23, 17:46   #10
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 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.

Last fiddled with by science_man_88 on 2016-01-23 at 17:52

2016-01-23, 18:02   #11
CRGreathouse

Aug 2006

598710 Posts

Quote:
 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: Code: ? 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: Code: ? 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?
Code:
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.

Last fiddled with by CRGreathouse on 2016-01-23 at 18:30

 Similar Threads Thread Thread Starter Forum Replies Last Post science_man_88 Miscellaneous Math 3 2010-10-13 14:32 davar55 Puzzles 8 2009-08-22 19:14 petrw1 Math 5 2008-11-04 20:27 baha2007 Information & Answers 2 2007-12-08 20:12 Xordan Math 4 2007-06-07 16:05

All times are UTC. The time now is 22:13.

Fri Jan 27 22:13:41 UTC 2023 up 162 days, 19:42, 0 users, load averages: 0.74, 1.06, 1.12