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_]:=

Try it out:

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

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

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

Visualizing heights

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

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

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

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

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

What is the smallest height that occurs for more than 1579 different 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.)