Tutorials‎ > ‎

Week 0: Introduction to Python and Perfect Numbers

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.

First Lines of Code

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:

    >>> print "I can write code!"

Press return (Enter) and this greeting will be repeated back to you. You should now see on screen:
    >>> print "I can write code!"
    I can write code!

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:

    >>> for i in range(10):
            print "I can write code!"

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.


Let's examine the loop a little more closely. First, try entering:
>>> range(10)

This should give a list of numbers, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]. Note that range(10) actually gives you a list of numbers from 0 to 9. The list has 10 elements but starts from zero. By convention, range(n) gives a list from 0 to n-1. For a list from 1 to 10, use range(1,n+1).

Now try an alternative loop
>>> for i in range(10):
        print i,

This should give the output 0 1 2 3 4 5 6 7 8 9. What actually happened here? Well, i takes each of the values in the list given by range(10), successively. So first i=0, then i=1, all the way up to i=9. For each value of i, the statements in the indented block are "executed" (run). In this case, the indented block is just the print function, which here displays the value of i. The comma (,) prevents the print function from adding a newline (try removing it - see the difference?)

For more on loops, see here.

Python as a Calculator

Python can be used as a simple calculator. Let's try adding, subtracting, multiplying and dividing, i.e.:

    >>> 3 + 2
    >>> 3 - 2
    >>> 3 * 2
    >>> 3 / 2

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:

    >>> 3 / 2.0

To get the remainder after division, use the % symbol. For example, try entering 16 % 6. It should give 4, which is the remainder when 16 is divided by 6.

We can raise a number to a power, in either of these ways:
>>> 2**3
>>> pow(2, 3)
Note that ^ does not raise to a power, in Python at least.

We can take a square root, like this:
>>> 2**0.5
Alternatively, we can use the sqrt function from the math library (package); first we need to import this package. Try:
>>> import math
>>> math.sqrt(2)

Other common functions are available through the math library. Try for example math.cos(math.pi), math.exp(1), or math.sinh(3) .

We can save the value of any calculation into a named variable, which can be used in later statements. Try, for example
>>> a = 1
>>> b = 3
>>> c = a + b
>>> print a, b, c

which should give the output 1 3 4. Do you see why?


Suppose we wanted to find a list of the squares of the numbers 0 to 10. How could we achieve this? One way would be to write

>>> a = []
>>> for i in range(10+1):
>>> print a

The first statement, a = [], creates an empty list (i.e. a list without any elements). The statement inside the loop, a.append(i**2),  appends the square of i to the end of the list. By putting this statement inside the loop, we can build up a list of squares, step-by-step.

There is an even simpler way to create the same list. Try

>>> a = [i**2 for i in range(10+1)]

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 a[i], where a is the name of the list variable, and i is the list index. The only subtlety here is that the index starts at zero, so a[0] is the first element of the list. For example, try entering

>>> a[3]

which gives the 4th element of our list, which is the square of 3, i.e. 9. What happens if you enter a[20]? Why?

It is simple to change the elements of a list individually, i.e.

>>> a[3] = "hippopotamus"

and to add new elements at the beginning, middle and end.

>>> a.insert(0, "aardvark")
>>> a.insert(3, "gnu")
>>> a.append("zebra")
>>> a

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

Defining a Function

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):

>>> def sqlist(n):
>>>    return [i**2 for i in range(n+1)]

Here sqlist is the name of the function, n is the argument, and def and return are Python keywords. Let's try it:

>>> sqlist(20)

Control statements

Now let's try defining a function to tell us whether a number is even or odd.

>>> def even_or_odd(n):
    if n % 2 == 0:
        str = "even"
        str = "odd"
    return str

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:
>>> [even_or_odd(i) for i in range(10)]

The same function can be written in a more compact way as follows:

>>> def even_or_odd(n):
     return "even" if n % 2 == 0 else "odd"

For more on control statements (like if/else), see here.

List comprehension

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).

>>> def ifactors(n):
    return [i for i in range(2, n/2+1) if n % i == 0]

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:
>>> ifactors(54)
>>> ifactors(53)

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.

Perfect numbers

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.

>>> def perfect(n):
    return [i for i in range(2, n+1) if sum(ifactors(i)) + 1 == i]

Let's try calling this function:

>>> perfect(100)

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 perfect(10000). What is the fourth perfect number?

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 pi3challenge@sheffield.ac.uk, or follow on Twitter @pi3challenge.