Browse Groups

• I have divided the primes into 3 groups working on a general format of 36mn +/- 6m +/- 6n +/- 1. Below is a simple and I think efficient algorithm for testing
Jan 3, 2010 1 of 2
View Source
I have divided the primes into 3 groups working on a general format of 36mn +/- 6m +/- 6n +/- 1.
Below is a simple and I think efficient algorithm for testing 36mn+6m-6n-1 primes. 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?

Let p be a potential prime p = 30a + b : b in {11,17,23,29}

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
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
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
• ... (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 ) *
Jan 4, 2010 1 of 2
View Source
> 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