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

Project Euler Problem 1

Project Euler (http://projecteuler.net) is an interesting site for folks like me who like to explore math on our own terms. It’s basically a listing of a set of math problems. Each problem explains the basic concept that you’ll be using and then challenges you to push yourself a bit further. The problems are listed in order of complexity and some problems give you tools that will help you to solve problems later in the list. You can register a login at the site for free and that will let you track your progress and compare it to other users.

The first problem is stated as follows:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Obviously, doing this by hand is awkward and prone to error not to mention boring so why not have a computer do it? Unfortunately computers are quite stupid so we’ll have to re-word the problem so that even the poor dumb thing can understand.

Let SUM equal our final answer and set it to 23 to start.

Let CURR equal the number we’re looking at now and start that at 11.
Does CURR divide evenly by 3?
Yes? – Add to SUM
No? – Keep going
Does CURR divide evenly by 5?
Yes? – Add to SUM
No? – Keep going
Add 1 to CURR
Keep checking.

Hmmmm…we can make this cleaner.  And by cleaner, I mean dumber.

Let SUM equal our final answer and set it to 23 to start.
Let CURR equal the number we’re looking at now and start that at 11.
Does CURR divide evenly by 3 OR by 5?
then
add to SUM
Add 1 to CURR
Is CURR equal to 1000?
then stop checking.
Test new value of CURR

So is there a point to this problem? According to the Project Euler About page:

The problems range in difficulty and for many the experience is inductive chain learning. That is, by solving one problem it will expose you to a new concept that allows you to undertake a previously inaccessible problem. So the determined participant will slowly but surely work his/her way through every problem.

So it looks like the thinking we employ here might pay off down the line. But that’s not good enough for me. What’s so special about 3 and 5?

Well, 3 is one of those ‘magical numbers’ that keep popping up wherever you look — 3 wishes, 3 Wise Men, 3 Blind Mice, etc., etc. 5 is one of those as well – five fingers on the human hand, 5 limbs on a starfish. (And don’t even get me started on the sinister significance of the number 23 )

But this is all numerological horse-hockey. I’m a man of SCIENCE!

Okay, starting again. Both 3 and 5 are primes. We live in 3 dimensions (arguably 4, though.) Also 3 is the only prime followed by a square as well as the only number that is the sum of all the natural numbers that are less than it. There are 5 Platonic Solids. 5 is also a palindromic prime as well as a twin prime.

Okay, nothing springs out to my attention here but clearly there are a lot of interesting mathematical properties for both 3 and 5 (and I included links to some sites where you can explore some more on your own). So let’s go ahead and solve the problem.

First we translate our pseudo-code to something that the computer actually understands. I have a number of choices as far as this goes. I’m quite comfortable with the bash scripting language and I’m doing this on a Mac, so here’s what I’ve got:

#!/bin/bash 
# Solution code for Project Euler problem 1
# Problem: If we list all the natural numbers below 10 that are multiples of 3 or 5, 
# we get 3, 5, 6 and 9. The sum of these multiples is 23.

# Find the sum of all the multiples of 3 or 5 below 1000.

# Set up our variables
SUM=23  
CURR=11

#Check to see if CURR is less than 1000. If it is, then quit.
while [ "$CURR" -lt 1000 ]
do
	if   !(( "$CURR" % 3 )) || !(( "$CURR" % 5 )) 
	then
		#echo $CURR is divisible by 3 or 5 # a little test code
		let "SUM+=$CURR"
	else
		# Do nothing
		echo > /dev/null
	fi
	# add 1 to the value of CURR
	let "CURR += 1"
done
echo The sum of all multiples of 3 or 5 that are below 1000 is $SUM.

The output I got when I ran this was:

The sum of all multiples of 3 or 5 that are below 1000 is 233158.

So is there anything special about this number? Let’s plug it into Wolfram Alpha (kind of like Google but for math) and see:

In binary (base 2), it’s

111000111011000110

This is kind of interesting. If we split this binary number in half, we get

111000111

and

011000110

both of which are palindromes. (They read the same backwards and forwards.) Recall 5 is also a palindrome. The first binary chunk (111000111) converts to 455 in decimal and is divisible by 5 but not 3. The second half (011000110) converts to 198 in decimal and is divisible by 3 but not 5. Okay, color me reasonably impressed.

It’s the product of two primes, 2 and 116579.

In fact, these are the only two factors of this number, despite it being an even number.

I could probably do some graphing as well but at this point I’m reasonably convinced that there’s something interesting going on here and it may come in handy as I continue down the list of Project Euler problems.

Did you find anything interesting in this exercise? Have you participated in Project Euler? Let me know in the comments!