Posted by Jason Polak on 29. January 2013 · Write a comment · Categories: number-theory · Tags: , ,

The 3n+1 conjecture (a.k.a. the Collatz conjecture) is easy to state, unsolved, probably difficult to prove if true, and can provide us with some pretty pictures. I’m only going to state it and show some pretty pictures.

First, what’s this conjecture? It’s about a simple algorithm: choose a positive integer $ n$. If $ n=1$, don’t do anything. Otherwise follow these instructions:

  1. If $ n$ is even, divide by $ 2$.
  2. If $ n$ is odd, multiply by $ 3$ and add $ 1$.

Do this to the result, and keep doing this until the result is 1. For instance, choose $ n=6$. We keep applying the steps above to get the numbers 6,3,10,5,16,8,4,2,1. The 3n+1 conjecture is that for any positive integer $ n$, this sequence always gets to 1.

For $ n=6$, it took eight steps to get to $ 1$. How does the number of steps depend one $ n$? No one knows a formula of course because no one knows whether every number can be reduced to $ 1$ by this process. However, we test a bunch of numbers, and draw graphs with $ n$ on the $ x$-axis and the number of steps on the $ y$-axis.

Let’s start with the first twenty numbers, which is probably the amount I’d do in the days before computers. Here’s what the number of steps looks like plotted against the first twenty positive integers:

FirstTwenty

There isn’t too much to see here, except some general trend of increase perhaps. However, this is what happens when we look at the first thousand:

FirstThousand

It seems as though distinct curves are appearing in this picture. Could these curves be the secret to unlocking the conjecture? Let’s look some more! Here is the first fifty thousand:

FiftyThousand

This plot is large, and I decreased the point size of the graph because otherwise it looks like a mess of squid ink. What happens if we try and average out the process: let $ A_{k}(n)$ denote the average number of steps to $ 1$ for the integers from $ n-(k-1)$ to $ n$; that is, the last $ k$ positive integers up to $ n$. Of course, this is only defined for $ n$ and greater. Here is what $ A_{20}(n)$ looks like from $ n=20$ to $ n=1019$:

A_20_1000

It’s still pretty chaotic. What about $ A_{500}(n)$? Here is a picture:

A_500_1000

Even though it looks more controlled, there is still some odd looking behaviour as the function increases. What if we look at $ n=500$ to $ n=12499$? Here it is:

A_500_12000

Those are some pretty weird looking patterns near the end of this one! Here are all the numbers up to 99999:

A_500_100000

It’s easy to think of many more data, graphs, and analyses to extract from this problem, but I’ll leave this post with one final observation: one sees upon looking at the data file directly some unusual patterns. For instance, the numbers 99984 to 99992 all take the same number of steps (159) to get to one. Moreover, these repeat numbers occur very frequently as the numbers start getting large. This is somewhat unusual, at least to yours truly, because this process depends upon the factors of the numbers at each stage, so I would have expected there to be not much in common between $ n$ and $ n+1$, though perhaps I don’t perceive the subtlety of this situation. Another shocking example is from 10634 to 10650 (17 numbers), all of which take 55 steps!! Moreover, there are multiple repeats of 55 near these numbers.

Could some pattern be revealed by examining these repeated step lengths? Suppose I take the list of path lengths, and replace each block of repeated digits by the number of repeats. Hence this block:

would be replaced by:

What would a plot of these numbers look like? First, I’ll mention that between 1 and 99999 the longest length of consecutive integers that have the same path number is 25. Here is a plot of the first five thousand numbers in this list (note, now the $ x$-axis does not correspond to $ n$):
PathLength5000

Here are the frequencies for the number of times a length $ p$ path is repeated amongst consecutive integers, for $ p=1$ to $ p=25$, for the integers up to 99999:

A good question is: do all positive integers eventually occur?

Further Exploring

It’s not hard to think of many more graphs, analyses, and question that can be extracted from this problem. Perhaps, if someone does enough exploring, some hidden elegant pattern will emerge that will lead to a proof of the 3n+1 conjecture.

You can download the data set set that I used, which I calculated from a simple program that I wrote in C.

Leave a Reply

Your email address will not be published. Required fields are marked *