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

Lucas mersenne ?

Expand Messages
  • ttpi314159
    Can someone find a counter example ( DAVID !) L(2^(p-1))mod 2^p -1 = 0 or, L(2^(p-1) -1) mod 2^p -1 = 0,then 2^p-1 prime ? 2^2 -1 divides L(2) 2^3 -1 divides
    Message 1 of 12 , Jan 1, 2002
    • 0 Attachment
      Can someone find a counter example ( DAVID !)
      L(2^(p-1))mod 2^p -1 = 0 or,
      L(2^(p-1) -1) mod 2^p -1 = 0,then 2^p-1 prime ?


      2^2 -1 divides L(2)
      2^3 -1 divides L(4)
      2^5 -1 divides L(15)
      2^7 -1 divides L(63)
      2^13-1 divide L(4095,4096) ?
      ...?


      It just seemed suspicious, but can't find L(4096) or divide if I did.
    • djbroadhurst
      ... 8191 divides L(4095)
      Message 2 of 12 , Jan 2, 2002
      • 0 Attachment
        > 2^13-1 divide L(4095,4096) ?
        8191 divides L(4095)
      • djbroadhurst
        ... p CASE [ 2, CASE1] [ 3, CASE1] [ 5, CASE2] [ 7, CASE1] [13, CASE2] [17, CASE2] [19, CASE1] interesting....
        Message 3 of 12 , Jan 2, 2002
        • 0 Attachment
          > L(2^(p-1))mod 2^p -1 = 0 or, [CASE1]
          > L(2^(p-1) -1) mod 2^p -1 = 0 [CASE2]

          p CASE
          [ 2, CASE1]
          [ 3, CASE1]
          [ 5, CASE2]
          [ 7, CASE1]
          [13, CASE2]
          [17, CASE2]
          [19, CASE1]

          interesting....
        • djbroadhurst
          Yes Shane, yours was indeed a nice observation. The classic Lucas-Lehmer test for Mersennes uses the Lucas sequence with p=2, q=-2, d=p^2-4*q=12 (Ribenboim
          Message 4 of 12 , Jan 2, 2002
          • 0 Attachment
            Yes Shane, yours was indeed a nice observation.

            The classic Lucas-Lehmer test for Mersennes
            uses the Lucas sequence with
            p=2, q=-2, d=p^2-4*q=12 (Ribenboim p.92).

            You can probably use the same batch of theorems
            from Ribenboim to prove the necessity and sufficiency
            of your more complicated two-case test with
            p=1, q=-1, d=p^2-q=5 (i.e. the rabbit case).

            Happy new year

            David
          • mikeoakes2@aol.com
            In a message dated 02/01/2002 08:31:16 GMT Standard Time, ... What s going on here is a special case of the following. Let q be any prime = 3 mod 4. (This
            Message 5 of 12 , Jan 5, 2002
            • 0 Attachment
              In a message dated 02/01/2002 08:31:16 GMT Standard Time,
              d.broadhurst@... writes:

              > > L(2^(p-1))mod 2^p -1 = 0 or, [CASE1]
              > > L(2^(p-1) -1) mod 2^p -1 = 0 [CASE2]
              >
              > p CASE
              > [ 2, CASE1]
              > [ 3, CASE1]
              > [ 5, CASE2]
              > [ 7, CASE1]
              > [13, CASE2]
              > [17, CASE2]
              > [19, CASE1]
              >
              > interesting....
              >

              What's going on here is a special case of the following.

              Let q be any prime = 3 mod 4. (This includes any of the form 2^p-1.)
              Then q divides L(m), where
              m = (q-1)/2 if q = +-1 mod 5,
              and m = (q+1)/2 if q = +-2 mod 5.
              [See e.g. Ribenboim's "New Book of Prime Number Records", Chap 2 Sec IV for a
              comprehensive treatment of all this.]

              For the Mersennes, this gives:-
              p q=2^p-1 q mod 5 m=(q+-1)/2 CASE
              2 3 -2 2 CASE1
              3 7 2 4 CASE1
              5 31 1 15 CASE2
              7 127 2 64 CASE1
              11 2047=23*89 [not prime] --
              13 8191 1 4095 CASE2
              17 131071 1 65535 CASE2
              19 524287 2 262144 CASE1

              Numbers q = 3 mod 4 which divide L(m) are not, however, NECESSARILY prime,
              only "Lucas pseudoprimes"; so we don't have a new primality test here,
              unfortunately.

              Mike Oakes
            • 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 6 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 7 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 8 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 9 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 10 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 11 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 12 of 12 , Sep 30, 2002
                          • 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.