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

Carmichael numbers of order 2

Expand Messages
  • David Broadhurst
    ... A Pari-GP script for producing 246 such pseudoprimes is erdos2.gp L=2^7*3^3*5^2*7*11*13*17*19*29; super-smooth seed
    Message 1 of 12 , Mar 31, 2009
    View Source
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "David Broadhurst" <d.broadhurst@...> wrote:

      > 97723892848682923994567734100095132801 =
      > 59*67*71*79*89*101*113*191*233*239*307*349*379*911*2089*5279

      A Pari-GP script for producing 246 such pseudoprimes is

      \\ erdos2.gp
      L=2^7*3^3*5^2*7*11*13*17*19*29; \\ super-smooth seed
      mp=sqrtint(L+1);A=[];B=[];C=[];k=0;sa=[1];sb=[1];
      {forprime(p=1,mp,if(gcd(L,p)==1&&L%(p^2-1)==0,
      k=k+1;if(k%2,A=concat(A,p),B=concat(B,p))));}
      for(k=1,#A,sa=concat(sa,sa*A[k]));
      for(k=1,#B,sb=concat(sb,sb*B[k]));
      st=vecsort(concat(sa%L,vector(#sb,k,(1/sb[k])%L)));
      for(k=3,#st,r=st[k];if(r==st[k-1],C=concat(C,r)));
      {for(k=1,#C,if(k%10==0,print("\\\\ done "k));c=C[k];
      for(j=1,#sa,if(sa[j]%L==c,t=sa[j];break));d=(1/c)%L;
      for(j=1,#sb,if(sb[j]%L==d,t=t*sb[j];break));C[k]=t;)}
      C=vecsort(C);print("{C=[");for(k=1,#C,print(C[k]","));
      print(#C"];}");print(round(gettime/10^3)" seconds");

      but take care: I allocated 3GB of core.

      This generates pseudoprimes N such that, for every prime p
      dividing N, both p-1 and p+1 divide N-1. The full output,
      comprising 246 "Carmichael numbers of order 2", is in
      http://physics.open.ac.uk/~dbroadhu/cert/erdos2.out
      and was obtained in 675 seconds, using 2.7 GB of core.
      The largest pseudoprime, found with the seed L, was

      127905790005702291893660711189034208857122374296\
      660769359758600083769407029360111561601
      =
      23*31*41*43*53*67*71*79*89*109*113*131*181*199
      *239*271*307*349*379*419*449*463*521*571*701
      *1217*1429*1871*2089*2551*4159*5279*5851*9281

      and has 34 prime factors.

      This Erdos-type algorithm was outlined in a talk
      entitled "Higher-order Carmichael numbers",
      given by Everett W. Howe in December 2006:
      alumnus.caltech.edu/~however/talks/FortCollins.pdf

      David Broadhurst
    • Robert Gerbicz
      2009/3/31 David Broadhurst ... Using L=50227322745600 smooth number, |P(2,L)|=60, the above man-in-the-middle approach in c program:
      Message 2 of 12 , Apr 1 12:14 PM
      View Source
      • 0 Attachment
        2009/3/31 David Broadhurst <d.broadhurst@...>

        > --- In primenumbers@yahoogroups.com <primenumbers%40yahoogroups.com>,
        > "David Broadhurst" <d.broadhurst@...> wrote:
        >
        > > 97723892848682923994567734100095132801 =
        > > 59*67*71*79*89*101*113*191*233*239*307*349*379*911*2089*5279
        >
        > A Pari-GP script for producing 246 such pseudoprimes is
        >
        > \\ erdos2.gp
        > L=2^7*3^3*5^2*7*11*13*17*19*29; \\ super-smooth seed
        > mp=sqrtint(L+1);A=[];B=[];C=[];k=0;sa=[1];sb=[1];
        > {forprime(p=1,mp,if(gcd(L,p)==1&&L%(p^2-1)==0,
        > k=k+1;if(k%2,A=concat(A,p),B=concat(B,p))));}
        > for(k=1,#A,sa=concat(sa,sa*A[k]));
        > for(k=1,#B,sb=concat(sb,sb*B[k]));
        > st=vecsort(concat(sa%L,vector(#sb,k,(1/sb[k])%L)));
        > for(k=3,#st,r=st[k];if(r==st[k-1],C=concat(C,r)));
        > {for(k=1,#C,if(k%10==0,print("\\\\ done "k));c=C[k];
        > for(j=1,#sa,if(sa[j]%L==c,t=sa[j];break));d=(1/c)%L;
        > for(j=1,#sb,if(sb[j]%L==d,t=t*sb[j];break));C[k]=t;)}
        > C=vecsort(C);print("{C=[");for(k=1,#C,print(C[k]","));
        > print(#C"];}");print(round(gettime/10^3)" seconds");
        >
        > but take care: I allocated 3GB of core.
        >
        > This generates pseudoprimes N such that, for every prime p
        > dividing N, both p-1 and p+1 divide N-1. The full output,
        > comprising 246 "Carmichael numbers of order 2", is in
        > http://physics.open.ac.uk/~dbroadhu/cert/erdos2.out<http://physics.open.ac.uk/%7Edbroadhu/cert/erdos2.out>
        > and was obtained in 675 seconds, using 2.7 GB of core.
        > The largest pseudoprime, found with the seed L, was
        >
        > 127905790005702291893660711189034208857122374296\
        > 660769359758600083769407029360111561601
        > =
        > 23*31*41*43*53*67*71*79*89*109*113*131*181*199
        > *239*271*307*349*379*419*449*463*521*571*701
        > *1217*1429*1871*2089*2551*4159*5279*5851*9281
        >
        > and has 34 prime factors.
        >
        > This Erdos-type algorithm was outlined in a talk
        > entitled "Higher-order Carmichael numbers",
        > given by Everett W. Howe in December 2006:
        > alumnus.caltech.edu/~however/talks/FortCollins.pdf<http://alumnus.caltech.edu/%7Ehowever/talks/FortCollins.pdf>
        >
        > David Broadhurst
        >
        >
        >

        Using L=50227322745600 smooth number, |P(2,L)|=60, the above
        man-in-the-middle approach in c program:
        #P=26 and #Q=34 was possible using 1GB Ram in about half a day. The expected
        number of solutions is 2^60/eulerphi(L)=143643, in fact it has been found
        144153 Carmichael numbers of order 2, downloadable at
        http://robert.gerbicz.googlepages.com/carmichael2.zip


        [Non-text portions of this message have been removed]
      • David Broadhurst
        I have sent an on-line message to Robert Gerbicz mooting the possibility to a distributed search for a Carmichael number of order 3. [Actually, I intended it
        Message 3 of 12 , Apr 1 3:06 PM
        View Source
        • 0 Attachment
          I have sent an on-line message to Robert Gerbicz
          mooting the possibility to a distributed search
          for a Carmichael number of order 3.

          [Actually, I intended it to go the list,
          but forgot that this is not the default,
          so I don't have a copy my own suggestion :-(
          Perhaps Robert might post my lost message, here?]

          David (not used to this unfriendly on-line default option)
        • David Broadhurst
          ... I have tested these. And every single one of them is right! http://www.springerlink.com/content/km644472gh145147/ Congrats to Robert David
          Message 4 of 12 , Apr 1 6:18 PM
          View Source
          • 0 Attachment
            --- In primenumbers@yahoogroups.com,
            Robert Gerbicz <robert.gerbicz@...> wrote:

            > 144153 Carmichael numbers of order 2

            I have tested these.
            "And every single one of them is right!"
            http://www.springerlink.com/content/km644472gh145147/

            Congrats to Robert

            David
          • Robert Gerbicz
            I was lazy and did not use binary indexing for products of primes. Yes, I used long long int (8bytes) to store the residue (L
            Message 5 of 12 , Apr 2 1:31 PM
            View Source
            • 0 Attachment
              "I was lazy and did not use binary indexing for products of primes."

              Yes, I used long long int (8bytes) to store the residue (L<2^63), and int (4
              bytes) to store the offset of the prime divisors (there were 26 primes in P
              so it was enough).

              Searching for Carmichael number of order 3 would be very hard:
              by the following quick code:
              generatesmooth(n)=T=1;forprime(p=2,n,q=p;while(q*p<=n,q*=p);T*=q);return(T)
              this is generating super smooth numbers, but for example for n=1000 this is
              giving only P(3,T)~225 numbers
              , the last 3 of them in order what I have found are:
              153572717
              217815289
              264982051
              So there are very few larger primes in P(3,T) set. Say there are another 25,
              then the expected number of solutions are
              2^250/eulerphi(generatesmooth(1000))=3*10^(-357), and it would require about
              2^200 multiplications/divisions (using man-in-the middle algorithm #P=25,
              #Q=200). Obviously using smaller n gives larger but still very small
              probability to find a 3 order number. So we have to increase the value of n:

              For example: L=generatesmooth(20000) gives P(L,3)>30000 primes and this
              means that it generates many Carmichael numbers of order 3:
              2^30000/eulerphi(L)>>1. But to find even one solution using this L value is
              still very hard.


              [Non-text portions of this message have been removed]
            • David Broadhurst
              In a talk http://alumnus.caltech.edu/%7Ehowever/talks/FortCollins.pdf given in December 2006, Everett Howe posed this Open Problem : What are the first 3
              Message 6 of 12 , Apr 2 6:39 PM
              View Source
              • 0 Attachment
                In a talk
                http://alumnus.caltech.edu/%7Ehowever/talks/FortCollins.pdf
                given in December 2006, Everett Howe posed this "Open Problem":

                "What are the first 3 Carmichael numbers of order 2?"

                Here is the answer:

                443372888629441
                39671149333495681
                842526563598720001

                David Broadhurst
              • David Broadhurst
                ... Richard Finch calls these unusually strong Lucas-Carmichael-minus (uLC-) numbers, with p^2-1|N-1, for every prime p|N. See:
                Message 7 of 12 , Apr 3 7:09 AM
                View Source
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com,
                  "David Broadhurst" <d.broadhurst@...> wrote:

                  > "What are the first 3 Carmichael numbers of order 2?"
                  >
                  > 443372888629441
                  > 39671149333495681
                  > 842526563598720001

                  Richard Finch calls these
                  "unusually strong Lucas-Carmichael-minus" (uLC-) numbers,
                  with p^2-1|N-1, for every prime p|N. See:
                  http://www.chalcedon.demon.co.uk/rgep/p20.pdf

                  I found the third of these by mining Richard's file of
                  Carmichael numbers between 10^17 than 10^18.
                  The first two had already been noted in
                  http://www.chalcedon.demon.co.uk/rgep/cartable.html

                  Richard classified
                  582920080863121 = 41 * 53 * 79 * 103 * 239 * 271 * 509
                  as a "strong", but not "unusually strong",
                  Lucas-Carmichael-minus number
                  since in this case both p-1 and p+1
                  divide N-1, for each prime p|N, but p^2-1
                  does not divide N-1 in the cases p = 79, 239, 271,
                  where p^2 = 1 mod 2^5
                  whilst N = 17 mod 2^5.

                  If we ask merely that p-1 and (p+1)/2 divide N-1,
                  then the following 3 numbers also occur, for N < 10^18:
                  28295303263921
                  894221105778001
                  2013745337604001
                  making 7 in all, of which only

                  842526563598720001
                  = 17 * 61 * 71 * 89 * 197 * 311 * 769 * 2729

                  occurs for 10^18 > N > 10^17.

                  Finally, I remark that Richard found precisely one
                  "unusually strong Lucas-Carmichael-plus" (uLC+) number,
                  with p^2-1|N+1, for prime p|N and N < 10^13, namely

                  79397009999 = 23 * 29 * 41 * 43 * 251 * 269.

                  David
                • David Broadhurst
                  Oh dear, another silly typo: I meant Richard Pinch, of course.
                  Message 8 of 12 , Apr 3 7:21 AM
                  View Source
                  • 0 Attachment
                    Oh dear, another silly typo: I meant Richard Pinch, of course.
                  Your message has been successfully submitted and would be delivered to recipients shortly.