Ctrl+K

Collatz conjecture

24. Collatz conjecture#

The Collatz conjecture, also known as the “conjecture de Syracuse” in French, is a famous unsolved problem in mathematics. It involves sequences of integers where each term is derived from the previous term using specific arithmetic operations. According to the conjecture, these sequences always eventually reach the number 1, regardless of the starting positive integer.

Here’s how the sequence is generated:

  • If the current term is even, the next term is half of the current term.

  • If the current term is odd, the next term is 3 times the current term plus 1.

Mathematically, the next term \(f(n)\) of the sequence is defined as:

\[\begin{split} f(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2},\\[4px] 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases} \end{split}\]

Now form a sequence by performing this operation repeatedly, beginning with any positive integer, and taking the result at each step as the input at the next. In notation:

\[\begin{split} a_i = \begin{cases}n & \text{for } i = 0, \\ f(a_{i-1}) & \text{for } i > 0 \end{cases} \end{split}\]

The conjecture asserts that these sequences will always eventually reach the number 1. Although the conjecture has been verified for integers up to approximately \(2.95×10^{20}\), no general proof has yet been discovered.

In this exercise, you will implement a Python function to explore the Collatz conjecture and practice using loops and lists.

24.1. Implementing the Sequence#

24.1.1. Function next_term#

Create the function next_term that returns the next term in a Collatz sequence given an integer i. This function will determine whether i is even or odd and then compute the next term in the sequence accordingly. Make sure that the return value is an integer.

def next_term(i):
    pass

24.1.2. Generating the sequence#

Create a function named collatz that takes an integer i as its parameter. This function should generate a list of integers representing the sequence starting from i and following the rules of the Collatz conjecture, until reaching 1.

def collatz(i):
    pass

# collatz(15) # [15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]

24.1.3. Ploting the Sequence#

You can use the matplotlib module to plot the flight. Copy and try the following function.

import matplotlib.pyplot as plt

def plot(i):
    l = collatz(i)
    plt.title(f'Collatz sequence of {i}')
    plt.plot(l)
    plt.show()

#plot(15)

24.2. Stopping Time#

For a sequence starting with \(a_0=n\), the smallest \(i\) such that \(a_i < a_0\) is called the stopping time \(n\). Similarly, the smallest \(k\) such that \(a_k = 1\) is called the total stopping time of \(n\).

24.2.1. Finding the Largest Total Stopping Time#

Create a function largest_total_stopping_time that returns the sequence starting from 1 to n, having the largest total stopping time.

def largest_total_stopping_time(n):
    pass

#s = largest_total_stopping_time(10)
#print(s) # [9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
#print(len(s)) # 20

24.2.2. Finding the Stopping Time#

Create a function find_stopping_time that takes a sequence as parameter and return the stopping time.

def find_stopping_time(l):
    pass

#s= [9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
#print(find_stopping_time(s)) # 3

24.2.3. Finding the Largest Stopping Time#

Create a function largest_stopping_time that returns the sequence starting from 1 to n, having the largest stopping time.

def largest_total_stopping_time(n):
    pass

largest_total_stopping_time(10) # [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

24.2.4. Plot#

Plot the sequence starting with a value less than than \(100\) with the largest stopping time. It will be hard to see anything in normal scale. You can change the scale of the y axes.

def plot(i):
    l = collatz(i)
    plt.yscale("log")
    plt.title(f'Collatz sequence of {i}')
    plt.plot(l)
    plt.show()
Contents