# The Syracuse problem

The Syracuse problem, also known as the Collatz conjecture or the 3n+1 conjecture or Ulam conjecture, is a very simple problem of arithmetics that is still unsolved today. It can be stated as follows.

Syracuse problem : $n \geq 1$ being an integer, repeat the following operations

• If the number is even then divide it by two
• If the number is odd then multiply it by $3$ and add $1$

Conjecture : This process always reaches the number $1$

Example : starting with $n=10$ the sequence is

$\displaystyle 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$

If we continue the process after $1$ then it indefinitely repeats a cycle

$\displaystyle 1 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 2 \rightarrow 1 \ldots$

The following graph represents the sequence for $n=11$ until it reaches $1$.

n = 11

The following graph represents the sequence for $n=27$ until it reaches $1$.

n = 27

The following graph represents the number of steps to reach $1$ for $n$ between $1$ and $10000$.

Number of steps until 1 is reached

The algorithm to compute the sequence was implemented in SciLab as follows :

result = [];
while n>1
result = [result ; n];
if modulo(n,2)==0
n = n/2;
else
n = 3*n+1;
end
end
result = [result ; 1];

This program halts when $1$ is reached. If the conjecture is true then it must always stops. At this time, the conjecture has been checked for all initial values up to $n = 19.2^{58}$ as explained on this web site.

Surprisingly, the story has inspired a novel (in French)

La Conjecture de Syracuse, Antoine Billot, Editions Gallimard