# Alternative formulation of the Collatz problem

Just for the sake of interest, I have realized that the additive step in the Collatz function can be technically avoided when computing the function iterates.

Rather than defining the Collatz function as $$T_0(n) = \begin{cases} (3n + 1)/2 &\quad \text{ if n \equiv 1 \pmod{2},} \\ n/2 &\quad \text{ if n \equiv 0 \pmod{2},} \end{cases}$$ and tracking the trajectory directly on $$n$$, one can track the same trajectory on $$n+1$$ with the function $$T_1(n) = \begin{cases} (n+1)/2 &\quad \text{ if n \equiv 1 \pmod{2},} \\ 3n/2 &\quad \text{ if n \equiv 0 \pmod{2}.} \end{cases}$$ Thus the "multiplying by 3" just moved to the "even" branch.

The trick is that, when calculating the function iterates, we switch between $$n$$ and $$n+1$$ in such a way that we always use only the "even" branch of either $$T_0$$ or $$T_1$$. Therefore, the above functions can be expressed as $$T_0(n) = \begin{cases} T_1(n+1)-1 &\quad \text{ if n \equiv 1 \pmod{2},} \\ n/2 &\quad \text{ if n \equiv 0 \pmod{2},} \end{cases}$$ and $$T_1(n) = \begin{cases} T_0(n-1)+1 &\quad \text{ if n \equiv 1 \pmod{2},} \\ 3n/2 &\quad \text{ if n \equiv 0 \pmod{2}.} \end{cases}$$

There are seemingly still two additions. However, considering the binary representation of the $$n$$, these additions can be avoided using right shifts and operations which count the number of one/zero bits following the least significant zero/non-zero bit. The powers of three can be precomputed in a look-up table.

I am just interested in knowing whether this formulation has appeared before? Is this a special case of some other known (more general) recurrence relation? Any feedback is welcome.

UPDATE: Some simple code to illustrate my idea can be found here. Currently, I am able to verify the convergence of all numbers below $$2^{40}$$ in approximatelly 4 minutes (single-threaded program running at 2.40GHz CPU).

• I could mention that the oddness and evenness is unimportant in the sense that the entire Collatz function can be transformed into a boolean equivalent where any even binary number is expressed as the input to the function, where $2n$ is the mapping to any odd and even input. There is a special to do this, but I leave that as an exercise, because there are many different ways to do this. So afaik the $3$ multiplier is not really that relevant if you study it from internal mechanics standpoint (in binary). I find that we don't need to find the exponent, but compute it using the xor-operation. Aug 2 '19 at 15:54
• Sorry, but I am not sure that such cosmetic transformations make you progress towards the goal. I prefer the definition with odd numbers only (discarding the trailing zeroes every time), but again, this doesn't make the resolution any simpler.
– user65203
Aug 3 '19 at 13:24
• @YvesDaoust Anyhow, I can check all numbers below 2^31 in about six seconds using the simple code I have linked (single threaded, 2.4 GHz CPU). Aug 4 '19 at 12:42
• Your code looks similar to $\frac{3^Un+3^U-2^U}{2^U}$ found here youtu.be/lNzzlFWWiDo?t=344, in the video he talks about cycles, but I noticed if you plug in odd n, and replace U with the number of trailing ones in n, you get the next 2 mod 6 number in n's collatz sequence. Aug 5 '19 at 14:12
• @YvesDaoust According to this paper from 2017, the authors can verify the convergence for all numbers below $2^{32}$ in about a second (using a CPU implementation). So at least, I'm not so far away from the state-of-the-art... Aug 5 '19 at 17:06

Answer to @BaBler's comment. The formula for finding trailing zeros is: $$n\oplus(n-1)$$, i.e., in Boolean form. To get a pow$$2$$ number we must add $$+1$$ to that or else it will just give trailing $$1$$'s. We must then subtract $$1$$ from the result and take the base $$2$$ logarithm. Here is the complete form:

$$v_2(n)=\log_2(n\oplus(n-1))$$

$$C(n) = \frac{3n+1}{2^{v_2(3n+1)}}$$

Input to this function must (only) be odd numbers: $$2n+1$$.

Code

n = (3 * n + 1) >> (int)log2((3 * n + 1) ^ (3 * n));


Since $$n\oplus(n-1)$$ gives $$2^x-1$$, the $$\log_2$$ rounds off to nearest exponent which is actually the number of trailing zeroes.

This is also known as the Reduced Collatz Function.

• We did not actually need to add $1$ to the result of the xor. Because it's integer operation. Aug 3 '19 at 13:00
• This seems to be incredibly inefficient way to compute the number of trailing zeros (which is a single instruction in modern CPUs). Have I missed somethink? Aug 4 '19 at 13:04
• If you are only out after efficiency on modern CPUs then you should stick to what you think is best. Aug 4 '19 at 19:51