# Ptyhon: For-Loops

([home](https://github.com/alexhkurz/introduction-to-programming/blob/master/README.md) ... [previous](https://hackmd.io/@alexhkurz/HyJqEPN2L) ... [next](https://hackmd.io/@alexhkurz/Hy48XsvpI))

(we spent a session on each activity plus one session solving the homework and one session discussing and improving solutions)

As legend has it, little [Gauss](https://en.wikipedia.org/wiki/Carl_Friedrich_Gauss) was disciplined by his teacher and had to calculate the sum $1+2+\ldots+100$.

Even with a calculator this is still a boring task. And a modern teacher could just replace the 100 by 1000.

**Activity:** Can we do this more easily in Python?

sum = 0
for i in range(0,101):
sum = sum + i
print(sum)

- The main idea of the program is to put the addition in a loop. In this way the `+` in the program corresponds to the 100 occurrences of $+$ in the sum $0+1+2+\ldots+100$.
- `i` counts the 100 times, the program goes through the loop. Note how `i` is used to update the value of `sum`.
- Read `sum = sum + i` as "let the new value of sum be the old value of sum plus i".

A good way to understand algorithms is to write them down in what is called **pseudocode**. Pseudocode is not tied to a particular programming language, and you are free to use plain English as long as it is clear how every single step should be executed. In our case we may write:

1: Let sum be 0.
2: Let i be 0
3a: Let the new value of sum be the old value of sum plus i.
3b: If i < 100 then increase i by 1 and goto line 3a.
4: Print sum.

**Optional Activity:** How did Gauss solve the problem so quickly without the help of a computer? Can you find a formula that avoids taking the sum?

## Triangular Numbers

We continue with the program above. (I made only one little change.) Download the program [for_loop_triangular.py](https://github.com/alexhkurz/introduction-to-programming/blob/master/src/for_loop_triangular.py).

**Activity:**
- Run the program for different values of `n`.
- To see what happens in the loop, indent the statement `print(sum)` (you can use the `tab`-key for this) so that it aligns with the line `sum = `. This means that the printing of `sum` now happens "in the loop", that is, it happens for each value of `i` starting from `0` up to `n`. Running the program now you should see a sequence that begins like
$$0,1,3,6,10,\ldots $$
- Explain the program in your own words. What is the role of the variable `sum`? Draw a table of the execution using the memory model of the [previous session](https://hackmd.io/@alexhkurz/HyJqEPN2L). Start as follows

|`i` | `sum` before `sum=sum+i` | `sum` after `sum=sum+i` |
|:---:|:---:|:---:|
|0 | 0| 0 |
|1 | 0| 1|
|2 | 1| 3|
|... | ...|...|

and continue the table.

## The Online Encyclopedia of Integer Sequences

Mathematicians love infinite sequence for so many different reasons. In fact, they wrote a whole book that only contains sequences, the [Online Encyclopedia of Integer Sequences(OEIS)](https://oeis.org/). You can enter any sequence of numbers and see whether it is the beginning of known sequence in the encyclopedia. Try it. Try to find one that is not in the encyclopedia. Have a look at the [wikipedia article on OEIS](https://en.wikipedia.org/wiki/On-Line_Encyclopedia_of_Integer_Sequences).

**Exercise:** Enter 0,1,3,6,10 in [OEIS](https://oeis.org/). How many sequences in the OEIS start in this way? Can you see under which name our sequence of numbers is known? How many numbers do you need to enter to determine this sequence? Look up the wikipedia article on these sequences.

By the way, the OEIS is an important tool for professional mathematicians and computer scientists. Integer sequences can come up in many applications. Via the OEIS, researchers can find the name of a sequence and then discover related work.

## Sums of squares

Our next example is a simple modification of the triangular numbers.

**Exercise:** Modify the program [for_loop_triangular.py](https://github.com/alexhkurz/introduction-to-programming/blob/master/src/for_loop_Gauss.py) so that it computes the "sum of squares"
$$ 1+4+9+16+ \ldots + n^2$$

The sequence "sums of squares" then is
$$ 0, 1, 5, 14, 30, \ldots $$

**Exercise:** Enter $0, 1, 5, 14, 30$ in [OEIS](https://oeis.org/). Under which name is our sequence known in the OEIS? Look the sequence up in Wikipedia.

## Fibonacci numbers

An old example of a similar but more complicated sequence is known as the Fibonacci numbers. [Leonardo of Pisa](https://en.wikipedia.org/wiki/Fibonacci) was the son of a merchant and accompanied his father on his travels. From the Arabs he learned how to use the zero, which he later made known in Europe with his [Book of Calculation](https://en.wikipedia.org/wiki/Liber_Abaci).

In this book, Fibonacci also described a sequence of numbers, now known as [Fibonacci numbers](https://en.wikipedia.org/wiki/Fibonacci_number), with the help of a [story about rabbits](http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibnat.html#section1.1).

**Activity:** The Fibonacci numbers start out like this:
$$0,1,1,2,3,5,8,13,\ldots$$

We can write the same sequence in table form (programmers like to start counting from 0 on):

|$n$ | $fib(n)$ |
|:---:|:---:|
|0 | 0|
|1 | 1|
|2 | 1|
|3 | 2|
|4 | 3|
|5 | 5|
|6 | 8|
|7 | 13|
|... | ...|

- Write down a rule that continues the sequence.
- Using the rule write out the next 4 Fibonacci numbers.
- Write a Python program that computes $fib(n)$.

[Hint: Write down the program first in pseudocode. You will need a conditional, a loop and two variables to keep track of the two last values of the sequence.]

## The mathematical definition of the Fibonacci numbers

The rule for computing a new Fibonacci number was:

To compute a new Fibonacci number take the sum
of the last two numbers in the sequence.

In symbolic notation, we can write this as
$$fib(n) = fib(n-2) + fib(n-1)$$

or also as
$$fib(n+2) = fib(n) + fib(n+1)$$

The latter form has the advantage that we do not need to make exeptions in order to avoid negative numbers.

To summarise, we can write down the official mathematical definition of the Fibonacci numbers as

\begin{align}
fib(0) & = 0\\
fib(1) & = 1\\
fib(n+2) & = fib(n) + fib(n+1)
\end{align}

where $n$ can be any natural number.

In the next session, we will discuss why the mathematical definition looks so much more elegant than the Python program and we will explore whether we cannot turn the mathematical definition into a program more directly.

## Homework

Learning your first programming language is a bit like learning a natural language. It needs a lot of practice.

In all the exercises you should go through the steps below.

- Devise a rule that continues the sequence.
- Write out a table displaying the computation for the first few steps.
- What variables do you need? How can the rule be given in Python code?
- Write and test the program.

Sometimes there is a [closed formula](https://en.wikipedia.org/wiki/Closed-form_expression) that could be used instead of a loop. As the exercises are meant to practice the writing of loops, I would recommend to not use the formula. (On the other hand, from a mathematical point of view, I don't want to discourage a clever solution.)

**Exercise:** For each of the following, write a Python program that continues the sequences below.

- $1, 2, 6, 24, 120,\ldots$

- $0,1,3,7,15,31, \ldots$

- $0,1,2,5,12,29,70, 169, \ldots$ (inspired by Fibonacci)

- Invent your own ...

## References

- [w3schools.com: Python For Loops](https://www.w3schools.com/python/python_for_loops.asp)
- [Python Language Reference: The `for` statement](https://docs.python.org/3/reference/compound_stmts.html#the-for-statement)
- [Stackoverflow: Is there a label/goto in Python?](https://stackoverflow.com/questions/438844/is-there-a-label-goto-in-python)

## Further Reading

- [Neil Sloane: My Favorite Integer Sequences](http://neilsloane.com/doc/sg.pdf)