2
$\begingroup$

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

$\endgroup$
13
  • $\begingroup$ 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. $\endgroup$ Aug 2 '19 at 15:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – user65203
    Aug 3 '19 at 13:24
  • 1
    $\begingroup$ @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). $\endgroup$
    – DaBler
    Aug 4 '19 at 12:42
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 5 '19 at 14:12
  • 1
    $\begingroup$ @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... $\endgroup$
    – DaBler
    Aug 5 '19 at 17:06
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ We did not actually need to add $1$ to the result of the xor. Because it's integer operation. $\endgroup$ Aug 3 '19 at 13:00
  • $\begingroup$ 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? $\endgroup$
    – DaBler
    Aug 4 '19 at 13:04
  • $\begingroup$ If you are only out after efficiency on modern CPUs then you should stick to what you think is best. $\endgroup$ Aug 4 '19 at 19:51

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.