mersenneforum.org > Math Repeating residues in LL tests of composite Mersenne numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2020-08-03, 17:30 #12 JeppeSN     "Jeppe" Jan 2016 Denmark 2×71 Posts 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
2020-08-03, 18:13   #13
JeppeSN

"Jeppe"
Jan 2016
Denmark

8E16 Posts

Quote:
 Originally Posted by Batalov 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

 2020-08-03, 18:15 #14 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100011011110002 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post jshort Factoring 9 2019-04-09 16:34 LaurV Math 18 2017-09-16 14:47 wildrabbitt Math 120 2016-09-29 21:52 T.Rex Math 12 2016-04-03 22:27 philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 05:27.

Mon Aug 10 05:27:13 UTC 2020 up 24 days, 1:13, 2 users, load averages: 1.41, 1.37, 1.39