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

it works!

Expand Messages
  • leavemsg1
    the following program tries to determine the primality of a number by combining two tests into one, avoiding the usual pseudo-prime situ- ation: 10 cls 20
    Message 1 of 5 , Feb 5, 2008
      the following program tries to determine the primality of a number by
      combining two tests into one, avoiding the usual pseudo-prime situ-
      ation:

      10 cls
      20 input N
      30 NN= int((N-1)/2)
      40 X= (2^N-3^NN-(N-1)) mod N
      50 Y = N mod 5
      60 print N;X
      70 if (X=2 or X=4) and Y<>0 then print "prime"
      80 goto 10

      it inevitably misses the 2, 3, and 5, but catches all the rest as far
      as I can test it.

      my computer is somewhat outdated, but it told me that there were 168
      primes before the number 1001, when I used this code inside a for-
      loop.

      i am aware of the law of small numbers, but can anyone realistically
      find a flaw or counter-example in this unproven technique ???

      Bill B.
    • Alan Eliasen
      ... Well, it fails on even numbers, for one. Additional failures occur a bit later on odd numbers: x y Error at 1729 2 4 Error at 2821 2
      Message 2 of 5 , Feb 5, 2008
        leavemsg1 wrote:

        > the following program tries to determine the primality of a number by
        > combining two tests into one, avoiding the usual pseudo-prime situ-
        > ation:
        >
        > 10 cls
        > 20 input N
        > 30 NN= int((N-1)/2)
        > 40 X= (2^N-3^NN-(N-1)) mod N
        > 50 Y = N mod 5
        > 60 print N;X
        > 70 if (X=2 or X=4) and Y<>0 then print "prime"
        > 80 goto 10
        >
        > it inevitably misses the 2, 3, and 5, but catches all the rest as far
        > as I can test it.
        >
        > my computer is somewhat outdated, but it told me that there were 168
        > primes before the number 1001, when I used this code inside a for-
        > loop.
        >
        > i am aware of the law of small numbers, but can anyone realistically
        > find a flaw or counter-example in this unproven technique ???

        Well, it fails on even numbers, for one.

        Additional failures occur a bit later on odd numbers:

        x y
        Error at 1729 2 4
        Error at 2821 2 1
        Error at 7921 2 1
        Error at 8911 4 1
        Error at 13699 4 4
        Error at 15841 2 1
        Error at 18721 2 1
        Error at 29341 2 1
        Error at 31621 2 1

        Sorry.

        --
        Alan Eliasen | "Furious activity is no substitute
        eliasen@... | for understanding."
        http://futureboy.us/ | --H.H. Williams
      • Alan Eliasen
        ... Hopefully for Bertrand, he didn t say that. If I m supposed to be finding counterexamples and errors today, that single sentence contains a treasure
        Message 3 of 5 , Feb 6, 2008
          Danny Fleming wrote:
          > Bertrand's postulate proved that there are at least two primes from x
          > to 2x for any integer.

          Hopefully for Bertrand, he didn't say that. If I'm supposed to be
          finding counterexamples and errors today, that single sentence contains
          a treasure trove.

          You may also wish to mention how you believe it related to the
          messages that you replied to.

          --
          Alan Eliasen | "Furious activity is no substitute
          eliasen@... | for understanding."
          http://futureboy.us/ | --H.H. Williams
        • Jacques Tramu
          Assuming N odd, First counter-examples with their prime factors : 1729 { 7, 13, 19} 2821 { 7, 13, 31} 7921 { 89} 8911 { 7, 19, 67} 13699 { 7, 19,
          Message 4 of 5 , Feb 6, 2008
            Assuming N odd, First counter-examples with their prime factors :

            1729 { 7, 13, 19}
            2821 { 7, 13, 31}
            7921 { 89}
            8911 { 7, 19, 67}
            13699 { 7, 19, 103}
            15841 { 7, 31, 73}
            18721 { 97, 193}
            29341 { 13, 37, 61}
            31621 { 103, 307}
            32761 { 181}
            41041 { 7, 11, 13, 41}
            46657 { 13, 37, 97}
            49141 { 157, 313}
            52633 { 7, 73, 103}
            63973 { 7, 13, 19, 37}
            64177 { 29, 2213}
            75361 { 11, 13, 17, 31}
            83333 { 167, 499}
            93961 { 7, 31, 433}
            115921 { 13, 37, 241}
            126217 { 7, 13, 19, 73}
            129481 { 11, 79, 149}
            162401 { 17, 41, 233}
            .......
            if( N < 10 000 000) whe have 123 failures.

            Regards,
            JT


            >the following program tries to determine the primality of a number by
            >combining two tests into one, avoiding the usual pseudo-prime situ-
            >ation:

            10 cls
            20 input N
            30 NN= int((N-1)/2)
            40 X= (2^N-3^NN-(N-1)) mod N
            50 Y = N mod 5
            60 print N;X
            70 if (X=2 or X=4) and Y<>0 then print "prime"
            80 goto 10

            >it inevitably misses the 2, 3, and 5, but catches all the rest as far
            >as I can test it.

            >my computer is somewhat outdated, but it told me that there were 168
            >primes before the number 1001, when I used this code inside a for-
            >loop.

            >i am aware of the law of small numbers, but can anyone realistically
            <find a flaw or counter-example in this unproven technique ???

            >Bill B

            ---------------------------------------
            http://www.echolalie.com
            ---------------------------------------





            [Non-text portions of this message have been removed]
          • Peter Kosinar
            Hello Bill, ... Slightly less programatic description of the test: If both 1) N must not be divisible by 5, and 2) 2^N - 3^((N-1)/2) = 1 or 3 (mod N), then N
            Message 5 of 5 , Feb 7, 2008
              Hello Bill,

              > the following program tries to determine the primality of a number by
              > combining two tests into one, avoiding the usual pseudo-prime situ-
              > ation:

              Slightly less programatic description of the test: If both
              1) N must not be divisible by 5, and
              2) 2^N - 3^((N-1)/2) = 1 or 3 (mod N),
              then N is declared prime.

              Clearly, this test is surely not stronger (although it is likely strictly
              weaker) than a combination of
              1) Divisibility by 5 test,
              2) Base 2 Fermat test and
              3) Base 3 Euler test
              while having about the same time-complexity as these three together (in
              fact, performing the step 3 only if step 2 succeeds can improve the
              actual speed).

              Combining the tests the way you did is usually not a good idea, as you're
              losing some potentially useful information. In particular, instead of
              checking 2^N = 2 (mod N) and 3^((N-1)/2) = +/-1 mod N, you're just
              checking if their difference is equal to something -- which can, unless
              proven otherwise, happen a lot more often.

              Peter

              --
              [Name] Peter Kosinar [Quote] 2B | ~2B = exp(i*PI) [ICQ] 134813278
            Your message has been successfully submitted and would be delivered to recipients shortly.