The sequence of Fibonacci numbers is defined as F1 = 1, Fn = Fn−2 + Fn−1. It has been conjectured that for any Fibonacci number F, F2 + 41 is composite.
... [T]ask is to either prove the conjecture to be true or find a counter-example that demonstrates it is false.
Here is my working code for this problem - although I don't know the conjecture is either true or false in general.
I tested it for first 107 natural numbers, also for first 1000 Fibonacci numbers - and it seems conjecture is true. but I takes a lot of time (80-90 seconds) to spit out a result.
As you see in last three functions, I have 3 method to test conjecture.
First one (
fibonacci_conjecture) generates a sequence of Fib2+41s and returns result of primality test.
Second one is similar to first, but it first checks if numbers in a given range are Fibonacci numbers or not.
Third one seems more optimal. As we know from definition, for a given Fibonacci number f, 5f2+4 or 5f2-4 is perfect square. If we add 41 to both of them we'll have 5f2+45 or 5f2+37. The first one is always divisible by 5, so there's no need to check these values.
How can this code be written in an optimal way, for faster results? Or, which techniques should I follow (either within the code or within the math)?
import math def is_perfect_square(x): return int(math.sqrt(x)) == math.sqrt(x) def is_fibo(x): c = 5*x*x return is_perfect_square(c+4) or is_perfect_square(c-4) def is_prime(x): c = int(math.sqrt(x))+2 if (x%2==0 and x!=2) or is_perfect_square(x): return False else: for i in range(2, c): if x%i==0: return False return True def minus_four(fib): if is_fibo(fib) and fib>0: return is_perfect_square(5*fib*fib-4) def fibo(x): if x<2: return 1 else: return fibo(x-1)+fibo(x-2) def fibonacci_conjecture(end): return (True not in map(is_prime, [fibo(i)*fibo(i)+41 for i in range(end+1)])) def second_way(end): return (True not in map(is_prime, [i**2+41 for i in range(end+1) if is_fibo(i)])) def third_way(end): return (True not in map(is_prime, [fibo(i)*fibo(i)+41 for i in range(end+1) if minus_four(i)]))
There is also a brute-force like implementation. that checks if 5x2+37 is prime, then checks if that number is a Fibonacci number.
from fibonacci_conjecture import * # functions above import time from sys import argv script, start, end = argv _list =  start_time = time.time() for i in range(int(start), int(end)): if is_prime(5*i*i+37) and is_fibo(5*i*i+37): _list.append(i) print _list print time.time() - start_time
Results calling the last one from Terminal:
$ python timings.py 0 1000  0.0163550376892 $ python timings.py 1000 2000  0.0392298698425 $ python timings.py 2000 12000  1.66012907028 $ python timings.py 12000 42000  35.4742548466 $ python timings.py 42000 43000  2.01177597046 $ python timings.py 43000 48000  11.1937119961