Collatz Heights

Math 242 Modern Computational Mathematics

Preliminary Code

The Collatz Function

Last time we defined the Collatz function Col(n) for any positive integer n as follows: if n is even, then Col(n)=(n/2), but if n is odd, then Col(n)=3n+1.

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

Computing trajectories

We also wrote a computeTrajectory module that computes the sequence of Collatz iterates from a starting integer n. This module stops when either a 1 is reached or the loop repeats maxIter times.

Today we modify our computeTrajectory module, specifying that maxIter is an optional parameter with a default value of 100,000. Note the syntax for this modification. Furthermore, we use the length of the trajectory rather than a separate counter variable.

computeTrajectory[start_,maxIter_:100000]:=Module[
{n=start,traj={start}},
(* compute the trajectory until we find 1 *)
While[n!=1,
n=col[n];
AppendTo[traj,n];
If[Length[traj]==maxIter,Break[]] (* quit if the length of the trajectory reaches maxIter *)
];
(* return the trajectory *)
traj
]

Test our revised module:

computeTrajectory[27]

Plotting trajectories

Here is a version of our plotTrajectory function from last time.

plotTrajectory[trajectory_]:=ListPlot[trajectory,PlotRange->All,AxesLabel->{"iteration","value"},Joined->True,PlotStyle->Orange,Mesh->All,MeshStyle->{Blue,PointSize[Medium]}]

We can compute a trajectory and then plot it like this:

traj=computeTrajectory[27]
plotTrajectory[traj]

Heights of Collatz Trajectories

Today we will explore the heights of Collatz trajectories. Let height(n) denote the maximum value in the Collatz trajectory starting with n.

Let’s write a simple function that computes the height of a Collatz trajectory:

height[n_]:=Max[computeTrajectory[n]]

Try it out:

height[27]

heightList=height/@Range[20]

computeTrajectory[3]

Height 16 appears frequently. Which starting value lead to height 16?

list16=Position[heightList,16]//Flatten

computeTrajectory/@list16

What is the most common height for starting values n<=100?

heightList=height/@Range[100]

Commonest[heightList]

Tally[heightList]

What is the most common height for starting values n<=10000?

heightList=height/@Range[10000];
SortBy[Tally[heightList],First]

SortBy[Tally[heightList],Last]

ReverseSortBy[Tally[heightList],Last]

Height 9232 occurs 1579 times.

N[1579/9232]

Visualizing heights

What happens if we plot height(n) for lots of positive integers n?

heightList=height/@Range[10000];
ListPlot[heightList,AxesLabel->{"n","height"}]

Do you see horizontal lines in the height plot? At what height values do these lines appear?

Looks like the most prominent horizontal line is at 9232.

computeTrajectory[9232]

Do you notice some diagonal lines in the height plot above? How can you explain these?

The lowest diagonal line appears to be height(n)=n. Let’s find the values of n such that height(n)=n:

heightList=height/@Range[1000];
nList=Position[
Table[heightList[[n]]==n,{n,1,Length[heightList]}],
True]//Flatten

Are these all multiples of 4?

Another diagonal line appears to be height(n)=3n+1.

Fix some large positive integer N. What proportion of positive integers n<N satisfy height(n)=n? Is this proportion stable as N increases?

Here is one way to do it:

heightList=height/@Range[30]
nList=Table[If[heightList[[n]]==n,1,0],{n,1,Length[heightList]}]
proportions=Table[Total[nList[[;;n]]]/n,{n,1,Length[heightList]}]

Now try it for larger N:

heightList=height/@Range[100000];
nList=Table[If[heightList[[n]]==n,1,0],{n,1,Length[heightList]}];
proportions=Table[Total[nList[[;;n]]]/n,{n,1,Length[heightList]}];

ListPlot[proportions,AxesLabel->{"n","proportion of height(n)=n for n <= N"}]

proportions[[-1]]//N

Fascinating! The proportion drops to about 10% (when N≈10000) before climbing slowly to about 14%.

Fix some large positive integer N. What proportion of values n<=N satisfy height(n)=3n+1? Is this proportion stable as N increases?

This can be approached in a similar way to the previous question.

What is the smallest height that occurs for more than 1579 different starting values?

Try computing height(n) for n up to 100,000:

heightList=height/@Range[100000];

ReverseSortBy[Tally[heightList],Last][[;;20]]

It appears that height 250,504 is quite common. Let’s compute height(n) for all n up to 250,504:

heightList=height/@Range[250504];

ReverseSortBy[Tally[heightList],Last][[;;20]]

We see that height 250,504 occurs for 1759 different starting values, and no smaller height occurs for more than 1759 starting values.

Write at least two good mathematical questions about the heights of Collatz sequences.

As we stated last time, a good mathematical question satisfies the following four characteristics:

The question is interesting to you.

It is not an question whose answer you already know.

It is not a question you've seen before, or at least not exactly.

It is a question about which you can begin to make computational investigations.

(These characteristics are from Barry Mazur and William Stein, Prime Numbers and the Riemann Hypothesis.)