The Collatz Conjecture

One of the most famous unsolved problems in mathematics

Definition

The Collatz Conjecture states that repetition of a simple rule on any positive integer will eventually converge to 1. The rule is: if the number is even, divide by 2; if the number is odd, multiple by three and add 1.

Let's implement the function in the Wolfram Language, allowing the function to memorize it as it is called:

Collatz[1]:=1;Collatz[n_?EvenQ]:=Collatz[n]=Collatz[n/2]Collatz[n_?OddQ]:=Collatz[n]=Collatz[3n+1]

When called, the function will recursively evaluate until hitting 1.

Let's test it for arbitrarily large numbers:

Collatz/@{5,222,9123,100001}

{1,1,1,1}

Now, test it for all numbers up to a certain limit:

DeleteDuplicates[Collatz/@Range[5000000]]

{1}

This doesn't prove the conjecture, but it does verify it for small numbers.

Visualization:

To explore the patterns of convergence, it is useful to define a new function, which lists the path every number takes to get to 1.

CollatzList[1]:=1;CollatzList[n_ /;EvenQ[n]]:=CollatzList[n]=Flatten[{n,CollatzList[n/2]}];CollatzList[n_/; OddQ[n]]:=CollatzList[n]=Flatten[{n,CollatzList[3n+1]}];

Start by visualizing how often the paths pass through each number.

Histogram[Flatten[Map[CollatzList,Range[100000]]],{1,20,1}]

The frequency on this chart is the number of integers from 1 to 100,000 that pass through the specified number before converging to 1. Every path must eventually pass through a power of two before reaching 1; this is illustrated by the histogram peaks at these numbers. The histogram nearly vanishes at every multiple of 3, indicating very few paths pass through these numbers. The distribution at the remaining integers seems more random.

Histogram[Flatten[Map[CollatzList,Range[100000]]],{1,100,1}]

Over a wider range, the random pattern seems to continue.

Now, view the number of steps required by each integer to reach 1. First, convert the list of paths into a list of steps.

RuleList[n_]:=Thread[Partition[CollatzList[n],2,1][[All,1]]-> Partition[CollatzList[n],2,1][[All,2]]];

The length of the list of steps gives the length of the path from every integer to 1.

ListPlot[Table[Length[RuleList[n]],{n,Range[2,100]}],PlotRange->All]

At low integer values, the path lengths seem to scale like Sqrt[n], with a set of exceptions above the main group.

ListPlot[Table[Length[RuleList[n]],{n,Range[2,1000]}],PlotRange->All]

With a larger set of integers, the previous exceptions look like a wholly separate pattern, characterized by longer paths.

ListPlot[Table[Length[RuleList[n]],{n,Range[2,100000]}],PlotRange->All]