Heights of Collatz Trajectories

Math 242 Modern Computational Mathematics

Preliminary Code

First we define the Collatz function col(n).

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

Here is a module to compute the Collatz trajectory with some starting value n. The loop in this module stops when either a 1 is reached or the trajectory contains maxIter terms. Note that maxIter is an optional parameter with default value 100000.

computeTrajectory[start_,maxIter_:100000]:=Module[{traj={start},n=start},
(* compute the trajectory until we find 1 *)
While[n!=1&&Length[traj]<maxIter,
n=col[n];
AppendTo[traj,n];
];
(* return the trajectory *)
traj
]

Try it out:

traj=computeTrajectory[27]

Here is a function to plot Collatz trajectories. The input to this function should be a trajectory, supplied as a list of integers.

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

plotTrajectory[traj]

Verify the Collatz Conjecture up to n=10000

Example :

Last[computeTrajectory[27]]==1

Table[Last[computeTrajectory[n]]==1,{n,1,10}]

Compute 10000 True/False values and compare them to table of 10000 True values

verificationResults=Table[Last[computeTrajectory[n]]==1,{n,1,10000}]

verificationResults==Table[True,10000]

Asking good mathematical questions

Asking good mathematical questions is not only an art, but also an important skill to develop. A good mathematical question:

is interesting to you;

is not an question whose answer is known to you;

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

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

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

Today we will practice asking good mathematical questions about Collatz trajectories, and specifically about heights of Collatz trajectories.

Heights of Collatz trajectories

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

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

Try it out:

height[27]

computeTrajectory[27]

Let's compute heights for n from 1 to 20:

heightList=height/@Range[20]

computeTrajectory[3]

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

list16=Position[heightList,16]//Flatten

computeTrajectory/@list16

What is the most common height for starting values up to 100?

heightList=height/@Range[100]

Tally[heightList]

ReverseSortBy[Tally[heightList],Last]

Now go up to 10000:

heightList=height/@Range[10000];
ReverseSortBy[Tally[heightList],Last]

Plot the heights

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

What proportion of n have height(n)=n?

heightNList=Table[heightList[[n]]==n,{n,1,1000}];

Take[heightNList,20]

Count[heightNList,True]/1000

How does this proportion change with n?

proportions=Table[Count[heightNList[[;;n]],True]/n,{n,1,1000}];
ListPlot[proportions,AxesLabel->{"N","proportion with height(n)=n for n<=N"}]