- Jan 4, 2010
> 2. Primality testing - a newby

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

> 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 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.

(Almost )everything simple has been done before.

> 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?

>

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

According to test 1,

> c=n, r=2n-1

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

> if q=p then p is r+- and not prime

>

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

Counter Example?

> 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

>

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

My comments could be more complete if you had also

> 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.

>

>

indicated, at least by a hint,

how you derived the formulas you used in the program.

Kermit Rose. - << Previous post in topic