The Collatz Problem asks if repeatedly applying the function
n
n
2
niseven
3n+1
nisodd
eventually gives
1
for all positive integers
n
. This post shows how to visualize this problem as a tree using the Wolfram Language.

Define the Iterators

In its most basic form, we can define the iterator in the Collatz problem as follows:
In[]:=
collatz[n_?EvenQ]:=n/2​​collatz[n_?OddQ]:=3n+1
We can get a list of the results of applying this iterator several times using the Wolfram Language function NestList:
In[]:=
NestList[collatz,25,10]
Out[]=
{25,76,38,19,58,29,88,44,22,11,34}
Or we can repeatedly apply this iterator until it reaches
1
using the function NestWhileList:
In[]:=
NestWhileList[collatz,25,Not@*EqualTo[1]]
Out[]=
{25,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1}
The Collatz conjecture states that this process will terminate for all positive integers
n
.
Since
3n+1
is even whenever
n
is odd, and so will be followed by
3n+1
2
, we can decrease the number of steps without affecting the Collatz problem as follows:
In[]:=
collatz2[n_?EvenQ]:=n/2​​collatz2[n_?OddQ]:=(3n+1)/2
Now with this iterator, the number of steps to reach
1
is decreased:
In[]:=
NestWhileList[collatz2,25,Not@*EqualTo[1]]
Out[]=
{25,38,19,29,44,22,11,17,26,13,20,10,5,8,4,2,1}
We can decrease the number of steps even further by restricting to odd numbers only and repeatedly dividing by
2
as much as possible at each step:
In[]:=
collatzOdd[n_?OddQ]:=With[{m=3n+1},m/2^IntegerExponent[m,2]]
With this iterator, all the even numbers in the original sequence are skipped:
In[]:=
NestWhileList[collatzOdd,25,Not@*EqualTo[1]]
Out[]=
{25,19,29,11,17,13,5,1}

Collatz Graph

The sequence of values produced by repeatedly applying an iterator to a given value is called its orbit. We can visualize these orbits by producing a graph using the function NestGraph:
In[]:=
collatzGraph[iterator_:collatz,init_,steps_]:=NestGraph[iterator,init,steps,VertexLabels->Automatic]//LayeredGraph
In[]:=
collatzGraph[12,3]
Out[]=
The orbits of the Collatz iterator form a branching structure, since some numbers, like
10
, can be reached in two different ways:
In[]:=
collatz[3]
Out[]=
10
In[]:=
collatz[20]
Out[]=
10
This results in two different branches merging together in the graph:
In[]:=
collatzGraph[{12,13},3]
Out[]=
The numbers
4
,
2
, and
1
form a cycle:
In[]:=
collatzGraph[4,3]
Out[]=
If the Collatz conjecture is true, then this is the only such cycle, and all branches eventually merge and lead to this cycle. For example, let’s consider the orbits of
12
,
13
, and
21
. After three steps, the orbits of
12
and
13
merge:
In[]:=
collatzGraph[{12,13,21},3]
Out[]=
After two more steps, these orbits merge:
In[]:=
collatzGraph[{12,13,21},5]
Here is the graph using the iterator that combines the two steps following odd numbers:
Here is the graph using the iterator restricted to odd numbers:

Collatz Tree

We can also perform this process in reverse, starting with a number and at each step producing the immediate predecessors in the Collatz orbits. First, let’s define the inverse iterator:
Then we can produce a tree using the function NestTree:
Let’s do the same with the inverse of the iterator that combines the two steps following odd numbers:
Produce the first two levels of the tree limited to five branches per node:

Interactive Collatz Tree

NestTree expands the branches of a tree up to a given level:
I submitted an interactive version of NestTree to the Wolfram Function Repository that allows branches to be expanded by clicking on the leaves:
The output is reset when the notebook is closed, so to save the output, select the cell and choose the Cell ▶ Convert To ▶ Bitmap menu item.
Interactively explore the full Collatz problem tree:
Interactively explore the tree using the iterator that combines the two steps following odd numbers:
Interactively explore the tree using the iterator restricted to odd numbers:

Acknowledgement

This post was inspired by a Wolfram Community user question.

CITE THIS NOTEBOOK

Exploring the Collatz Problem Tree​
by Ian Ford​
Wolfram Community, STAFF PICKS, January 31, 2024
​https://community.wolfram.com/groups/-/m/t/3113948