Collatz Sequences in the Wolfram Language
Author
Arnoud Buzing
Title
Collatz Sequences in the Wolfram Language
Description
Exploring Collatz Sequences with the Wolfram Language
Category
Working Material
Keywords
collatz, collatz conjecture, collatz sequence
URL
http://www.notebookarchive.org/2021-08-7vhmf3n/
DOI
https://notebookarchive.org/2021-08-7vhmf3n
Date Added
2021-08-17
Date Last Modified
2021-08-17
File Size
229.98 kilobytes
Supplements
Rights
Redistribution rights reserved
Download
Open in Wolfram Cloud
Collatz Sequence
Collatz Sequence
by Arnoud Buzing
Collatz function definition — If n is even, divide it by 2. Otherwise, multiply by 3 and add 1:
In[]:=
collatz[n_Integer]:=If[EvenQ[n],Quotient[n,2],3n+1]
Example 1 — The number 5 is even, so the output is 16 (3×5+1):
In[]:=
collatz[5]
Out[]=
16
Example 2 — The number 8 is even, so the output is 4 (divide by 2):
In[]:=
collatz[8]
Out[]=
4
Collatz sequence definition — iterate the sequence until it terminates:
In[]:=
collatzSequence[n_Integer]:=NestWhileList[collatz,n,#=!=1&]
This is the sequence for 17:
In[]:=
collatzSequence[17]
Out[]=
{17,52,26,13,40,20,10,5,16,8,4,2,1}
It is conjectured, but not known, that the sequence always ends in 1. The numbers in the sequence jump both up and down, like a hailstone in a thunderstorm. The number 63,728,127 takes 949 steps:
In[]:=
ListLinePlot[collatzSequence[63728127],PlotRange->All]
Out[]=
In[]:=
Length[collatzSequence[63728127]]
Out[]=
950
It reaches a very large number before eventually tumbling back to 1:
In[]:=
MinMax[collatzSequence[63728127]]
Out[]=
{1,966616035460}
You can plot the length of each sequence for a given number. This plots them for numbers up to 1,000:
In[]:=
ListPlot[Length[collatzSequence[#]]&/@Range[1000],PlotRange->All]
Out[]=
Different starting values can give the same result:
In[]:=
{collatz[5],collatz[32]}
Out[]=
{16,16}
From that point on, the sequences are the same:
In[]:=
collatzSequence[5]
Out[]=
{5,16,8,4,2,1}
In[]:=
collatzSequence[32]
Out[]=
{32,16,8,4,2,1}
You can turn these sequences into a directed graph:
In[]:=
dEdges[n_]:=BlockMap[DirectedEdge@@#&,collatzSequence[n],2,1]
In[]:=
Graph[dEdges[5],VertexLabels->"Name"]
Out[]=
In[]:=
Graph[dEdges[32],VertexLabels->"Name"]
Out[]=
You can combine multiple sequences as well:
In[]:=
g=DeleteDuplicates[Join[dEdges[5],dEdges[32]]]
Out[]=
{516,168,84,42,21,3216}
In[]:=
Graph[g,VertexLabels->"Name"]
Out[]=
Here is a directed graph that combines the sequences for starting numbers up to 20:
In[]:=
collatzGraph[n_Integer]:=DeleteDuplicates[Join@@Table[dEdges[i],{i,n}]]
In[]:=
Graph[collatzGraph[20],VertexLabels->"Name"]
Out[]=
For larger numbers, the graph becomes highly branched. This helps to understand why the Collatz conjecture is so difficult to prove.
In[]:=
Graph[collatzGraph[1000],ImageSize->Full]
Out[]=
The same graph, but using a different graph layout:
In[]:=
Graph[collatzGraph[1000],GraphLayout->{"LayeredDigraphEmbedding","Rotation"->90°},ImageSize->Full]
Out[]=
Cite this as: Arnoud Buzing, "Collatz Sequences in the Wolfram Language" from the Notebook Archive (2021), https://notebookarchive.org/2021-08-7vhmf3n
Download
