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.

My question is:

How this code can 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