Problem Twenty Five

Here’s problem twenty five:

Question: What is the first term in the Fibonacci sequence to contain 1000 digits?

This was pretty simple, all we need to do is generate Fibonacci terms and check the length of each one. We also need a counter to keep track of what term we’re on.

a = b = n = 1
counter = 2

while len(str(n)) != 1000:
	counter += 1
	n = a + b
	a, b = b, n

print(counter)

a, b, and n are variables used to generate the Fibonacci sequence. Since Project Euler defines the first term of the Fibonacci sequence as 1 rather than 0, we initialize the counter to 2, since the first term we calculate (2) will be the 3rd term. The rest is self-explanatory.

Answer: 4782

Problem Two

Ok, let’s move on to problem two.

Question: By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Basically, we need to sum all the even fibonacci terms under four million. Let’s look holistically at how we would solve this problem. First, we need to have a function, or at least a procedure, to get the fibonacci terms. Then we need to do a test to check that it’s even, and if true, we add that term into some variable.

I did a quick google search to find some python code for the fibonacci sequence, and there were already a ton of solutions. However, it was pretty hard to intuitively understand (grok?) this code at first, even the simple ones, so I decided to try my hand at writing it myself. It took me about 30 minutes to come up with a clunky version of it, but I did pare it down by starting at one, instead of zero as I originally planned.

(Note: The projecteuler website states that the fibonacci sequence is “1, 2, 3, 5, 8, 13…”, but it technically is “0, 1, 1, 3, 5, 8…”. This does not affect our result though since we are only dealing with even numbers.)

From then on it was a quick manipulation to check the even-odd-ness (is there a word for that?) of the term, and then adding it into a sum variable. Here’s what the code looks like:

a = 0 
b = 1
total = 0

while b < 4000000:

	if b % 2 == 0:
		total += b

	a, b = b, b+a

print(total)

This code is pretty straightforward, but it might be a little hard to grasp at first. If you’re confused, think about it this way. Lines 1-3 initialize the variables. It’s important for a to equal zero and b to equal one. Lines 5 & 8 are essentially the code for the fibonacci sequence. I’ll explain line 8 in more detail later on, but now just take my word for it. Lines 6 & 7 check to see if the current term is even and adds it into total. Line 10 prints that variable.

So let’s examine line 8. This is the inner workings of the fibonacci sequence. Originally this code was three lines long, and looked like this:

c = b
b += a
a = c

Keep in mind that this is all line 8 (in the while loop), in its unshortened form. We are basically doing two things in the these lines: adding the previous term to the current term, and setting the current term to become the previous term in the next iteration. However, this requires a third variable c to work, to temporarily store the current value. I found a more efficient way of doing this in my earlier google searches, which looks like line 8 above.

Also duplicated here:

a, b = b, b+a

This essentially sets the two variables in one line, without the need of a third variable to temporarily store a value.

So that’s the code, but how would you solve it mathematically? Credit goes to RudyPenteado in the forum for coming up with this very clever solution. He realized that every third term of the fibonacci sequence is even. Additionally, phi, or φ, is the approximate ratio between consecutive terms in the fibonacci sequence. This fact can be manipulated so that the ratio between consequtive even terms is φ3, or 4.236068. The first even term is 2, so multiply that by 4.236068 and you get, after rounding to the nearest integer, 8. You repeat this to find the values up to four million (there’s less than ten terms), and add them with a calculator.

Answer: 4613732