In this recipe, we will sum the even-valued terms in the Fibonacci sequence whose values do not exceed four million. The Fibonacci series is a sequence of integers starting with zero, where each number is the sum of the previous two; except, of course, the first two numbers zero and one.
Note
For more information, read the Wikipedia article about Fibonacci numbers at http://en.wikipedia.org/wiki/Fibonacci_number .
This recipe uses a formula based on the golden ratio, which is an irrational number with special properties comparable to pi. It we will use the
sqrt,
log,
arange,
astype, and
sum functions.
The first thing to do is calculate the golden ratio (http://en.wikipedia.org/wiki/Golden_ratio), also called the golden section or golden mean.
- Calculate the golden ratio.
We will be using the
sqrtfunction to calculate the square root of five:phi = (1 + numpy.sqrt(5))/2 print "Phi", phi
This prints the golden mean:
Phi 1.61803398875 - Find the index below four million.
Next in the recipe, we need to find the index of the Fibonacci number below four million. A formula for this is given in the Wikipedia page, and we will compute it using that formula. All we need to do is convert log bases with the
logfunction. 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 recipe:n = numpy.log(4 * 10 ** 6 * numpy.sqrt(5) + 0.5)/numpy.log(phi) print n
The value for
nis:33.2629480359 - Create an array of 1-n.
The
arangefunction is a very basic function, which many people know. Still, we will mention it here for completeness:n = numpy.arange(1, n)
- Compute the 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 this recipe as input parameters.
Print the first nine Fibonacci numbers to check the result:
fib = (phi**n - (-1/phi)**n)/numpy.sqrt(5) print "First 9 Fibonacci Numbers", fib[:9]
Tip
Have a look at Chapter 8, Quality Assurance for pointers on how to write a unit test.
We are not starting with the number zero here, by the way. The aforementioned code gives us a series as expected:
First 9 Fibonacci Numbers [ 1. 1. 2. 3. 5. 8. 13. 21. 34.]You can plug this right into a unit test, if you want.
- Convert to integers.
This step is optional. I think it's nice to have an integer result at the end. OK, I actually wanted to show you the
astypefunction:fib = fib.astype(int) print "Integers", fib
This code gives us the following result, after snipping a bit for brevity:
Integers [ 1 1 2 3 5 8 13 21 34 ... snip ... snip ... 317811 514229 832040 1346269 2178309 3524578]
- Select even-valued terms.
The recipe demands that we select the even-valued terms now. This should be easy for you, if you followed the boolean indexing piece in the previous chapter:
eventerms = fib[fib % 2 == 0] print eventerms
There we go:
[ 2 8 34 144 610 2584 10946 46368 196418 832040 3524578]
For completeness, following is the complete code for this recipe:
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()
In this recipe, we used the functions sqrt, log, arange, astype, and sum; their description is as follows:
- The Indexing with booleans recipe in Chapter 2, Advanced Indexing and Array Concepts