Fibonacci conjecture
Another one for the " using computers to investigate trivial mathematics" file...
I had another meeting with my STEP student today, who showed me the following problem: find a simple expression for the sum of the squares of the nth and (n-1)st Fibonacci numbers. In other words, what is Fn2 + Fn-12? We're taking the zeroth Fibonacci number to be 0, and the first to be 1.
Looking at the first few, I noticed that the terms in question were themselves Fibonacci numbers: in fact, Fn2 + Fn-12 was F2n-1. I hacked around for a bit, but couldn't see a proof; so, I looked for a bit more supporting evidence.
fibs = 0:1:zipWith (+) fibs (tail fibs)
evens [] = []
evens (x:y:xs) = x:evens xs
evens (x:[]) = []
odds [] = []
odds (x:xs) = evens xs
sumsquares = zipWith (+) fibSquares (tail fibSquares)
where fibSquares = map (\x -> x * x) fibs
*Main> and $ zipWith (==) (take 1000 sumsquares) (take 1000 $ odds fibs)
True
*Main> and $ zipWith (==) (take 10000 sumsquares) (take 10000 $ odds fibs)
True
*Main> and $ zipWith (==) (take 100000 sumsquares) (take 100000 $ odds fibs)[At this point, the machine hung: I don't advise you to try this!)
I still can't see a proof, but no doubt one will occur to me in the morning...
In other news, I've been playing around a bit more with the Catalan numbers - in fact, I briefly thought they might have something to do with my actual research, and got very excited, but on further reflection I don't think they're very helpful. But it seems likely that the reason the "naive" J code hung didn't have all that much to do with the naiveté of the algorithm - using the same algorithm, and on the same machine, MIT Scheme (interpreted) was able to calculate the 100,000th Catalan number in around 100s, with no paging or machine-locking, and Python was able to calculate it in under 20s! It seems to me that J is using either a poor bignum implementation, or (more likely) a very poor implementation of the binomial coefficients - I discussed this with my father (we're that kind of family), and he suggested that it's probably written recursively, and thus consumes vast amounts of stack space. Easy enough to fix, if only the J interpreter weren't closed-source...
I had another meeting with my STEP student today, who showed me the following problem: find a simple expression for the sum of the squares of the nth and (n-1)st Fibonacci numbers. In other words, what is Fn2 + Fn-12? We're taking the zeroth Fibonacci number to be 0, and the first to be 1.
Looking at the first few, I noticed that the terms in question were themselves Fibonacci numbers: in fact, Fn2 + Fn-12 was F2n-1. I hacked around for a bit, but couldn't see a proof; so, I looked for a bit more supporting evidence.
fibs = 0:1:zipWith (+) fibs (tail fibs)
evens [] = []
evens (x:y:xs) = x:evens xs
evens (x:[]) = []
odds [] = []
odds (x:xs) = evens xs
sumsquares = zipWith (+) fibSquares (tail fibSquares)
where fibSquares = map (\x -> x * x) fibs
*Main> and $ zipWith (==) (take 1000 sumsquares) (take 1000 $ odds fibs)
True
*Main> and $ zipWith (==) (take 10000 sumsquares) (take 10000 $ odds fibs)
True
*Main> and $ zipWith (==) (take 100000 sumsquares) (take 100000 $ odds fibs)[At this point, the machine hung: I don't advise you to try this!)
I still can't see a proof, but no doubt one will occur to me in the morning...
In other news, I've been playing around a bit more with the Catalan numbers - in fact, I briefly thought they might have something to do with my actual research, and got very excited, but on further reflection I don't think they're very helpful. But it seems likely that the reason the "naive" J code hung didn't have all that much to do with the naiveté of the algorithm - using the same algorithm, and on the same machine, MIT Scheme (interpreted) was able to calculate the 100,000th Catalan number in around 100s, with no paging or machine-locking, and Python was able to calculate it in under 20s! It seems to me that J is using either a poor bignum implementation, or (more likely) a very poor implementation of the binomial coefficients - I discussed this with my father (we're that kind of family), and he suggested that it's probably written recursively, and thus consumes vast amounts of stack space. Easy enough to fix, if only the J interpreter weren't closed-source...