CoolManGame's blog

By CoolManGame, history, 13 months ago, In English

SAD NEWS: beepbeepboop has found 219781 to be a counter example :(( I was too excited that I forgot to check for big numbers. In fact there are quite many counter examples above 1e5. This conjecture is therefore proven to be false.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I unexpectedly found a simple primality condition when browsing the prime number sequence on OEIS. I thought it would be nice to share it here since I haven't seen it shared anywhere else. It's also easier to remember than the Miller-Rabin test. Here's some pseudocode to describe the primality test:

isPrime(N):
 if N <= 10: return N in [2, 3, 5, 7]
 return (Fib(N) % N == 1 or Fib(N) % N == N-1) and (2**(N-1) % N) == 1

(Note: (Fib(N) % N) and (2**(N-1) % N) can be evaluated in O(logn))

This does work, and I've gotten AC on https://www.spoj.com/problems/PON/ with it.

You can find this conjecture on https://oeis.org/A000040 where it said "Conjecture: Sequence = {5 and n <> 5| ( Fibonacci(n) mod n = 1 or Fibonacci(n) mod n = n — 1) and 2^(n-1) mod n = 1}. — Gary Detlefs, May 25 2014". It's a conjecture, but conjectures are true in CP am I right lol.

I haven't found a name for it, nor have I seen it shared anywhere else. Though, if it's already known with a published name (I'm not the best googler lol), do let me know through the comments or DM.

  • Vote: I like it
  • +127
  • Vote: I do not like it

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by CoolManGame (previous revision, new revision, compare).

»
13 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Incredible. It also seems to be faster than Miller-Rabin.

»
13 months ago, # |
  Vote: I like it +51 Vote: I do not like it

imagine inventing O(log n) primality test and publishing it only on oeis

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems to be a heuristic primality test proposed by Selfridge.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did see it, but it seems like a different but similar test. The one I posted doesn't require p = 2 or -2 (mod 5)

»
13 months ago, # |
  Vote: I like it +157 Vote: I do not like it

Sadly, it fails on $$$219781$$$ giving a false positive. $$$fib(219781) = 1$$$ $$$(\mod 219781)$$$ and $$$2^{219780} = 1$$$ $$$(\mod 219781)$$$ but $$$219781$$$ is a composite number equal to $$$271 \times 811$$$.

You can check the calculation on Wolfram.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +99 Vote: I do not like it

    Man disproved a conjecture with just a for loop 💀

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    OMG This is heartbreaking !!! :((( I was too excited after the AC on SPOJ, shouldve tried it with "Count Primes" on Leetcode. Later I'll update the post, and try the conjecture given below (there are two, though most likely it also fails). Sorry for this sadness :(( Thanks for pointing out the counter example

    • »
      »
      »
      13 months ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      Bro if we do find one and it is posted publicly, then it is actually BAD NEWS! RSA Encyption wouldn't work and we would all be hacked... :(

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Primality tests do not break RSA, since we do not actually find the prime factors of the number.

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Looks like according to the link orz sent, you just won $620!

    Edit: Oops, nevermind :(

    • »
      »
      »
      13 months ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      unfortunately to claim the prize money the possible prime $$$p$$$ has to be equal to $$$\pm 2 \pmod{5}$$$ while $$$219781 = 1 \pmod{5}$$$ Source

      Edit: the hyperlink seems to not be working for me atleast, https://en.m.wikipedia.org/wiki/John_Selfridge#Selfridge's_conjecture_about_primality_testing

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Challenge accepted! $$$22711873$$$ is one counterexample. It checks all the boxes:

        • $$$22711873 \equiv -2$$$ $$$\pmod{5}$$$,
        • $$$fib(22711873) \equiv 1$$$ $$$\pmod{22711873}$$$,
        • $$$2^{22711873 - 1} \equiv 1$$$ $$$\pmod{22711873}$$$.

        However, $$$22711873$$$ is a composite number equal to $$$59 \times 349 \times 1103$$$. Calculations on Wolfram.

        • »
          »
          »
          »
          »
          13 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The wikipedia article and the blog seem to have different conditions for the primality test.

          The blog's condition is that:

          $$$fib(n) = \pm 1 \mod n \newline$$$ $$$2^{n-1} \equiv 1 \mod n \newline$$$

          While the PSW conjecture in the wikipedia article is that:

          $$$n \equiv \pm 2 \pmod{5}\newline$$$ $$$fib(n+1) = 0\mod n \newline$$$ $$$2^{n-1} \equiv 1 \mod n \newline$$$

          Your counterexample works for condition in the blog, but does not work for the actual PSW conjecture. Wolfram calculations: link

      • »
        »
        »
        »
        13 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        That link gives a slightly different test. Note that it requires $$$p \equiv \pm 2 \pmod 5$$$ and $$$F_{p+1} \equiv 0 \pmod p$$$

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What about numbers such that $$$n \equiv \pm 1 \mod 5$$$

»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by CoolManGame (previous revision, new revision, compare).