mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2017-06-11, 09:40   #1
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100101011000102 Posts
Cool Lucas and Fibonacci primes

There were 64 known prime Lucas numbers (including PRPs) and many of them are packed in clusters. Unexpectedly, there is a huge gap after the last previously known prime. (And similarly in Fibonacci primes, - observe the gap between 1968721 and 2904353, not quite as large but still 1.5x )

As agreed with R. and H.Lifschitz, I started the search at n>1800000, and found one more (though they reported that no primes were found in the substantial range between - where they searched since 2009). L(2316773) is a PRP after L(1051849). The size of the gap makes one suspect that something is amiss (there may be another prime). Or not!
...Makes one think - the same could happen to Mersennes. Like, you know, a jump from 74,207,281 to >150,000,000.
Attached Thumbnails
Click image for larger version

Name:	Log2_L#n.png
Views:	223
Size:	7.5 KB
ID:	16225   Click image for larger version

Name:	Log2_F#n.png
Views:	222
Size:	7.0 KB
ID:	16227  
Batalov is offline   Reply With Quote
Old 2017-06-11, 11:11   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

386610 Posts
Default

Quote:
Originally Posted by Batalov View Post
L(2316773) is a PRP
Code:
? n=2316773;N=fibonacci(n+1)-fibonacci(n-1);write("Lucas_2316773",N)
Code:
time ../../coding/gwnum/lucasPRP Lucas_2316773
Lucas testing on x^2 - 3*x + 1 ...
Is Lucas PRP!

real	51m50.458s
user	148m41.324s
sys	5m29.136s
I guess GIMPS is more fastidious about their RES64. Did R&H keep theirs for you to compare with? -- I guess you all used OpenPFGW.
paulunderwood is offline   Reply With Quote
Old 2017-06-11, 17:24   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×3×5×11×29 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
-- I guess you all used OpenPFGW.
Yes. (That's the Achilles' heel of this project.)

They have their sieve, and I have my sieve, and with regards to sieving -- PFGW itself is doing quite a good job: you can sieve to ~49-50 bits just by doing the proper command-line:
pfgw64 -V -N -k -l -f200"{2p}" -q"L(p)"
where
200 is optional.

Don't know anything about residues, they probably do. I only had one email exchange with them with an answer to 'how far did they test'. Verifying residues is of course possible.
Batalov is offline   Reply With Quote
Old 2017-06-12, 18:50   #4
sweety439
 
sweety439's Avatar
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

24·191 Posts
Default

Please see the thread http://mersenneforum.org/showthread.php?t=21814 for the n-Fibonacci primes and the n-step Fibonacci primes.

Last fiddled with by sweety439 on 2017-06-12 at 18:51
sweety439 is offline   Reply With Quote
Old 2017-06-20, 08:36   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·1,933 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Code:
? n=2316773;N=fibonacci(n+1)-fibonacci(n-1);write("Lucas_2316773",N)
This should be N=fibonacci(n+1)+fibonacci(n-1)
paulunderwood is offline   Reply With Quote
Old 2017-06-20, 14:31   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100101011000102 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Quote:
Originally Posted by paulunderwood View Post
Code:
? n=2316773;N=fibonacci(n+1)-fibonacci(n-1);write("Lucas_2316773",N)
This should be N=fibonacci(n+1)+fibonacci(n-1)
Wait, was the "-" form a "Is Lucas PRP!", too?!
Batalov is offline   Reply With Quote
Old 2017-06-20, 14:33   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,933 Posts
Default

Quote:
Originally Posted by Batalov View Post
Wait, was the "-" form a "Is Lucas PRP!", too?!
Not likely! I think I screen-scraped the correct value and tested it, before using Pari/GP to write the file afresh with wrong value -- I am testing it now, but it was not Fermat 7-PRP

Last fiddled with by paulunderwood on 2017-06-20 at 14:53
paulunderwood is offline   Reply With Quote
Old 2017-06-20, 15:38   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,933 Posts
Default

Wow! The bad value is Lucas-PRP with respect to x^2-3*x+1.

I am now testing the good value, which is using x^2-5*x+1.
paulunderwood is offline   Reply With Quote
Old 2017-06-20, 16:55   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,933 Posts
Default

Code:
../../coding/gwnum/lucasPRP Lucas_2316773 
Lucas testing on x^2 - 5*x + 1 ...
Is Lucas PRP!
I checked F(2316773) (for that is what it is) and it is not Fermat 2-PRP, but it is Lucas PRP w.r.t. x^2-3*x+1
paulunderwood is offline   Reply With Quote
Old 2017-06-28, 16:56   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

115758 Posts
Default

Quote:
Originally Posted by paulunderwood View Post

I checked F(2316773) (for that is what it is) and it is not Fermat 2-PRP, but it is Lucas PRP w.r.t. x^2-3*x+1
There is a simple explanation for this. It is analogous to the fun fact that, if p is prime, then Mp = 2p - 1 is a base-2 pseudoprime, whether Mp is prime or not.

In the present instance, the zeroes of the polynomial f = x^3 - 3*x + 1 are the squares of the zeroes of x^2 - x - 1. Consequently, if s = Mod(2*x - 3, f) [so that s is a square root of 5], then we may write

Mod(x, f)^n = Mod((L2*n + F2*n*s)/2, f).

Now, given a modulus N > 1, we see that Mod(x, f)^n == 1 (mod N) when L2*n == 2 (mod N) and F2*n == 0 (mod N).

Now let p be an odd prime number, and (5/p) = -1 (i.e. p == 3 or 7 (mod 10)). Then p remains prime in the ring R = Z[Mod(x, f)] (which is the maximal order of K = Q[Mod(x, f)]), and

r^p == r' (mod pR) for any r in R, where ' is conjugation in K/Q ["Frobenius automorphism"]. Consequently, we have

Fp+1 == 0 (mod pR) and Lp+1 == L1 = 2 (mod pR), so that Mod(x, f)p+1 == 1 (mod pR).

Now, we show that, if P = Fp, then Mod(x, f)P+1 == 1 (mod PR), whether P is prime or not, regardless of whether (5/P) = 1 or -1.

We also have (again assuming (5/p) = -1) Fp == -1 (mod p). This means [since P = Fp] that

p|(P + 1), so that P|FP+1. Therefore P|F2*(P+1) also. Now, in order to show that

Mod(x, f)P+1 == 1 (mod PR),

we only need to show that

L2*(P+1) == 2 (mod P).

Since P+1 is even, we have

(L(P+1))2 - 5*(FP+1)2 = 4, so that

(L(P+1))2 == 4 (mod P). Again, since P+1 is even, we have

L2*(P+1) = (L(P+1))2 - 2, whence

L2*(P+1) == 2 (mod P),

and the proof is complete.

Remarks: I drew a blank on L(P+1) (mod P), apart from its square being 4 (mod P). If P were prime, L(P+1) would be == -2 (mod P). If it turned out to be anything other than 2 or -2 (mod P), it would immediately give a factorization of P.

One has (5/p) = (5/Fp) = -1 when p == 7, 13, 23, 37, 47, or 53 (mod 60); 2316773 == 53 (mod 60).

Last fiddled with by Dr Sardonicus on 2017-06-28 at 16:57
Dr Sardonicus is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucas-Lehmer Primes henryzz And now for something completely different 42 2019-06-03 14:09
Primes in n-fibonacci sequence and n-step fibonacci sequence sweety439 And now for something completely different 17 2017-06-13 03:49
Smarandache-Fibonacci Primes rogue And now for something completely different 5 2016-07-18 14:33
Fibonacci and Lucas factors Raman Math 40 2010-07-19 03:30
Factoring Fibonacci/Lucas numbers geoff Factoring 13 2005-12-23 01:59

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


Fri Oct 22 13:18:07 UTC 2021 up 91 days, 7:47, 1 user, load averages: 1.20, 1.41, 1.34

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