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

Re: fact or fiction

Expand Messages
  • djbroadhurst
    ... It takes less than 2 seconds to prove that there are at least 124880 counterexamples with N
    Message 1 of 4 , Feb 1, 2010
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      Bill Bouris <leavemsg1@...> wrote:

      > if 'N' passes the 2-PRP test, then...
      > if 3, 5, or 7 divides 'N', then 'N' is composite...
      > (or) if either ALL or NONE of them divide 'N-1',
      > then a simple 3-PRP will conclude that 'N' is composite, 
      > without a doubt.

      It takes less than 2 seconds to prove that there are
      at least 124880 counterexamples with N < 10^15. See:
      http://physics.open.ac.uk/~dbroadhu/cert/ct124880.zip

      It is likely that there are *precisely*
      124880 counterexamples with N < 10^15

      David
    • djbroadhurst
      ... In less than 20 seconds, I found 993305 counterexamples in tables from William Galway and Richard Pinch. There are 319226 numbers N
      Message 2 of 4 , Feb 2, 2010
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        Bill Bouris <leavemsg1@...> wrote:

        > if 'N' passes the 2-PRP test, then...
        > if 3, 5, or 7 divides 'N', then 'N' is composite...
        > (or) if either ALL or NONE of them divide 'N-1',
        > then a simple 3-PRP will conclude that 'N' is composite,
        > without a doubt.

        In less than 20 seconds, I found 993305 counterexamples
        in tables from William Galway and Richard Pinch.

        There are 319226 numbers N < 10^15 that are 2-PSP and 3-PSP.
        Of these, 287672 are coprime to 3*5*7.
        Of these, 119450 have N-1 divisible by 3*5*7
        and another 5430 have N-1 coprime to 3*5*7
        giving us 124880 counterexamples below 10^15.

        There are 1296432 Carmichael numbers C between 10^15 and 10^18.
        Of these, 1131205 are coprime to 3*5*7.
        Of these, 868340 have C-1 divisible by 3*5*7
        and another 85 have C-1 coprime to 3*5*7
        giving us 868425 additional counterexamples.

        Tally and timing from Pari-GP:
        124880 + 868425 = 993305 counterexamples in 19320 milliseconds

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