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

     

    1. See below...

      21 → 64 → 32 → 16 → 8 → 4 → 2 → 1 ...

      13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 ...

      31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 ...

    2. Every number seems to generate a sequence that gets stuck in the loop 4, 2, 1, ...

    3. Consider the first 4 iterations:

      $8k+4 \rightarrow 4k+2 \rightarrow 2k+1 \rightarrow 6k+4$
      $8k+5 \rightarrow 24k+16 \rightarrow 12k+8 \rightarrow 6k+4$

      From there on, the sequences are identical, and thus get stuck in the loop 4,2,1 at the same time.

    4. Consider the first 4 iterations:

      $128k+28 \rightarrow 64k+14 \rightarrow 32k+7 \rightarrow 96k+22$
      $128k+29 \rightarrow 384k+88 \rightarrow 192k+44 \rightarrow 96k+22$
      $128k+30 \rightarrow 64k+15 \rightarrow 192k+46 \rightarrow 96k+23$

      Notice, the first two sequences have merged. Now consider the next 7 iterations:

      $96k+22 \rightarrow 48k+11 \rightarrow 144k+34 \rightarrow 72k+17\rightarrow$
      $ 216k+52 \rightarrow 108k+26 \rightarrow 54k+13 \rightarrow 162k+40$

      $96k+23 \rightarrow 288k+70 \rightarrow 144k+35 \rightarrow 432k+106 \rightarrow$
      $216k+53 \rightarrow 648k+160 \rightarrow 324k+80 \rightarrow 162k+40$

      So now, all three sequences have merged, which implies they will get stuck in the loop 4,2,1 at the same time.