In this first tutorial, we will explore some basic constructs of the Python language. We will encounter loops, lists, control flow and print statements. The aim is to show how powerful and intuitive the language can be by combining its simplest elements.
I will show how you can define your own functions. A function can be thought of as a "machine" which takes some inputs and gives you an output. A simple example is a function which finds all the divisors of a number n.
We will finish with a naive method for finding Perfect Numbers: (numbers which are equal to the sum of their proper divisors), and some mini-challenges.
The first task is to install the programming language Python, and IDLE, the Integrated Development Environment: see the Getting Started page. Note that we are using Python version 2.7.
Let's begin by opening IDLE. Either double-click the icon on the Desktop of the Raspberry Pi, or type "idle &" at the command prompt in the terminal. Once IDLE has loaded, you will see a new window with the title "Python Shell", and a prompt that looks like this:
You can enter simple Python statements at the prompt. Try entering, for example:
Press return (Enter) and this greeting will be repeated back to you. You should now see on screen:
Perhaps we should repeat ourselves a few times, until we start to believe this is actually true! We can repeat this by using a loop. Try entering:
Here, the second line should be indented so that it appears to be a "child" of the first line. The python shell automatically indents the second line for you. It does this whenever it sees the ":" symbol. You can change the indentation using the Tab key. Indenting is an essential grammatical feature of the Python language. It is used to group statements together in a logical way. For example, the loop will repeat all subsequent statements that have been indented once.
Once you have entered this code snippet, press return twice. If you have succeeded, you will see "I can write code!" repeated 10 times on successive lines. If you have not entered it correctly, you will get an error message, which may be rather incomprehensible! Try again until you succeed.
This should give a list of numbers,
Now try an alternative loop
This should give the output
For more on loops, see here.
Python can be used as a simple calculator. Let's try adding, subtracting, multiplying and dividing, i.e.:
You should get the answers 5, 1, 6, and 1. It may surprise you that the last answer is "1" rather than "1.5". A convention in many programming languages is that, an integer divided by another integer is also an integer, specifically, the result rounded down. To get the expected answer, try instead:
To get the remainder after division, use the
We can raise a number to a power, in either of these ways:
Note that ^ does not raise to a power, in Python at least.
We can take a square root, like this:
Alternatively, we can use the
Other common functions are available through the
We can save the value of any calculation into a named variable, which can be used in later statements. Try, for example
which should give the output
The first statement,
There is an even simpler way to create the same list. Try
Do you understand this syntax? It gives us a very powerful way of making lists.
The individual elements of a list can be accessed with
which gives the 4th element of our list, which is the square of 3, i.e. 9. What happens if you enter
It is simple to change the elements of a list individually, i.e.
and to add new elements at the beginning, middle and end.
As you can see from the above example, the elements in a list can be of different types. Here we have a mixture of "integers" (the numbers) and "strings" (the animal names), and the list is now rather bizarre!
For more about lists, see the introduction at python.org
A function is a "machine" that accepts inputs (arguments) and returns an output. Let's define a function 'sqlist' which returns a list of square numbers up to n*n (inclusive):
Now let's try defining a function to tell us whether a number is even or odd.
We have used an "if" statement. Here, "if" the remainder of n divided by 2 is zero, then the first statement is executed, otherwise ("else") the second statement is executed. Let's test it out:
The same function can be written in a more compact way as follows:
For more on control statements (like if/else), see here.
We can use "if" statements in list definitions. This offers a very powerful tool. For example, here is a one-line function that returns ALL the divisors of an integer (with the exception of 1 and the number itself).
Do you understand the syntax? This statement cycles through all numbers from 2 to n/2+1, but only includes in the list those numbers for which the statement n % i == 0 is "True". In other words, those numbers i for which n divided by i leaves no remainder.
Let's try it:
Note that 53 has no factors except 1 and itself (it is a prime number). So the list of factors is empty in this case.
It is rather amazing that we can find the factors of a number with just a single line of Python code. However, this statement is not particularly efficient. It checks n numbers; so we expect the time taken to scale in proportion to n.
A perfect number is a number which is equal to the sum of its proper divisors, i.e. all its divisors including 1 but not the number itself. For example, 6 = 3 + 2 + 1.
Combining Python's capabilities, we can write a one-line statement to find all the perfect numbers in the range 2 to n.
Let's try calling this function:
You can see that the perfect numbers are few and far between. This method is not particularly efficient. The time it takes scales roughly in proportion to the square of n (we say it is O(n2)). Try
This example reveals the power of Python, and also the power of the computer: we can check the first ten thousand numbers in a fraction of the time that a human would need. However, the example also demonstrates the limitations of any such crude 'frontal assault' on the problem. In a over a minute of run time on the Raspberry Pi, we have only managed to find the first four perfect numbers! Yet, for centuries, mathematicians have been aware of many more perfect numbers. In 1644, Mersenne listed the first eight: 6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008133952128.
Why is our approach so limited? There are two important reasons. Firstly, our method is not very efficient. It is not well-designed, and it does not make use of any of the special properties of perfect numbers that mathematicians have worked out over the years (for example, that every even perfect number can be written via Euclid's formula). With the aid of clever algorithms which make use of 'special knowledge', over 40 perfect numbers have now been found by computers.
But there is another, more more fundamental limitation: we can never hope to search all the numbers in a finite time, because there are an infinite number of integers! It is difficult to imagine how we could use a program to answer a really fundamental question like: are there an infinite number of perfect numbers? (and if not, what is the highest one?)
Despite such limitations, computers are an indispensible tool for many pure mathematicians: here is a recent discussion of the role of computers in proof in mathematics.
Despite the apparent simplicity of perfect numbers, there is still much that we don't know. For example, are there an infinite number of perfect numbers? Are there any odd perfect numbers? Perhaps one day you can help to answer these questions ...
1. Write a code to show that 8128 is a perfect number.
2. Fermat's little theorem says that ap-1 - 1 is divisible by p, if p is a prime number (for any integer a). Write a code to check this for the first few prime numbers 2,3,5,7,11,13,17,19,23, etc., and for the numbers a=2,3,4,5, etc. Challenge (A-level standard): Can you find out how to prove Fermat's little theorem?
3. Euclid proved that 2p−1(2p−1) is an even perfect number whenever 2p−1 is prime. Use this to find the 5th and 6th perfect numbers. Challenge (A-level standard): can you find out how to prove Euclid's statement?
4. The pair of numbers 220 and 284 are amicable numbers (i.e. friendly), because the sum of the factors of 220 is 284 (=1+2+4+5+10+11+20+22+44+55+110), and the sum of the factors of 284 is 220 (=1+2+4+71+142). Can you find the next highest amicable pair? For more about amicable numbers, see here or here.
5. Sociable numbers are chains of numbers, the sum of each of whose factors equals the next number in the chain. Can you find any chains with more than two links? For more about sociable numbers, see here. (Curio: as far as I know, no-one has found a chain with just 3 links, and it is not known whether three-link chains exist at all).
6. Let s(n) represent the sum of the factors of n (excluding n itself). For example, s(12) = 1+2+3+4+6 = 16. A number n is said to be abundant if s(n) > n, and deficient if s(n) < n. Can you write a code to find the first abundant odd number?
7. Is 276 part of a sociable chain of numbers?
Let us know how you are getting on: Email firstname.lastname@example.org, or follow on Twitter @pi3challenge.