Last week, we introduced some simple commands in Python and used them to compute the first few perfect numbers, using only a few lines of code.
In this tutorial we will look at another simple mathematical problem which can be explored with Python: the Fibonacci Sequence. The Golden Ratio will make an unexpected appearance!
Last time, we wrote our Python commands directly into the shell, by typing at the prompt (
In the menu of IDLE, go to File -> New Window. In the new window, type
You can run your program (i.e. execute the commands in the python file, in the order in which they appear) by pressing F5 in IDLE, or selecting the menu option Run -> Run Module. You should now see your greeting appear in the Python Shell.
You can also run your program directly from the command line, by typing
From now on, I suggest that you save (Ctrl-S) your Python commands in files, and run them with F5 in IDLE. At the end of this page, I have attached some example Python files which you may wish to investigate.
The sequence of Fibonacci numbers is
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, etc. ...
You can see that the next value in the list is found by adding together the preceding two values. For example, 13 = 8 + 5, 21 = 13 + 8, 34 = 21 + 13, etc. Mathematically, we can define the sequence with a recurrence relation:
F(n+1) = F(n) + F(n-1)
and two initial 'seed values', F(0) = 0 and F(1) = 1.
Leonardo of Pisa, known as Fibonacci, introduced this sequence to European mathematics in his 1202 book Liber Abaci. It is thought to have arisen even earlier in Indian mathematics.
Let's look at a simple code -- from the official Python tutorial -- that generates the Fibonacci sequence.
I've put these commands in
This example introduces some new Python commands, which are explained here. Let's take a look at each line in turn:
There are many other ways to compute the Fibonacci sequence. One possibility is the following code:
This is an iterative method, like the previous example -- it uses a loop. The main difference is that I keep the values in a list, and "appending" new values to the end of the list.
Do you see how we can retrieve the individual elements of the list? Here,
Fibonacci numbers are defined mathematically (above) with (i) a recurrence relation F(n+1) = F(n) + F(n-1) and (ii) base cases F(1) = 1, F(0) = 0. Rather than using an iterative method, featuring a loop, we may instead define a "recursive" function which is closer in spirit to this mathematical definition.
See how the function calls itself repeatedly? This is an example of a recursive method. By repeatedly calling itself, the recurrence proceeds downwards until the base case is reached.
Now let's think about the ratio of successive elements of the sequence, i.e. F(n+1) / F(n). It turns out that this ratio tends towards a fixed value, as the Fibonacci numbers get larger. Moreover, this particular value is very well-known to mathematicians through the ages. It is known as the golden ratio, and is given by
Try computing the ratio of successive terms in the list of Fibonacci numbers, with a statement like:
What do you see? How close can you get to the precise value of the Golden Ratio? (This code may be found in
The Fibonacci numbers can be represented graphically as the lengths of arms in a spiral, or as squares tiling a rectangle, as shown below. In future weeks, I will show how to draw such patterns using the
The Golden Ratio is found in a special type of rectangle. When a rectangle is placed next to a square, as shown, they make a second rectangle. The Golden Ratio occurs when the two rectangles are similar, which means that the ratio of their side lengths is that same,
There is actually a simple mathematical formula for computing the nth Fibonacci number, which does not require the calculation of the preceding numbers. It features the Golden Ratio:
This is called Binet's formula. We can implement Binet's formula in Python using a function:
This code might look a bit dodgy. For instance, how can we be sure that the square root will be taken before the division? Here, we are relying on the fact that Python (like most languages) executes statements in a certain fixed order of precedence. Raising-to-the-power takes precedence over division, which (like multiplication) takes precedence over addition and subtraction. See here for the order of precedence of common operations. Where a different order is required, we should use brackets (as in the example above).
Python code for all of these methods can be found in
1. In the picture above, six squares are fitted inside a rectangle, leaving no space. In other words, the rectangle is tiled with squares. Can you add another square to make a new rectangle? How big is it? Now add another square ... how big? How does the size of the squares relate to the Fibonacci sequence?
2. In the picture above, there are two squares of the same size. But if you could only use squares of different sizes (whole numbers), can you tile a rectangle? If so, can you work out how? [This is quite hard, if you need a hint, firstname.lastname@example.org]
Next week we will learn how to use Python to generate beautiful Fibonacci disks like this (using a code written by Peter Derlien)