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.
Auto comment: topic has been updated by CoolManGame (previous revision, new revision, compare).
Incredible. It also seems to be faster than Miller-Rabin.
imagine inventing O(log n) primality test and publishing it only on oeis
It seems to be a heuristic primality test proposed by Selfridge.
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)
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.
Man disproved a conjecture with just a for loop 💀
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
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... :(
Primality tests do not break RSA, since we do not actually find the prime factors of the number.
Looks like according to the link orz sent, you just won $620!
Edit: Oops, nevermind :(
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
Challenge accepted! $$$22711873$$$ is one counterexample. It checks all the boxes:
However, $$$22711873$$$ is a composite number equal to $$$59 \times 349 \times 1103$$$. Calculations on Wolfram.
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
Oops, you're right.
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$$$
What about numbers such that $$$n \equiv \pm 1 \mod 5$$$
Everything is OK
Auto comment: topic has been updated by CoolManGame (previous revision, new revision, compare).