Fibonacci Conjecture

January 23, 2015

We test primality using the Miller-Rabin algorithm:

from random import randint

def isPrime(n, k=5): # miller-rabin
    if n < 2: return False
    for p in [2,3,5,7,11,13,17,19,23,29]:
        if n % p == 0: return n == p
    s, d = 0, n-1
    while d % 2 == 0:
        s, d = s+1, d/2
    for i in range(k):
        x = pow(randint(2, n-1), d, n)
        if x == 1 or x == n-1: continue
        for r in range(1, s):
            x = (x * x) % n
            if x == 1: return False
            if x == n-1: break
        else: return False
    return True

Then we generate the fibonacci sequence item by item, testing each member of the sequence for the conjecture:

fminus2, fminus1, f, n = 0, 1, 1, 1

while not isPrime(f*f+41):
    fminus2 = fminus1
    fminus1 = f
    f = fminus2 + fminus1
    n = n + 1

print n

It takes a while, but when n = 12586 the conjecture is disproved; Fn =

2437420528658316261009349390793966957742064\
3628861129205119104129367296544863664132318\
7350629550946523694153755521722137479950927\
2904723884962366758282082558958533077607016\
4703846370983386287796589758104627824352090\
5662005007112216576623475679256710071871042\
3501925305429172597994769639007117036154468\
7180679967509632642871862665093652981386467\
8910317854243133922877435406205076602327076\
9741103525885355233426517035556242651050139\
7776152157485442589142262270805545603989018\
2738554122228622158431371645352398507835723\
0385583847730548224182907279173376294450080\
9559053247797188570862253302394816309497146\
6878325147926036684128681457928096551878450\
9048663514751789277765677734737548105702983\
9734854764440251783035033215144047874666733\
6848868926251340058764754077781140566043315\
8701933074493040543009488664637360050636904\
2928079603209789838364413285025609380384265\
6795053352943252616137226071900435738575737\
1979845493254607828392109996976472074994766\
9033598594913864908202612667104449679242977\
8610516507362889175957975232663636222152077\
4284526382848518239624979685302202912236641\
6943769232769303904917019647139581084704832\
7272516266180237248581730637609553420348612\
0484912018032012452608038735409013648590994\
8240242575154900347260104409588725662982761\
8930795229966774742603711212498750506258076\
3014931449402618392241302765309360591836332\
5458917719554093037261461679173796989091018\
2435816239415372148826244578310525764913283\
5242405725134042227992345138785534218377273\
5053838856017355194609598851478158802143512\
7175941347773542411307602896674709526451628\
6476071607991857431689522947614987960169330\
6722813421495472939532252545388730790498301\
2251572189695241349427758764490786113582769\
8645909666431556968864724496839492828557311\
9170002013318196219345226290957660638411642\
0016581274984591009084728165483905358516182\
0297135028779916414354206794185844039364018\
8608957647160096027031880341964822877335354\
5751715205632025400536873014390149732416863\
9085890424786551710413554658241864854000794\
6745670650479244297452105370763155766676763\
7318438261153992762039335049099708136846624\
8277001806713678125062905001779238666279561\
6632647722206547535282413463861123144939517\
6474406575548095847232978261553672514077110\
1662200616963869051516130934571518303860888\
9635879329162191473644658218460874561795754\
7161483044610603455086191314143678151570447\
9169448264328530870952452811943101857223733\
6743709285893930610721261923392743649444251\
2593507974839519719984251378323935971154303\
0401762641878184079758301800088653799694925\
1691510246396397638712811252669104365214937\
6779473254356292498767183110896869322621345\
2857548409354754231404289782181584228127633\
62455056

I’m writing in Python instead of Scheme because I happened to have a Python window open, with an isPrime function already loaded, when I saw the conjecture. That takes a while to run because the numbers quickly become large.

This is a good example of a conjecture that seems to be true; it takes a long time to find a counter-example (with 2630 digits!) so it fools you into thinking that it might be correct. There are other famous conjectures — the Collatz conjecture, the twin-primes conjecture, the conjecture that all perfect numbers are even, the Riemann hypothesis — for which there is strong empirical evidence but no proof.

You can run the program at http://programmingpraxis.codepad.org/Q4e8Xt8V.

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: