Loading ...
Sorry, an error occurred while loading the content.

Re: Lucas mersenne ?

Expand Messages
  • djbroadhurst
    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
    • ttpi314159
      ... 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
        --- In primenumbers@y..., "djbroadhurst" <d.broadhurst@o...> wrote:
        > 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.
      • djbroadhurst
        ... 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).
          David Broadhurst
        • ttpi314159
          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 ?
          • mikeoakes2@aol.com
            ... 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
            • mikeoakes2@aol.com
              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,
                d.broadhurst@... writes:

                > 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
              • Shane
                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
                  > d.broadhurst@o... writes:
                  >
                  > > 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?
                  What do you think about this variation?
                Your message has been successfully submitted and would be delivered to recipients shortly.