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

Primality testing - a newby

Expand Messages
  • Kermit Rose
    ... (6 m + 1) * (6 n + 1) = 36 m n + 6 m + 6 n + 1 (6 m -1) * (6 n + 1) = 36 m n + 6 m - 6 n - 1 ( 6 m + 1 ) * (6 n - 1) = 36 mn - 6 m + 6 n - 1 (6 m -1 ) *
    Message 1 of 2 , Jan 4, 2010
    • 0 Attachment
      > 2. Primality testing - a newby
      > Posted by: "William" wj.forman@... fatbobforman
      > Date: Sun Jan 3, 2010 2:50 pm ((PST))
      >
      > I have divided the primes into 3 groups working on a general format of 36mn +/- 6m +/- 6n +/- 1.
      >
      (6 m + 1) * (6 n + 1) = 36 m n + 6 m + 6 n + 1

      (6 m -1) * (6 n + 1) = 36 m n + 6 m - 6 n - 1

      ( 6 m + 1 ) * (6 n - 1) = 36 mn - 6 m + 6 n - 1

      (6 m -1 ) * (6 m + 1) = 36 m n - 6 m - 6 n + 1

      So you really mean primes which are of one of the four forms

      36 m n + 6 m + 6 n - 1 = (6 m + 1) (6 n + 1) - 2,
      36 m n + 6 m - 6 n + 1 = (6 m - 1) (6 n + 1) + 2,
      36 m n - 6 m + 6 n +1 = (6 m + 1) ( 6 n - 1) + 2,
      36 m n - 6 m - 6 n - 1 = (6 m - 1) ( 6 n - 1 ) - 2.

      Note that no twin primes occur among these four forms.

      Also,

      6 * (6 m n + m + n ) - 1 = 36 m n + 6 m + 6 n - 1 = (6 m + 1) (6 n +
      1) - 2,
      6 * ( 6 m n + m - n) + 1 = 36 m n + 6 m - 6 n + 1 = (6 m - 1) (6 n + 1)
      + 2,
      6 * (6 m n - m + n) + 1 = 36 m n - 6 m + 6 n + 1 = (6 m + 1) ( 6 n - 1)
      + 2,
      6 * (6 m n - m - n) - 1=36 m n - 6 m - 6 n - 1 = (6 m - 1) ( 6 n - 1
      ) - 2.

      P can occur as one of these four forms if and only if
      (1) P is 6 d + 1 where d is of form 6 m n + m - n or 6 m n - m + n
      or
      (2) P is 6 d - 1 where d is of form 6 m n + m + n or 6 m n - m - n





      > Below is a simple and I think efficient algorithm for testing 36mn+6m-6n-1 primes.

      I believe we can make simpler and more efficient algorithms. :)

      36mn+6m-6n-1 = (6 m -1) * (6 n + 1)

      Perhaps you mistyped something else as 36mn+6m-6n-1.



      > The other two algorithms are similar.
      > If it makes you groan at my stupidity then please direct me to somewhere where I can learn to be less dense.
      > Otherwise - has it been done before?
      >

      (Almost )everything simple has been done before.

      In my vocabulary,
      There are no stupid algorithms.

      There are algorithms that fail,
      and there are algorithms that are woefully inefficient.

      Any algorithm that reflects your learning the math is a smart algorithm,.



      > Let p be a potential prime p = 30a + b : b in {11,17,23,29}
      >
      11 = 6 * 2 - 1
      17 = 6 * 3 - 1
      23 = 6 * 4 - 1
      29 = 6 * 5 - 1

      So you really meant either 36 m n + m + n - 1 = (6 m + 1)(6 n + 1)
      - 2 or 36 m n - m - n - 1 = (6 m -1 )(6n -1) + 2.


      > 1. n = ((81+8p)^1/2 + 5)/24, rounded up to an integer
      > c=n, r=2n-1
      > q = ((24n-5)^2 -81)/8
      > if q=p then p is r+- and not prime
      >
      According to test 1,
      221 = 13 * 17 is not prime.
      551 = 19 * 29 is not prime.
      1643 = 31*53 is not prime.
      3311 = 11 * 301 is not prime
      4361 = 49*89 is not prime
      6893 = 61 * 113 is not prime
      etc

      I would like to know the algebraic analysis that led to this test 1 formula.

      Don't know what you mean by " is r+- ".

      > 2. q = q - 36c - 42, r = r - 1
      > if r=0 then p is prime
      > if q=p then p is r+- and not prime
      > if q > p then goto 2
      > if q < p then goto 3
      >
      Counter Example?

      p = 77;

      Step1

      n = ((81+8p)^1/2 + 5)/24, rounded up to an integer = 1,

      c=n = 1

      r=2n-1 = 1

      q = ((24n-5)^2 -81)/8 = 35

      Step 2:

      q = q - 36c - 42 = -43

      r = r - 1 = 0

      if r=0 then p is prime.

      r = 0, but p = 77 is not prime.

      Incidentally, 77 = 6 * 12 + 5 = 6 * 13 - 1
      and 77 = (6 + 1) * (2 * 6 - 1) = 36 * 2 + 2 * 6 - 1 * 6 - 1
      13 = 6 * (2 * 1) + 2 - 1




      > 3. q = q - 36r - 30, c = c - 1
      > if c=0 then p is prime
      > if q=p then p is r+- and not prime
      > if q > p then an error has occurred
      > if q < p then goto 4
      > 4. q = q + 36c + 42, r = r + 1
      > if q=p then p is r+- and not prime
      > if q > p then goto 5
      > if q < p then goto 4
      > 5. q = q - 36r - 30, c = c - 1
      > if c=0 then p is prime
      > q = 36c - 42, r = r - 1
      > if q=p then p is r+- and not prime
      > if q > p then an error has occurred
      > if q < p then goto 4
      > I would appreciate your comments.
      >
      >
      My comments could be more complete if you had also
      indicated, at least by a hint,
      how you derived the formulas you used in the program.

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