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)$.

◆ ◆ ◆