Collatz sequences

(10 pts)

Let $n_1 \geq 1$ be an integer. We can make a new integer $n_2$ as follows:

• if $n_1$ is even, then $n_2 = n_1/2$

• if $n_1$ is odd, then $n_2 = 3n_1 + 1$

Repeating this, we obtain a sequence of integers $n_1, n_2, n_3, \dots$. Here is and example of such a sequence starting with $n_1 = 17$:

Collatz conjecture says, that no matter what the first integer $n_1$ is, this sequence will always reach the number 1. After that the sequence will start repeating:

This conjecture has been around for 90 years, but It is still not known if it is true or not. The goal of this project is to investigate sequences obtained in this way and make some observations about them.

Here is some terminology:

• A Collatz sequence is a sequence $n_1, n_2, \dots, n_k$ obtained as above, where $n_k = 1$, and it is the first occurence of 1 in this sequence.

• The stopping time of a Collatz sequence for an integer $n_1 \geq 1$ is the length of the Collatz sequence $n_1, n_2, \dots, n_k = 1$.

• The peak of a Collatz sequence is the largest integer in that sequence.

Project¶

Explore Collatz sequences and make some observations about them. Here are some ideas you may want to consider. Do not research all these suggestions, just pick a few. You can also choose entirely different questions that you find interesting.

• Find examples of some interesting Collatz sequences (e.g. especially long or short or with a very high peak compared to the starting number, etc.). Plot these sequences and make some observations about them.

• Plot stopping times for numbers up to some integer n. What do you see in the plot? Zoom in on some interesting areas.

• For an integer n, compute the average stopping time of all numbers smaller than n. How is this average changing with n? What about the maximum stopping time for numbers smaller than n?

• Which numbers give the shortest Collatz sequences? What about numbers that are immediately preceeding or succeding these numbers?

• Sometimes several consecutive numbers $n, n+1, n+2, \dots, n+k$ have the same stopping times. Find some examples of such numbers. How different are Collatz sequences for such numbers? Do they share a lot of numbers or are they mostly different?

• In Collatz sequences starting an integer smaller than n, on average what is the fraction of steps that
  increase the sequence? How does this change with n?

• For a given integer n, what are the biggest and the average values of peaks of sequences starting with k, for k smaller than n? How does this change as n increases?

• Let peak(k) denote the peak of the Collatz sequence that starts with k. Compute ratios peak(k)/k. What is the average of these ratios for all k smaller than some n? How does it change with n? How often does this ratio exceeed 10? 100? 1000?

• How many steps does it take for the Collatz sequence staring with n to reach its peak? How does it change with n?

• For a given number n, how many integers are there with the stopping time less than n? How does it change with n?