Why does this pattern emerge: k iterations of collatz mod 2

Question

Let $f(n)$ denote the Collatz-function: $$ f(n) = \begin{cases} n/2, & \text{if $n$ is even} \\ 3n+1, & \text{if $n$ is odd} \end{cases}$$ Let $C^k$ denote a sequence, where the $i$th element is the $i$th natural number after $k$ iterations of $f\bmod 2$, say: $$C^k_i=\underbrace{f(f(f(i)))}_{k\text{ times}}\mod 2$$ So $$C^1 = \{0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,\ldots\}$$ $$C^2 = \{0,0,1,1,0,0,1,0,0,0,1,1,0,0,1,0,\ldots\}$$ $$C^3 = \{1,0,0,0,0,1,0,1,1,0,0,0,0,1,0,0,\ldots\}$$

Cycles can be found in these sequences, in particular it seems that the cycles are always of length $2^{k+1}$.

The question: Isn't this somehow surprising, given how seemingly random the collatz sequence for a given integer looks like? Or is the presence of a repeating pattern and its doubling in length because of something trivial at work here?

Please excuse the possibly confusing explanation, but I am very non-fluent in 'mathspeak'. A more formal notation for the idea of $C^k$ would be highly appreciated.

Answer 1

Here's what I hope is a nicely non-technical way to see what's going on here. Let's pick a power of $2$, say, $8=2^3$. Now, every natural number can be written in one of the forms: $8n, 8n+1, 8n+2,\ldots,8n+7$. Let's pick one of these, say, $8n+5$. When we start applying the Collatz function, we know what happens for the first few steps, without having to know what $n$ equals:

$$8n+5\rightarrow 24n+16 \rightarrow 12n+8 \rightarrow 6n+4 \rightarrow 3n+2$$

As soon as we get to $3n+2$, we have to stop, because whether that number is even or odd depends on what $n$ equals.

Here's another sequence: $$8n+3\rightarrow 24n+10 \rightarrow 12n+5 \rightarrow 36n+16 \rightarrow 18n+8 \rightarrow 9n+4$$

Again, as soon as the coefficient in front of $n$ is not even, we can't continue.

Here's one more, which is a "worst case scenario", in terms of how far we can look ahead: $$8n\rightarrow 4n \rightarrow 2n \rightarrow n$$

In any event, we know whether the first and second steps after our original number are even or odd, and that answer doesn't depend on $n$. Thus, if you list $f^2(i)\bmod 2$, it will be $0$ for every number of the form $8n$, it will be $1$ for every number of the form $8n+3$, and it will be $0$ for every number of the form $8n+5$. These agree with your list $C^2$.

If we had started out writing numbers in the forms $16n, 16n+1$, etc., then we would be able to see reliably three steps ahead, instead of just two. That's because, starting with a coefficient of $16$, we can divide the coefficient by $2$ three times, and still know whether we're looking at an even or odd number. Thus, $C^3$ repeats every $16$ steps.

I hope this makes sense; if you have any questions, feel free to ask them in the comments. :)

---

As far as a more formal notation for $C^k$, it can be defined formally this way: $$\{C^k_i\}_{i\ge 1}=f^k(i)\bmod 2,$$

where we're using $\bmod$ to indicate the usual computer operation of sending a number to its remainder when divided by $2$.

Answer 2

It's just induction. Let's define $C_k(i) = f^k(i) \bmod{2}$. Clearly, $C_0$ is periodic with a period of $2$. Now, assume $C_{k}$ is periodic with period $2^{k+1}$.

Pick $n \in \mathbb{N}$. If $n = 2m$ is even, then $n + 2^{k+2} = 2m+2\cdot2^{k+1}$ is also even. Then

$$\color{blue}{C_{k+1}(n)} = C_k(m) = C_k(m+2^{k+1}) = C_{k+1}(2m + 2\cdot2^{k+1}) = \color{blue}{C_{k+1}(n+2^{k+2})}$$

Now, if $n$ is odd, then

$$ \begin{align} \color{blue}{C_{k+1}(n)} = C_k(3n+1) = C_k(3n + 1 + 2^{k+1}) &= \\ C_k(3n+2^{k+1}+\color{purple}{5\cdot 2^{k+1}}+1) &= \\ C_k(3n+1+ 6\cdot 2^{k+1}+1) &= \\ C_k(3n+ 3 \cdot 2^{k+2}+1) &= \\ \color{blue}{C_{k+1}(n + 2^{k+2})} \end{align} $$ Thus, $C_{k+1}(n) = C_{k+1}(n+2^{k+2})$. This completes the induction.

---

Conclusion: Nothing special about the Collatz configuration is required for this to be true. Also, we may be stronger; for odd $n$ and $k > 0$,

$$C_{k}(n) = C_k(n+2^{k})$$