Pre: Demo of Collatz conjecture

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:

\[\begin{split}f(n) = \begin{cases} n / 2& \text{ if }n = 0 \text{mod } 2\\ 3n + 1& \text{ if }n = 0 \text{mod } 2\\ \end{cases}\end{split}\]

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

\[\begin{split}\begin{align} f(3) &= 3\times 3 + 1 = 10\\ f(10) &= 10/2 = 5\\ f(5) &= 3\times 5 + 1 = 16\\ f(16) &= 16/2 = 8\\ f(8) &= 8/2 = 4\\ f(4) &= 4/2 = 2\\ f(2) &= 2/1 = 1 \end{align}\end{split}\]

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

\[\begin{align} f(6) &= 6/2 = 3 \end{align}\]

which we know terminates.

For \(n=7\):

\[\begin{split}\begin{align} f(7) &= 3\times 7 + 1 = 22\\ f(22) &= 22/2 = 11\\ f(11) &= 3\times 11 + 1 = 34\\ f(34) &= 34/2 = 17\\ f(17) &= 3\times 17 + 1 = 52\\ f(52) &= 52/2 = 26\\ f(26) &= 26/2 = 13\\ f(13) &= 3\times 13 + 1 = 40\\ f(20) &= 20/2 = 10 \end{align}\end{split}\]

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.