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

Re: [PrimeNumbers] Re: it works!

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