mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2016-01-23, 01:02   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

10000011101012 Posts
Default 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
paulunderwood is offline   Reply With Quote
Old 2016-01-23, 01:21   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by paulunderwood View Post

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
science_man_88 is offline   Reply With Quote
Old 2016-01-23, 01:27   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

11·383 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
paulunderwood is offline   Reply With Quote
Old 2016-01-23, 01:34   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
science_man_88 is offline   Reply With Quote
Old 2016-01-23, 01:40   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

11·383 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
paulunderwood is offline   Reply With Quote
Old 2016-01-23, 01:45   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-01-23, 14:46   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

11·383 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2016-01-23, 15:03   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-01-23, 17:42   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

11×383 Posts
Default

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 )
paulunderwood is offline   Reply With Quote
Old 2016-01-23, 17:46   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-01-23, 18:02   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne(prime exponents) factorization science_man_88 Miscellaneous Math 3 2010-10-13 14:32
Sums of Mersenne Exponents davar55 Puzzles 8 2009-08-22 19:14
Mersenne Observation.... petrw1 Math 5 2008-11-04 20:27
Mersenne exponents verified baha2007 Information & Answers 2 2007-12-08 20:12
Mersenne exponents Xordan Math 4 2007-06-07 16:05

All times are UTC. The time now is 08:16.


Wed Jul 6 08:16:16 UTC 2022 up 83 days, 6:17, 0 users, load averages: 1.19, 1.12, 1.14

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔