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

Lucas-Lehmer like test

Expand Messages
  • leavemsg1
    Hello, Group. Let n= 1, 2, 3, etc. and Nn= 3^n -2. Does the sequence 1, 7, 25, 79, 241, 727, 1185, etc. have a test for verifying the primality of Nn similar
    Message 1 of 2 , Mar 1 12:49 PM
    • 0 Attachment
      Hello, Group.

      Let n= 1, 2, 3, etc. and Nn= 3^n -2.

      Does the sequence 1, 7, 25, 79, 241, 727, 1185, etc. have a test for
      verifying the primality of Nn similar to the LL test for Mersenne Mp=
      2^p -1?

      I tried for several weeks to find one and couldn't.

      Bill
    • Paul Underwood
      ... No. Note N+1 == 3^n-2+1 == 3^n-1 and N-1 == 3^n-2-1 == 3*(3^(n-1)-1 So given enough factors of N+-1 the combined classical tests can be used:
      Message 2 of 2 , Mar 1 5:54 PM
      • 0 Attachment
        >
        > Let n= 1, 2, 3, etc. and Nn= 3^n -2.
        >
        > Does the sequence 1, 7, 25, 79, 241, 727, 1185, etc. have a test for
        > verifying the primality of Nn similar to the LL test for Mersenne Mp=
        > 2^p -1?
        >

        No.

        Note N+1 == 3^n-2+1 == 3^n-1
        and N-1 == 3^n-2-1 == 3*(3^(n-1)-1

        So given enough factors of N+-1 the combined "classical tests" can be
        used:
        http://primes.utm.edu/prove/index.html

        These have been implemented in PFGW:
        http://groups.yahoo.com/group/primeform/

        At the cutting edge, a less than 33.33 % factored percentage could
        lead to a proof: "Konyagin-Pomerance" (KP) or "Coppersmith
        Howgrave-Graham" (CHG).

        If the number is sub-gigantic (<10,000 digits) it can be proven with
        Marcel Martin's ECCP implementation, Primo:
        http://www.ellipsa.net/

        Wojciech Florek has some good pages covering 3^n-2:
        http://perta.fizyka.amu.edu.pl/pnq/

        > I tried for several weeks to find one and couldn't.
        >

        You aren't the first to try ;-)

        Paul
      Your message has been successfully submitted and would be delivered to recipients shortly.