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, F² + 41 is composite.

... [T]ask is to either prove the conjecture to be true or find a counter-example that demonstrates it is false.

(source)

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 10⁷ 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 Fib²+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, 5f²+4 or 5f²-4 is perfect square. If we add 41 to both of them we'll have 5f²+45 or 5f²+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 5x²+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