# New Test for Primes

1. Sep 20, 2011

### ramsey2879

Can anyone find an exception to this test for odd P > 3?

P = Input an odd number > 3
Msg = "not Prime"
A = 4
B = 32
Do
C = B
B = Mod(6*C - A + 8,P)
A = C
If A = 4 Then
If B != 0 Then Exit Do
Else Msg = "Prime"
Exit Do
End If
End If
If B = 0 Then Exit Do
Loop
Print "P is" & Msg
End

Thanks, Ken Ramsey

2. Sep 20, 2011

### TylerH

By my C++ translation, it doesn't work for 5.

Code (Text):
#include <iostream>
#include <string>

using namespace std;

int main()
{
std::string message = "Not Prime";
int p = 5;
int a = 4, b = 32;

while(b != 0)
{
int c = b;
b = (6 * c - a + 8) % p;
a = c;

if(a == 4)
{
if(b != 0)
break;
else
{
message = "Prime";
break;
}
}
}

cout << p << ": " << message;

return 0;
}

3. Sep 20, 2011

### D H

Staff Emeritus
Unless I coded your algorithm wrong, 5, 7, and 13 are "not Prime". 15 is particularly troublesome. It cycles and never returns.

4. Sep 20, 2011

### ramsey2879

I don't know C++ so I cant tell where the problem is. The strings for 5,7,and 13 and 15 support my test.

For 5 the string is
{4,32,1,2,4,0 ...} so this should return P is prime

For 7 the string is
{4,32,0} which appears to give a false reading but 32 mod 7 = 4 so the string should have been {4,4,0} which would give a correct result. Since 32 equals 4 mod 7 but not for any other prime, this exception is merely a result of my giving a shortened version of the algorithm.

For 13 the string is {4,32,1,8,3,5,9,5,3,1,6,4,0 ...} so this should give a correct result also.

For 15 the string is {4,32,1,12,4,5 ...} Since the 4 is followed by a non-zero number, i.e. 5, your code should break at this point.

In short, you must have miss read my original code or made a error in translation.

To further help in your coding, note the following sequence for P = 9:
{4,32,7,0}. Since a zero appears in the string not immediately after a "4", the code should break at this point also. That is why I included the final clause "If B = 0 Then Exit Do" because the case where A= 4, and is follow by a zero for B, was made part of an earlier test. These are the only necessary tests.

Last edited: Sep 20, 2011
5. Sep 21, 2011

### D H

Staff Emeritus
Your algorithm. As far as I can tell his implementation is spot-on.

What string? What are the values for A, B, C each pass through your loop?

If you don't know C++, write your algorithm as code in some language you do know.

6. Sep 21, 2011

### RamaWolf

My coding:
Code (Text):

tmp2:=" is compo";
a:=4; b:=32;
tmp1:=Str(b);
while b <> 0 do
c:=b;
b:=(6*c - a + 8)  mod p;
tmp1:=concat(tmp1,"|",Str(b));
a:=c;
if c = 4 then
break;
end;
end;
if b = 0 then
if c = 4 then
tmp2:=" is prime";
end;
end;
writeln(tmp1);
writeln("n = ", p, tmp2);

---------------------------------
My results:
n = 5
32|1|2|4|0
n = 5 is prime
n = 7
32|0
n = 7 is compo
n = 9
32|7|0
n = 9 is compo
n = 11
32|9|8|3|7|3|8|9|10|4|0
n = 11 is prime
n = 13
32|1|8|3|5|9|5|3|8|1|6|4|0
n = 13 is prime
n = 15
32|1|12|4|5
n = 15 is compo
n = 17
32|9|13|9|15|4|0
n = 17 is prime
n = 19
32|6|12|17|3|9|2|11|15|11|2|9|3|17|12|6|13|4|0
n = 19 is prime
n = 21
32|7|18|4|14
n = 21 is compo
n = 23
32|12|2|8|8|2|12|9|4|0
n = 23 is prime
n = 25
32|21|2|24|0
n = 25 is compo
n = 27
32|7|18|1|23|10|18|25|5|13|0
n = 27 is compo
n = 29
32|22|21|25|21|22|3|4|0
n = 29 is prime
n = 31
32|10|5|28|16|14|14|16|28|5|10|1|4|0
n = 31 is prime
n = 33
32|31|30|25|29|25|30|31|32|4|0
n = 33 is prime
-----------------------------------------------
for n = 32 the algorithms fails.

Last edited by a moderator: Sep 21, 2011
7. Sep 21, 2011

### D H

Staff Emeritus
RamaWolf:
I edited your post to insert the code in code blocks.

8. Sep 21, 2011

### D H

Staff Emeritus
You missed this one. It's right there in your output.

The problem with coding this algorithm in a computer language is that the meaning of modulo for negative integers isn't particularly well defined. Given integers $a$ and $b$, there are three common implementations of integer division for negative numbers and hence three ways to implement $a \mod b$ are
• Truncated division, $q=\mbox{sgn}(a/b)\lfloor{|a/b|}\rfloor$
• Floored division, $q=\lfloor{a/b}\rfloor$
• Euclidean algorithm, $q = \lfloor{a/b}\rfloor\,\text{if b is positive},\, \lceil{a/b}\rceil\,\text{if b is negative}$.

In this case, the divisor is positive, so the Euclidean algorithm reverts to floored division.

The algorithm in the OP fails for 7, 33, 35, 45, 51, 55, 57, 63, 77, 99, ... for floored division.
It fails for 5, 7, 13, 15, 33, 35, 39, 43, 45, 51, 53, 55, 57, 63, 69, 73, 77, 97, 99, ... for truncated division.

Edit
Word of warning: When implementing this in a computer language, do not use unsigned integers. Unsigned integers in most languages use modulo 2N arithmetic: A+B → A+B mod 2N. This will lead to infinite loops.

Last edited: Sep 21, 2011
9. Sep 21, 2011

### dodo

Hello, ramsey,
could you copy here the sequences you obtain with p=6 and p=10, please?

I need these to reconstruct what you're trying to do, since I managed to obtain the same results as you so far, but failing for 6 and 10 (which show as "primes").

To the rest of the audience, apparently his interpretation of $a \text{ mod } b$ for negative $a$ and positive $b$ involves taking a quotient $q=\lceil{a/b}\rceil$, and then taking the positive remainder from that.

A bit more on this "translation": I believe the idea is to explore the recurrence sequence
\begin{align*} b_0 &= 0 \\ b_1 &= 4 \\ b_n &= (6b_{n-1} - b_{n-2} + 8) \text{ mod } p & \text{for } n > 1 \end{align*}
with "mod" defined as above, and assert two things:
• that the sequence will always reach a $b_n = 4$, for some $n > 1$; and
• that, at that final point, the next value $b_{n+1}$ should say something about the primality of $p$, depending on whether it is 0 or not.

Last edited: Sep 21, 2011
10. Sep 21, 2011

### D H

Staff Emeritus
In fairness to ramsey, he never said this algorithm worked for even numbers.

Since the interpretation for modulo for negative dividends / negative divisors is a bit fuzzy, perhaps a clarification from ramsey2879 is due:

What is -2 mod 5? And -7 mod 5?

Regardless of the interpretation, 33 and 35 (and many others) fail but never do run into this ambiguity. 6*C - A + 8 is always positive in these cases.

Except ramsey started with b0=4, b1=32.

11. Sep 21, 2011

### dodo

Oops, sorry about that, I missed it.

The idea is that $6 \cdot 4 - 0 + 8 = 32$; and he mentioned reducing 32 modulo $p$ at some point.

12. Sep 21, 2011

### dodo

PF's "database error" gave me time to think of my sins.

The required "modulo" appears to correspond to the "truncated division" implementation (ramsey2879 should confirm with the examples suggested by D.H.), so the $b_n$ rule could succinctly be expressed as
$$b_n = \left| 6b_{n-1} - b_{n-2} + 8 \right| \text{ mod } p \qquad \text{for } n > 1$$Also, I messed the termination conditions: any of 0 or 4 should terminate the sequence. I apologize for my mess-up.

Something I find interesting is that this sequence tends to produce palindromes (if left to continue appropriately): if c = 6b-a+8, then 6b-c+8 = a. Hence the sequences for p=5 (0 4 2 1 2 4 0), p=9 (0 4 5 7 0 1 5 1 0 7 5 4 0) or p=27 (0 4 5 7 18 1 4 4 1 10 13 22 19 19 22 13 10 1 4 4 1 ...). So, when by some chance the "center" of the palindrome gets produced (such as, for p=5, the numbers 2,1 being followed by 2) the rest of the behavior follows.

Last edited: Sep 21, 2011
13. Sep 21, 2011

### ramsey2879

I take the mod as -2 = 5*-1 + 3 = 3 mod 5 and -7 = 5*-2+ 3 = 3 mod 5. Sorry that I led everyone on a goose chase. I was looking at the series S_n = 6*S_(n-1) - S_(n-2) - K where S_0 = 2*P^2, S_1 = (P+2)^2 and K = 2*P^2 + 8P - 8. Such series give a perfect square for odd n, and twice a perfect square for even n. I was looking at this series mod P and chose to start the test with S_1 and S_2 instead of S_0 and S_1. I just didn't look far enough before posting it. Turns out to be a rather trival test with many false hits.