Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

New Test for Primes

  1. Sep 20, 2011 #1
    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. jcsd
  3. Sep 20, 2011 #2
    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;
    }
     
     
  4. Sep 20, 2011 #3

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Unless I coded your algorithm wrong, 5, 7, and 13 are "not Prime". 15 is particularly troublesome. It cycles and never returns.
     
  5. Sep 20, 2011 #4
    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
  6. Sep 21, 2011 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  7. Sep 21, 2011 #6
    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
  8. Sep 21, 2011 #7

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    RamaWolf:
    I edited your post to insert the code in code blocks.
     
  9. Sep 21, 2011 #8

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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 [itex]a[/itex] and [itex]b[/itex], there are three common implementations of integer division for negative numbers and hence three ways to implement [itex]a \mod b[/itex] are
    • Truncated division, [itex]q=\mbox{sgn}(a/b)\lfloor{|a/b|}\rfloor[/itex]
    • Floored division, [itex]q=\lfloor{a/b}\rfloor[/itex]
    • Euclidean algorithm, [itex]q = \lfloor{a/b}\rfloor\,\text{if $b$ is positive},\, \lceil{a/b}\rceil\,\text{if $b$ is negative}[/itex].

    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
  10. Sep 21, 2011 #9
    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 [itex]a \text{ mod } b[/itex] for negative [itex]a[/itex] and positive [itex]b[/itex] involves taking a quotient [itex]q=\lceil{a/b}\rceil[/itex], and then taking the positive remainder from that.

    A bit more on this "translation": I believe the idea is to explore the recurrence sequence
    [tex]
    \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*}
    [/tex]
    with "mod" defined as above, and assert two things:
    • that the sequence will always reach a [itex]b_n = 4[/itex], for some [itex]n > 1[/itex]; and
    • that, at that final point, the next value [itex]b_{n+1}[/itex] should say something about the primality of [itex]p[/itex], depending on whether it is 0 or not.
     
    Last edited: Sep 21, 2011
  11. Sep 21, 2011 #10

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  12. Sep 21, 2011 #11
    Oops, sorry about that, I missed it.

    The idea is that [itex]6 \cdot 4 - 0 + 8 = 32[/itex]; and he mentioned reducing 32 modulo [itex]p[/itex] at some point.
     
  13. Sep 21, 2011 #12
    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 [itex]b_n[/itex] rule could succinctly be expressed as
    [tex]b_n = \left| 6b_{n-1} - b_{n-2} + 8 \right| \text{ mod } p \qquad \text{for } n > 1[/tex]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
  14. Sep 21, 2011 #13
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: New Test for Primes
  1. Test for Primes (Replies: 5)

  2. A new prime sieve (Replies: 23)

  3. New property of primes (Replies: 11)

Loading...