Test Primes: Find an Exception for P > 3? - Ken Ramsey

[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

 

[TylerH]

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

#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;
}

 

[D H]

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

 

[ramsey2879]

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

I don't know C++ so I can't 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.

 

[D H]

I don't know C++ so I can't tell where the problem is.

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

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

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.

 

[RamaWolf]

My coding:

      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.

 

[D H]

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

 

[D H]

n = 7
32|0
n = 7 is compo

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 2^N arithmetic: A+B → A+B mod 2^N. This will lead to infinite loops.

 

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

 

[D H]

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

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

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.

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.

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.

Except ramsey started with b₀=4, b₁=32.

 

[dodo]

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

Oops, sorry about that, I missed it.

Except ramsey started with b₀=4, b₁=32.

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

 

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

 

[ramsey2879]

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.

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.