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

Re: Carmichael numbers of order 2

Expand Messages
  • 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 1 of 12 , Apr 1 6:18 PM
      --- 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 2 of 12 , Apr 2 1:31 PM
        "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 3 of 12 , Apr 2 6:39 PM
          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 4 of 12 , Apr 3 7:09 AM
            --- 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 5 of 12 , Apr 3 7:21 AM
              Oh dear, another silly typo: I meant Richard Pinch, of course.
            Your message has been successfully submitted and would be delivered to recipients shortly.