3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you very much, a nice explanation. So it's really just something trivial as I've feared. :) $\endgroup$ – SmallestUncomputableNumber May 23 '18 at 15:33
  • 1
    $\begingroup$ Eh, you know. You can actually get some mileage out of this kind of analysis. If you're looking for a counterexample to the conjecture, then there is some number $n_0$ that is the least number failing to reach $1$. We know that $f^k(n_0)\ge n_0$ for every $k$, so, for example, $n_0$ cannot be even. Looking at the examples above, it can't be of the form $8n+5$, either, because $f^3(8n+5)=6n+4$, which is less than $8n+5$. This path doesn't lead to a proof, but it does narrow the classes of numbers where one would look for a counterexample. $\endgroup$ – G Tony Jacobs May 23 '18 at 16:36
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.