Collatz Patterns

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 it repeats maxIter times, which prevent us from possibly running an infinite loop or a loop that takes a very long time to finish. This module also implements Algorithm 3.4 in the text.

computeTrajectory[start_,maxIter_:100000]:=Module[
(* initialize variables *)
{curr=start,traj={start},counter=0},

(* compute the trajectory until we reach a 1 *)
While[curr!=1,
curr=col[curr];
AppendTo[traj,curr];
If[counter>=maxIter,Break[]] (* quit if the length of the trajectory reaches maxIter *)
];

(* return the trajectory *)
traj
]

Test this module:

computeTrajectory[27]

Plotting trajectories

Here is a module called plotTrajectory that makes a nice plot of a Collatz trajectory.

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

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

Here is a simple function that computes the height of a Collatz trajectory:

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

Try it out:

computeTrajectory[15]
height[15]

In the reading for today, you should have noticed the plot of height(n) for lots of positive integers n. We can now make this plot for ourselves, as follows.

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

Note that for plots with lots of graphical elements, Mathematica may get bogged down with all of the interactive visualization effects. It’s useful to disable these effects by adding the PlotHighlighting→None option.

Investigate the following questions. Use computation to precisely identify features that you notice in the Collatz height plot. Discuss your observations with your neighbors.

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

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

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

Stopping time of Collatz trajectories

For any positive integer n, define stop(n) to be the number of iterations of the function col required to reach 1 from n. This is one less than the length of the list returned by our computeTrajectory function.

stop[n_]:=

Let’s compute some stopping times:

computeTrajectory[10]
stop[10]

We can also make a list of stopping times for the first 20 starting values:

stop/@Range[20]

We can use Tally to find some common stopping times:

stopList=stop/@Range[50];
Tally[stopList]

ReverseSortBy[Tally[stopList],Last]

Visualizing stopping times

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

stopList=stop/@Range[2000];
ListPlot[stopList,AxesLabel->{"n","stop(n)"},PlotHighlighting->None]

What do you notice about the stopping time plot? What questions does this prompt you to ask?

Horizontal line segments?

Some of the dots in the stopping time plot appear to form small horizontal line segments. Why is this?

Detecting streaks (consecutive identical values) in a list

How can we detect streaks of consecutive identical values in a list? We can iterate through list, remembering the length of the current streak in the variable currStreak. Whenever we encounter a new value, set currStreak = 1. Whenever we encounter a repeated value, increment currStreak. The following code cell implements this idea, which is also found in Algorithm 3.9 in the text.

detectStreak[vals_,k_]:=Module[
(* initialize variables *) 
{currStreak=1,currPos=2},

(* main loop *)
While[currPos<=Length[vals],
If[vals[[currPos]]==vals[[currPos-1]],currStreak=currStreak+1,currStreak=1];
If[currStreak==k,Break[]];
currPos=currPos+1
];

(* return value *) 
If[currStreak==k,currPos-currStreak+1,False]
]

Try it out:

detectStreak[{5,7,2,2,2},3]

Now search for streaks in the list of Collatz stopping times. What is the longest streak that you can find?

Write at least two good mathematical questions about 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.)