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.
↵
~~~~~↵
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.
