Project Euler #2 – Fun With Fibonacci

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Do you remember those standardized tests you used to take in school, the ones that were supposed to tell you what kinds of things you were meant to do for a living? (Of course, that’s not how they were presented but effectively that’s what these tests were about, slotting you into a particular career path. For the record, I scored high on math, verbal, abstract visualization, etc., but absolutely sucked rocks on ‘clerical speed and accuracy’. Well, there goes my dream of working for the IRS…. [NOTE TO THE IRS: You folks are doing the Lord’s work and I thank you for your service. Please don’t audit me.])

Anyway, at some point in those tests you’d get a question like this:

What is the next number in the following sequence?:
1,2,3,4,5…?

That’s sort of the story behind the Fibonacci sequence, kind of. Originally described by Indian scholars, this number sequence really hit popular culture (as it were) in the 13th century when Leonardo Fibonacci published a math book that introduced them to good, God-fearing, Western European white folk. (Otherwise it would be known as the Aryabhata sequence or the Brahmagupta sequence or the Bhaskara sequence or other foreign-sounding names like that when we have a perfectly good down-home name like Fibonacci that we already know how to pronounce.)

The cool thing about Fibonacci numbers is that once you find out about them, you start seeing them everywhere – trees, artichokes, pineapples, honeybees, even in the growth pattern of mollusc shells. They have tons of practical uses as well – generating random numbers, searching, sorting, data compression and encryption. Some stock traders even use them to predict future share prices.

In fact, if you’ve ever been in a gym that uses weight circuit machines you’ve probably seen ones where the cams (the bit that the pulley belt runs over) aren’t circular but rather look kind of like a dented oval or a kidney bean. This shape is based on the Fibonacci sequence and is specially designed to distribute the weight so that your muscles are putting out a consistent level of effort. In other words, more weight is applied where your muscles are stronger.

At any rate, we’re back again with more from Project Euler. We’re moving on to problem 2, which deals with even-valued Fibonacci numbers. Now that we know what’s special about Fibonacci numbers, what’s so special about the even ones? Well, if we write out the sequence for a bit:

0 1 1 2 3 5 8 13 21 34 55 89 144

We notice that a pattern shows up pretty quickly:

odd odd even odd odd even odd odd even….

(NOTE: 0 is technically neither odd nor even.)

So every even Fibonacci number is two Fibonacci numbers away from every other even Fibonacci number. Okay, what about the sums? It turns out that the sum of even valued terms up to any specified number (like 4,000,000 in the problem at the start of this post) will always be 1 more than the sum of the odd valued terms up to that same number. (At this point, all the math nerds are holding their cigarette lighters up in the air, or more probably, smartphones with a photo of a cigarette lighter on the screen.)

Alright, time for the rubber to meet the road. Here’s how we’re going to solve this, pseudo-code style:

Let A = 1
Let B = 2
Let SUM = 2
{Keep doing this next bit until I tell you to stop}
Let X = A + B
Let A = B
Let B = X
Is B greater then 4000000?
Yes: stop and print “The sum of the even Fibonacci numbers less than 4000000 is SUM”
No: keep going
Is X even?
Yes: Let SUM = SUM + X
No: keep going

That seems pretty straightforward. Let’s do it for real:

#!/bin/bash
# Euler02 - Based on problem 2 at Project Euler
# Find the sum of even Fibonacci numbers less then 4,000,000
#
# Pseudocode:
# Let A = 1
# Let B = 2
# Let SUM = 2
# {Keep doing this next bit until I tell you to stop}
# Let X = A + B
# Let A = B
# Let B = X
# Is B greater then 4000000?
# 	Yes: stop and print “The sum of the even Fibonacci numbers less than 4000000 is SUM”
# 	No: keep going
# Is X even?
# 	Yes: Let SUM = SUM + X
# 	No: keep going

A=1
B=2
SUM=2
#X=0

while true
do
{
	let "X=A+B"
	A=$B
	B=$X
	if [ "$B" -gt 4000000 ]
	then
		break
	fi

	# is X even?
	if !(( "$X" % 2 ))
	then
		let "SUM+=X"
	fi	
}
done

echo The sum of all even Fibonacci numbers less than 4,000,000 is $SUM.

The output of this code is:

The sum of all even Fibonacci numbers less than 4,000,000 is 4613732.

Now it just takes a quick tweak to add up all of the odd Fibonacci numbers and when we do we get the result:

The sum of all odd Fibonacci numbers less than 4,000,000 is 4613731.

So it looks like our rule about Fibonacci sums works!

Consider this an open thread.

Advertisements

Leave a Reply

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

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 )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s