mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2020-08-03, 17:30   #12
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2×7×11 Posts
Default

It is perhaps also interesting to note the lengths of the "pre-periods", or offsets. That is the number of terms in the LL sequence preceding the first occurrence of the period. With Batalov's data as input, that is easy (PARI/GP):
Code:
findOffset(p,t)=s=Mod(4,2^p-1);S=s;for(i=1,t,S=S^2-2);i=0;while(s!=S,s=s^2-2;S=S^2-2;i++);i
Pass the Mersenne exponent as p, and the period length (from Batalov's post; of course Batalov's technique for finding the period length is also easy to write in PARI/GP) as t. In the function, the S sequence is always t positions ahead of the s sequence, so we just check to see how long it takes until they agree.

Result:
Code:
findOffset(11,60)
1

findOffset(23,32340)
1

findOffset(29,252)
1

findOffset(37,516924)
5

findOffset(41,822960)
1

findOffset(43,420)
3

findOffset(47,20338900)
4

findOffset(53,1309620)
2
The last one, findOffset(59,345603421440), would take a long time with PARI/GP with this approach.

Not sure if the above values have any interesting interpretation. We see that for the cases I was able to resolve, the constant 120000 in Batalov's C program was on the safe side. Of course, Viliam Furik's approach (searching for "14") works exactly in the cases where findOffset gives 1.

/JeppeSN
JeppeSN is offline   Reply With Quote
Old 2020-08-03, 18:13   #13
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2·7·11 Posts
Default

Quote:
Originally Posted by Batalov View Post
Periods may (?) be different if we use the other popular seed values S0 = 10, or S0 = 2/3 (mod Mp).
That is true: This PARI/GP function imitates your program, with an optional seed argument:
Code:
findPeriod(p,seed=4)=s=Mod(seed,2^p-1);for(i=1,120000,s=s^2-2);S=s;i=0;until(s==S,S=S^2-2;i++);i
Results:
Code:
findPeriod(11)
60

findPeriod(11,10)
10

findPeriod(11,2/3)
5
So they do differ. The one for 2/3 is not even a multiple of 11 - 1 = 10. You may think PARI handles 2/3 wrong, but it does not: Evaluating findPeriod(11,683) also gives 5.

Explicitly, the LL sequence for 2^11 - 1, starting from seed 2/3 == 683, is:

683 -> 1818 -> 1264 -> 1034 -> 620 -> 1609 -> 1471 -> 160 -> 1034 -> etc.

Similarly, for 2^29 - 1, and seed 2/3, the period length is 154, which is 14 mod 28.

/JeppeSN
JeppeSN is offline   Reply With Quote
Old 2020-08-03, 18:15   #14
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

216448 Posts
w00t

You have a solid footing to retrace Tony's DiGraphs adventure, now! It is a bit of a déjà vu, but a good warm up to visit his old threads.
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring composite Mersenne numbers using Pollard Rho jshort Factoring 9 2019-04-09 16:34
question: decidability for quadratic residues modulo a composite LaurV Math 18 2017-09-16 14:47
2 holes in bizarre theorem about composite Mersenne Numbers wildrabbitt Math 120 2016-09-29 21:52
Use Pepin's Tests for proving primality of Mersenne numbers ? T.Rex Math 12 2016-04-03 22:27
Factoring highly composite Mersenne numbers philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 09:03.

Sun Sep 20 09:03:33 UTC 2020 up 10 days, 6:14, 0 users, load averages: 1.41, 1.29, 1.37

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.