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

n = 11

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

n = 27

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

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 La Conjecture de Syracuse, Antoine Billot, Editions Gallimard

Advertisements

One thought on “The Syracuse problem

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s