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

Re: [PrimeNumbers] it works!

Expand Messages
  • 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 1 of 5 , Feb 6, 2008
    • 0 Attachment
      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 2 of 5 , Feb 7, 2008
      • 0 Attachment
        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.