True O(logn) (for 64bit numbers(Disproven) True O(logn) and deterministic primality test using Fibonacci numbers
Difference between en3 and en4, changed 335 character(s)
SAD NEWS: [user:beepbeepboop,2023-09-22] 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:↵

 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 with it.↵

You can find this conjecture on where it said "Conjecture: Sequence = {5 and n <> 5| ( Fibonacci(n) mod n = 1 or Fibonacci(n) mod n = n &mdash; 1) and 2^(n-1) mod n = 1}. &mdash; 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.


  Rev. Lang. By When Δ Comment
en4 English CoolManGame 2023-09-22 13:37:08 335 Making it known that the conjecture is false
en3 English CoolManGame 2023-09-21 20:37:14 0 (published)
en2 English CoolManGame 2023-09-21 20:36:00 6 Reformatted code block (saved to drafts)
en1 English CoolManGame 2023-09-21 20:33:52 1184 Initial revision (published)