NumPy Project Euler Problem 2

This entry is part 2 of 9 in the series NumPy Project Euler

Project Euler Problem 2 is definitely harder than Problem 1. This one requires reading the Fibonacci numbers Wikipedia article.

I read that the Project Euler problems are some sort of katas. Katas are what martial artist call exercises, preparing you for real-life fighting situations. For instance, imagine that your house is on fire and that your family is surrounded by heavily armed thugs. What do you do? In this case your secret weapon is NumPy, which is like the Dim Mak death touch. If you master that like me, then you don’t even need to bother with katas.

1. Calculate the golden ratio

When the bad ninja guys are walking towards you, the first thing to do, is calculate the golden ratio, also called the golden section. This part of the kata is called Moro Ashi Dachi.

1
2
phi = (1 + numpy.sqrt(5))/2
print "Phi", phi

This prints the golden mean.

1
Phi 1.61803398875

2. Find the index below 4 million

Next in the kata we need to find the index below 4 million. A formula for this is given in the Wikipedia page. All we need to do is convert log bases. We don’t need to round the result down to the closest integer. This is automatically done for us in the next step of the kata.

1
2
n = numpy.log(4 * 10 ** 6 * numpy.sqrt(5) + 0.5)/numpy.log(phi)
print n

We get the result 33.2629480359. You can double check this yourself from the Wikipedia article.

3. Create an array of 1-n

No, you say. Not the arange function again. We know about it already, when are we going to learn about the Jyutping. Patience, let’s first master the basics.

1
n = numpy.arange(1, n)

4. Compute Fibonacci numbers

There is a convenient formula we can use to calculate the Fibonacci numbers. We will need the golden ratio and the array from the previous step in the kata as input parameters. Print the first 9 Fibonaci numbers to check the result. I could have made an unit test instead of a print statement. This variation of the kata is left as an exercise for the reader.

1
2
fib = (phi**n - (-1/phi)**n)/numpy.sqrt(5)
print "First 9 Fibonacci Numbers", fib[:9]

The output is below. You can plug this right into an unit test, if you want.

1
First 9 Fibonacci Numbers [  1.   1.   2.   3.   5.   8.  13.  21.  34.]

5. Convert to integers

This step is optional. I think it’s nice to have an integer result at the end. It’s like the difference between Mawashi Geri and Mawashi Geri Koshi. The effect is almost the same, but one feels better than the other. OK, I actually wanted to show you the astype function.

1
2
fib = fib.astype(int)
print "Integers", fib

A long list of numbers is printed.

1
2
3
Integers [      1       1       2       3       5       8      13      21      34
  ... snip ... snip ...
  317811  514229  832040 1346269 2178309 3524578]

6. Select even-valued terms

The kata demands that we select the even valued terms now. This should be easy for you, if you followed the previous kata.

1
2
eventerms = fib[fib % 2 == 0]
print eventerms

There we go. Another opportunity to write unit tests.

1
2
[      2       8      34     144     610    2584   10946   46368  196418
  832040 3524578]

7. Sum the selected terms

This is the final step. Your enemies are lying on the ground helpless, unable to fight back. Finish the job, call the ndarray sum method.

1
print eventerms.sum()

For completeness, below is the complete code of this kata.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import numpy
 
#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.
 
#1. Calculate phi
phi = (1 + numpy.sqrt(5))/2
print "Phi", phi
 
#2. Find the index below 4 million
n = numpy.log(4 * 10 ** 6 * numpy.sqrt(5) + 0.5)/numpy.log(phi)
print n
 
#3. Create an array of 1-n
n = numpy.arange(1, n)
print n
 
#4. Compute Fibonacci numbers
fib = (phi**n - (-1/phi)**n)/numpy.sqrt(5)
print "First 9 Fibonacci Numbers", fib[:9]
 
#5. Convert to integers
# optional
fib = fib.astype(int)
print "Integers", fib
 
#6. Select even-valued terms
eventerms = fib[fib % 2 == 0]
print eventerms
 
#7. Sum the selected terms
print eventerms.sum()

That was quite a workout. More katas to come soon. Please stay tuned.

If you liked this post and are interested in NumPy check out NumPy Beginner’s Guide by yours truly. I would like to thank Christopher Felton and Gael Varoquaux for their recent reviews of my book.

Series NavigationNumPy Project Euler Problem 1NumPy Project Euler Problem 3
By the author of NumPy Beginner's Guide, NumPy Cookbook and Instant Pygame. If you enjoyed this post, please consider leaving a comment or subscribing to the RSS feed to have future articles delivered to your feed reader.
Share
This entry was posted in programming and tagged , . Bookmark the permalink.