Penultimate Lucas-Lehmer step - Page 3

ATH · 2012-09-29, 23:57

I was looking at the penultimate LL step for the other "universel" seeds S0=10 and S0=2/3 and I found out for S0=4 and S0=10 there are an infinite sequence of universel seeds:
http://www.mersenneforum.org/showthread.php?t=138

I'll call them A and B:
A(1)=4, A(2)=52, A(N)=14*A(N-1)-A(N-2)
B(1)=10, B(2)=970, B(N)=98*B(N-1)-B(N-2)

but it looks like seeds within the same sequence gives the same penultimate LL step although with alternating signs:

Code:

A(1)=4, A(2)=52, A(N)=14*A(N-1)-A(N-2)
 
A(1)=4,A(2)=52,A(3)=724,A(4)=10084,A(5)=140452,A(6)=1956244,A(7)=27246964,
A(8)=379501252,A(9)=5285770564,A(10)=73621286644,A(11)=1025412242452
 
          A(1)  A(2)  A(3)  A(4)  A(5)  A(6)  A(7)  A(8)  A(9)  A(10) A(11)
M2:  p=3	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M3:  p=5	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M4:  p=7	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M5:  p=13	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M6:  p=17	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M7:  p=19	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M8:  p=31	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M9:  p=61	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M10: p=89	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M11: p=107	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M12: p=127	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M13: p=521	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M14: p=607	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M15: p=1279	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M16: p=2203	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M17: p=2281	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M18: p=3217	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M19: p=4253	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M20: p=4423	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M21: p=9689	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M22: p=9941	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M23: p=11213	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M24: p=19937	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M25: p=21701	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M26: p=23209	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M27: p=44497	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M28: p=86243	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M29: p=110503	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M30: p=132049	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
 
 
B(1)=10, B(2)=970, B(N)=98*B(N-1)-B(N-2)
 
B(1)=10,B(2)=970,B(3)=95050,B(4)=9313930,B(5)=912670090,B(6)=89432354890,B(7)=8763458109130,
B(8)=858729462339850,B(9)=84146723851196170,B(10)=8245520207954884810,B(11)=807976833655727515210
 
		B(1)  B(2)  B(3)  B(4)  B(5)  B(6)  B(7)  B(8)  B(9) B(10) B(11)
M2:  p=3	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M3:  p=5	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M4:  p=7	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M5:  p=13	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M6:  p=17	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M7:  p=19	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M8:  p=31	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M9:  p=61	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M10: p=89	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M11: p=107	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M12: p=127	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M13: p=521	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M14: p=607	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M15: p=1279	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M16: p=2203	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M17: p=2281	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M18: p=3217	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M19: p=4253	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M20: p=4423	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M21: p=9689	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M22: p=9941	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M23: p=11213	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M24: p=19937	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M25: p=21701	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M26: p=23209	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M27: p=44497	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M28: p=86243	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+
M29: p=110503	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+ 	- 	-
M30: p=132049	- 	+ 	+ 	- 	- 	+ 	+ 	- 	- 	+ 	+

So it's only necessary to check the 3 universel seeds 4, 10 and 2/3:

Code:

		S[0]=4	S[0]=10	S[0]=2/3
M2:  p=3	+	-	-
M3:  p=5	+	-	-
M4:  p=7	-	-	-
M5:  p=13	+	+	+
M6:  p=17	-	+	+
M7:  p=19	-	+	-
M8:  p=31	+	+	-
M9:  p=61	+	+	+
M10: p=89	-	+	+
M11: p=107	-	+	-
M12: p=127	+	+	-
M13: p=521	-	+	+
M14: p=607	-	-	-
M15: p=1279	-	-	-
M16: p=2203	+	-	-
M17: p=2281	-	+	+
M18: p=3217	-	+	+
M19: p=4253	+	+	+
M20: p=4423	-	-	-
M21: p=9689	-	+	+
M22: p=9941	+	+	+
M23: p=11213	-	-	+
M24: p=19937	+	-	+
M25: p=21701	-	-	+
M26: p=23209	+	-	+
M27: p=44497	-	+	+
M28: p=86243	+	-	-
M29: p=110503	+	+	-
M30: p=132049	+	-	+
M31: p=216091	-	+	-
M32: p=756839	+	+	-
M33: p=859433	-	+	+
M34: p=1257787	-    
M35: p=1398269	+    
M36: p=2976221	+    
M37: p=3021377	+    
M38: p=6972593	+    
M39: p=13466917	+    
M40: p=20996011	+    
M41: p=24036583	-    
M42: p=25964951	+    
M43: p=30402457	-    
M44: p=32582657	-    
M45: p=37156667	+    
M46: p=42643801	-    
M47: p=43112609	+    
M48: p=57885161	-
 
		24+
		23-

If I ever get prime95 or mprime compiled so I can change S0 I will extend the list for S0=10 and S0=2/3.

Batalov · 2013-02-05, 04:53

24+ : 23- now.

(not much of a useful hint to find the exponent, so there)

ATH · 2013-02-05, 14:57

Quote:

Originally Posted by Batalov

24+ : 23- now.

M57885161 interim We4 residue D3AD196D848B393E at iteration 57885157
M57885161 interim We4 residue 567B00CF01C29872 at iteration 57885158
M57885161 interim We4 residue 5A6C21ACD6B4A120 at iteration 57885159
M57885161 interim We4 residue FFFFFFFFFFFFFFFF at iteration 57885160
M57885161 interim We4 residue 0000000000000000 at iteration 57885161
M57885161 is prime! We4: 58BF09CF,00000000

penultimate.txt

UPDATED LINK:
http://www.hoegge.dk/mersenne/penultimateresults.txt

Batalov · 2013-02-05, 19:48

Aw, shoot, the forum's engine cleverly replaces all TABs by spaces (even inside [code] blocks). I'll fix the table now (a couple posts above).

Batalov · 2015-07-08, 21:53

Andreas,

As implemented by George, one can replace the S0 value by setting InitialLLValue=10 in prime.txt.
I've got a hack in place for you to use the S0 = 2/3 value. (Use InitialLLValue=23 in prime.txt. Of course 23 is not 2/3, but 23 is not a vaild starting S0 value anyway); maybe George can clean up this quick hack and recompile?

The patch is this:

Code:

*** ../p95v287src/commonb.c     Thu May 14 14:53:12 2015
--- commonb.c   Wed Jul  8 14:36:48 2015
***************
*** 5421,5428 ****
  /* different FFT data - thus greatly reducing the chance that a CPU or program error corrupts the results. */

        if (counter == 2) {
!               if (IniGetInt (INI_FILE, "InitialLLValue", 4) != 4) {
!                       dbltogw (&lldata.gwdata, (double) IniGetInt (INI_FILE, "InitialLLValue", 4), lldata.lldata);
                        lldata.units_bit = 0;
                } else {
                        unsigned long i, word, bit_in_word;
--- 5421,5440 ----
  /* different FFT data - thus greatly reducing the chance that a CPU or program error corrupts the results. */

        if (counter == 2) {
!               unsigned long S0;
!               if ((S0 = IniGetInt (INI_FILE, "InitialLLValue", 4)) != 4) {
!                       if(S0 == 23) {
!                         giant tmp;
!                         tmp = allocgiant ((p >> 5) + 5);
!                         if (tmp == NULL) return (OutOfMemory (thread_num));
!                         ultog (2, tmp);
!                         power (tmp, p);
!                         iaddg (1, tmp);
!                         dbldivg (3, tmp);
!                         gianttogw (&lldata.gwdata, tmp, lldata.lldata);
!                       } else {
!                         dbltogw (&lldata.gwdata, (double) S0, lldata.lldata);
!                       }
                        lldata.units_bit = 0;
                } else {
                        unsigned long i, word, bit_in_word;

Prime95 · 2015-07-08, 22:16

Quote:

Originally Posted by Batalov

As implemented by George, one can replace the S0 value by setting InitialLLValue=10 in prime.txt.
I've got a hack in place for you to use the S0 = 2/3 value. (Use InitialLLValue=23 in prime.txt. Of course 23 is not 2/3, but 23 is not a vaild starting S0 value anyway); maybe George can clean up this quick hack and recompile?

I've added your code for the next release.

Batalov · 2016-01-15, 18:37

Quote:

Originally Posted by Batalov

24+ : 23- now.

(not much of a useful hint to find the exponent, so there)

24+ : 24- now. It is, again, a draw.

But these are [B]not[/B] the heads and tails that David Eddy meant.

ATH · 2016-01-25, 19:49

M49 penultimate step came in as a + for the 2 other universal seeds S0=10 and S0=2/3. I finished those 2 lists like 6 months ago up to M48, but never posted them.

Thanks to George for implementing the InitialLLvalue options and to Serge for the patched version to run S0=2/3.

penultimatellstep.txt

Result files with the last 5 iteration of each prime:
penultimateresultsS0=4.txt
penultimateresultsS0=10.txt
penultimateresultsS0=2-3.txt

Code:

		     S[0]=4  S[0]=10 S[0]=2/3
M2:  p=3		+	-	-
M3:  p=5		+	-	-
M4:  p=7		-	-	-
M5:  p=13		+	+	+
M6:  p=17		-	+	+
M7:  p=19		-	+	-
M8:  p=31		+	+	-
M9:  p=61		+	+	+
M10: p=89		-	+	+
M11: p=107		-	+	-
M12: p=127		+	+	-
M13: p=521		-	+	+
M14: p=607		-	-	-
M15: p=1279		-	-	-
M16: p=2203		+	-	-
M17: p=2281		-	+	+
M18: p=3217		-	+	+
M19: p=4253		+	+	+
M20: p=4423		-	-	-
M21: p=9689		-	+	+
M22: p=9941		+	+	+
M23: p=11213		-	-	+
M24: p=19937		+	-	+
M25: p=21701		-	-	+
M26: p=23209		+	-	+
M27: p=44497		-	+	+
M28: p=86243		+	-	-
M29: p=110503		+	+	-
M30: p=132049		+	-	+
M31: p=216091		-	+	-
M32: p=756839		+	+	-
M33: p=859433		-	+	+
M34: p=1257787		-	+	-
M35: p=1398269		+	+	+
M36: p=2976221		+	+	+
M37: p=3021377		+	-	+	
M38: p=6972593		+	-	+
M39: p=13466917		+	+	+	
M40: p=20996011		+	-	-	
M41: p=24036583		-	-	-
M42: p=25964951		+	+	-
M43: p=30402457		-	+	+
M44: p=32582657		-	+	+
M45: p=37156667		+	-	-
M46: p=42643801		-	+	+
M47: p=43112609		+	-	+
M48: p=57885161		-	+	+
M49: p=74207281		-	+	+

		       24+ 	29+	28+
		       24-	19-	20-
		-----------------------------
		       48	48	48

Batalov · 2017-12-31, 03:07

So, for future reference in this thread (due to Jansen and Gebre-Egziabher), for p > 5:

$\eps (10,\ p) = \eps (4,\ p) \ \times \ (-1) ^ {{(p+1)(p+3)} \over 8}$

$\eps ({2 \over 3},\ p) = (-1) ^ {p-1 \over 2}$

Batalov · 2017-12-31, 16:29

Some people asked me to put a simple English-translated version of the above statement. Here it is:

As soon as we know p for a Mersenne prime M_p, we already know what the sign of the penultimate iteration will be if we start with the universal seed s₀ = (2^p+1) / 3 (also known as 2/3).
It will be (-1)^(p-1)/2 for p≠5 (and -1 for p==5).

And then, as we will learn the sign of the penultimate L-L iteration with the conventional seed s₀ = 4 (there is no other way as of now other than to run L-L),
then we will know the sign of the penultimate iteration with the conventional seed s₀ = 10. (which is shown above)

GP2 · 2017-12-31, 19:36

Quote:

Originally Posted by Batalov

It will be (-1)^(p-1)/2 for p≠5 (and -1 for p==5).

The original formulation in English is maybe clearer.

All primes p other than 2 are odd. That is, when divided by 4 they have remainder of either 1 or 3. This is expressed as p ≡ 1 (mod 4) or p ≡ 3 (mod 4).

If p ≡ 1 then the sign is +, and if p ≡ 3 then the sign is −. Unless p = 5.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
lucas-lehmer theorem	Robot2357	Math	6	2013-06-15 03:10
Can zero be an "intermediate step" value in Lucas-Lehmer?	That Don Guy	Math	10	2012-02-03 18:02
lucas lehmer outstretch	science_man_88	Miscellaneous Math	7	2010-07-14 12:35
Lucas-Lehmer Test	storm5510	Math	22	2009-09-24 22:32
Lucas-Lehmer	Dougal	Information & Answers	9	2009-02-06 10:25

2013-02-05, 04:53	#24
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	24+ : 23- now. (not much of a useful hint to find the exponent, so there)

2013-02-05, 19:48	#26
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	Aw, shoot, the forum's engine cleverly replaces all TABs by spaces (even inside [code] blocks). I'll fix the table now (a couple posts above).

2017-12-31, 03:07	#31
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9477₁₀ Posts	So, for future reference in this thread (due to Jansen and Gebre-Egziabher), for p > 5: $\eps (10,\ p) = \eps (4,\ p) \ \times \ (-1) ^ {{(p+1)(p+3)} \over 8}$ $\eps ({2 \over 3},\ p) = (-1) ^ {p-1 \over 2}$

2017-12-31, 16:29	#32
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22405₈ Posts	Some people asked me to put a simple English-translated version of the above statement. Here it is: As soon as we know p for a Mersenne prime M_p, we already know what the sign of the penultimate iteration will be if we start with the universal seed s₀ = (2^p+1) / 3 (also known as 2/3). It will be (-1)^(p-1)/2 for p≠5 (and -1 for p==5). And then, as we will learn the sign of the penultimate L-L iteration with the conventional seed s₀ = 4 (there is no other way as of now other than to run L-L), then we will know the sign of the penultimate iteration with the conventional seed s₀ = 10. (which is shown above)