## Re: Lucas mersenne ?

Expand Messages
• Thanks for the clarification, Mike. But Shane s question was not answered by either of us: is there a Lucas mersenne pseudoprime, M(p)=2^p-1 with prime p and
Message 1 of 12 , Jan 5, 2002
• 0 Attachment
Thanks for the clarification, Mike.
But Shane's question was not answered by either of us:
is there a Lucas mersenne pseudoprime,
M(p)=2^p-1 with prime p and composite M(p)
and one of the two tests satisfied?
It's a nice question!
David
• ... So, then I most ask the most obvious question ? Using the Fibonacci sequence: Case 1: F(2^p) mod 2^p -1 = 0 Case 2: F(2^p -2) mod 2^p -1 = 0 F(4)=3 C1
Message 2 of 12 , Jan 5, 2002
• 0 Attachment
> Thanks for the clarification, Mike.
> But Shane's question was not answered by either of us:
> is there a Lucas mersenne pseudoprime,
> M(p)=2^p-1 with prime p and composite M(p)
> and one of the two tests satisfied?
> It's a nice question!
> David

So, then I most ask the most obvious question ?
Using the Fibonacci sequence:

Case 1: F(2^p) mod 2^p -1 = 0
Case 2: F(2^p -2) mod 2^p -1 = 0

F(4)=3 C1
F(8)=7 C1
F(30)=31 C2
F(128)=127 C1

F(8190,8192)=8191 ?
F( ... ?

The cases so far between Lucas and Fibonacci are identical.
Is the Golden String involved ? (ie.1011010110110...)

Maybe I've gone to far !
Shane F.
• ... I think not, Shane. It seems to me that you have stayed in the same place, since F(2*n)=L(n)*F(n). David Broadhurst
Message 3 of 12 , Jan 5, 2002
• 0 Attachment
Shane Findley wrote:
> Maybe I've gone to far !
I think not, Shane.
It seems to me that you have stayed in the same place,
since F(2*n)=L(n)*F(n).
• One more, issue. Case 2, seems to have 2^p +1 /3 as a prime divisor too ?
Message 4 of 12 , Jan 5, 2002
• 0 Attachment
One more, issue.
Case 2, seems to have 2^p +1 /3 as a prime divisor too ?
• ... I guess what you mean is:- if L(2^(p-1)-1) mod (2^p-1) = 0 [CASE2} then L(2^(p-1)-1) mod (2^p+1)/3 = 0. Well, as per my previous communication, write q =
Message 5 of 12 , Jan 6, 2002
• 0 Attachment
Shane wrote:
> One more, issue.
> Case 2, seems to have 2^p +1 /3 as a prime divisor too ?

I guess what you mean is:-
if L(2^(p-1)-1) mod (2^p-1) = 0 [CASE2}
then L(2^(p-1)-1) mod (2^p+1)/3 = 0.

Well, as per my previous communication, write q = 2^p-1.

If CASE2, then q mod 5 = +-1, and q divides L(m) with m=(q-1)/2 = 2^(p-1)-1.
But q mod 5 = +1 => (2^p+1) mod 5 = 3 => (2^p+1)/3 mod 5 = +1,
and q mod 5 = -1 => (2^p) mod 5 = 0 which is impossible.
So in CASE2, (2^p+1)/3 mod 5 = 1,
so (2^p+1)/3 divides L(n) with n=((2^p+1)/3-1)/2 = (2^(p-1)-1)/3.
But any prime dividing L(n) also divides L(3*n)=L(2^(p-1)-1).
Q.E.D.

Mike Oakes
• In a message dated 05/01/2002 12:42:45 GMT Standard Time, ... I have obtained a partial answer to this question: there is no such Mersenne with (prime or
Message 6 of 12 , Jan 8, 2002
• 0 Attachment
In a message dated 05/01/2002 12:42:45 GMT Standard Time,

> Thanks for the clarification, Mike.
> But Shane's question was not answered by either of us:
> is there a Lucas mersenne pseudoprime,
> M(p)=2^p-1 with prime p and composite M(p)
> and one of the two tests satisfied?
> It's a nice question!
>

I have obtained a partial answer to this question: there is no such Mersenne
with (prime or composite) p <= 4500. [I'm sure you'll appreciate the number
of CPU cycles that went into this result, David -- L(2^4499) is quite big! --
did I compute it? -- "Were there but world enough and time", as the poet put
it...]

However, I expect there actually to be infinitely many such Mersennes, for
the following reason:- about one in 100,000 integers are "Lucas pseudoprimes"
(as defined in my previous posting), the first being 15251=101*151, the 23rd
being 1970299=199*9901 - and no, they don't ALL have just 2 primes factors:-).
So, if there is nothing special about the form (2^n-1) (a big IF), and if the
density of these pseudoprimes doesn't decrease too much with increasing size
(another big IF), then one would expect about 1 in 100,000 Mersennes to be
Lucas pseudoprimes.

Anyone up to shedding light on these IFs, and/or extending the search range
above p=4500?

Mike Oakes
• mikeoakes2@a... wrote: 05/01/2002 ... Mersenne with (prime or composite) p
Message 7 of 12 , Sep 30 4:10 PM
• 0 Attachment
mikeoakes2@a... wrote:
05/01/2002
>
> > Thanks for the clarification, Mike.
> > But Shane's question was not answered by either of us:
> > is there a Lucas mersenne pseudoprime,
> > M(p)=2^p-1 with prime p and composite M(p)
> > and one of the two tests satisfied?
> > It's a nice question!
> >
> I have obtained a partial answer to this question: there is no such
Mersenne with (prime or composite) p <= 4500. [I'm sure you'll
appreciate the number of CPU cycles that went into this result,
David -- L(2^4499) is quite big! -- did I compute it? -- "Were
there but world enough and time", as the poet put it...]
> However, I expect there actually to be infinitely many such
Mersennes, for the following reason:- about one in 100,000 integers
are "Lucas pseudoprimes" (as defined in my previous posting), the
first being 15251=101*151, the 23rd
> being 1970299=199*9901 - and no, they don't ALL have just 2 primes
factors:-). So, if there is nothing special about the form (2^n-1)
(a big IF), and if the density of these pseudoprimes doesn't
decrease too much with increasing size (another big IF), then one
would expect about 1 in 100,000 Mersennes to be Lucas pseudoprimes.
> Anyone up to shedding light on these IFs, and/or extending the
search range
> above p=4500?
> Mike Oakes

Hello Mike, You had sent me a program for this, could you send it
again?

I am wondering if PRP/Newpen can be verified first by:
L(2^n-1) mod (k*2^n +/-1)=0
Then if positive execute PRP, and finally proth.

Does the 1/100,000 probability still hold?