# Pre: Demo of Collatz conjecture¶

## Corresponding lab sheet:¶

## Objectives¶

- Motivate the use of recursion and writing/reading to file through the study of the Collatz conjecture;
- Describe recursion;
- Describe reading and writing to file.

## Notes¶

Tell students we are going to investigate a particular mathematical process defined by the following recursive relationship:

**Ask students what :math:`f(2)` is?**

Realise that we have what we will call a base case: computing \(n=2\) essentially ends the process.

**What happens when we recursively call :math:`f(n)`?**

Demonstrate what is meant by this with \(n=3\):

We see that with \(n=3\) the process eventually finishes.

**Ask students if they think this will always be the case? Why?**

**In groups, using pen and paper repeatedlycompute :math:`f(n)` for
:math:`nin{2, 3, 4, 5, 6, 7, 8, 9, 10}**

We know it terminates for \(n\in\{2,3,4,5,8,10\}\).

For \(n=6\):

which we know terminates.

For \(n=7\):

which we know terminates.

**Ask students if they think this will always be the case? Why?**

Explain that there is overwhelming evidence that this does indeed always terminate but that we do not know for sure if it is true.

**Ask students if they know what this is called?**

A conjecture.

Mention the following text from the corresponding wiki page:

“Paul Erdős said about the Collatz conjecture: ‘Mathematics may not be ready for such problems.’ He also offered $500 for its solution.[9] Jeffrey Lagarias in 2010 claimed that based only on known information about this problem, ‘this is an extraordinarily difficult problem, completely out of reach of present day mathematics.’”

**In groups: write some code to check if the process terminates for a given
:code:`n`**

First let us write the function itself:

```
>>> def func(N):
... """Function to apply the Collatz transformation to an integer N"""
... if N % 2 == 0:
... return int(N / 2)
... return 3 * N + 1
>>> func(10)
5
>>> func(5)
16
```

**Describe recursion as having two steps:**

- A base case: in our case this is \(N=1\).
- Recursive relationship: in our case \(a(N)=f(a(N - 1))\)

Let us write the process:

```
>>> def collatz_process(N, count=0):
... """
... Recursively call the collatz process and return the number of
... times it was called. This is called the "stopping time".
... """
... if N == 1:
... return count
... count += 1
... return collatz_process(func(N), count=count)
>>> collatz_process(4)
2
>>> collatz_process(7)
16
```

**Ask students, to in group discuss the code and check if there are any
questions.**

Finally, explain that so far essentially all mathematicians have been able to do
is test this process numerically and have found that it **always** terminates.

One way to do this is to keep track of the results so far on disk:

```
>>> with open("collatz_data.txt", "w") as f:
... for N in range(2, 50): # Could swap this for an infinite loop
... stopping_time = collatz_process(N)
... string = str(N) + "," + str(stopping_time) + "\n"
... f.write(string)
```

We could then read this in and check from a given point or perhaps give the file to other to use.

## Lab sheet¶

Show how these recursion will be gone over in the lab sheet. Also discuss reading and writing: highlight where the files needs to be.