Exercises - The Collatz Conjecture

1. Suppose we define $f(x)$ in the following way, for positive integers $x$:
$$f(x)= \left\{ \begin{array}{ll} x/2 & \textrm{ if x is even}\\ 3x+1 & \textrm{ if x is odd}\\ \end{array} \right.$$
1. Construct the sequence of values $a_0, a_1, a_2, ...$ so that $a_0 = n$ and $a_{i+1} = f(a_{i})$. Verify that this sequence ultimately gets stuck in the loop 4, 2, 1, 4, 2, 1, ... for the following values of $n$:

1. $n=21$
2. $n=13$
3. $n=31$
2. Find the sequence described in part (a) for other values of $n$. What do you notice?

3. Suppose we use $L(n)$ to denote the position where $1$ first occurs in the sequence so generated and starting with $n$. Show that if $n=8k+4$, then $L(n)=L(n+1)$.

4. Show that if $n=128k+28$, then $L(n)=L(n+1)=L(n+2)$.

◆ ◆ ◆