Fibonacci Conjecture

January 23, 2015

The sequence of Fibonacci numbers is defined as F0 = 0, F1 = 1, Fn = Fn−2 + Fn−1. It has been conjectured that for any Fibonacci number F, F2 + 41 is composite.

Your task is to either prove the conjecture to be true or find a counter-example that demonstrates it is false (hint: this is not a blog about proving math theorems). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisement

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
7 Comments »

7 Responses to “Fibonacci Conjecture”

  1. Brett Warren said
    January 23, 2015 at 10:03 AM

    Quick and dirty brute-force method in python. Copy and pasted the isprime function, made a fibb generator, and started testing for anomalies.
    Detected 2^2 + 41 as the odd one out:

    def isprime(number):
	from math import ceil
	
	if number <= 1:
		return False
	elif number == 2:
		return True
	elif number % 2:
		return False
	else:
		for n in range(3, number**0.5, 2):
			if not number % n:
				return True
		return False

def fibb_gen():
	(n, m) = (1, 1)
	while True:
		yield (n + m)
		(n, m) = (m, (n + m))

if __name__ == "__main__":
	a = fibb_gen()
	for n in a:
		if n % 2:
			continue
		if not isprime(n**2 + 41):
			print(n, n**2 + 41)
			break
  2. Brett Warren said
    January 23, 2015 at 10:05 AM

    NEVER MIND, IGNORE MY PREVIOUS COMMENT, NOT THE SOLUTION.

    I am truly a poop.

  3. sbmassey said
    January 23, 2015 at 2:09 PM

    Fails for F_0, as 41 is prime.

  4. Jan Van lent said
    January 25, 2015 at 3:18 PM

    I think that according to the definition in the question the value of n in the model solution is off by 2.
    For that definition, the initialisation line would be

    fminus2, fminus1, f, n = 0, 1, 1, 2
  5. ironiya said
    April 20, 2015 at 9:52 PM

    i took 1 as first fibonacci number and run my code in several ranges as my machine lets me.
    it seems conjecture is true. though if it is not, i will not be surprised.

    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)]))

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: