# Reference on the Collatz conjecture [closed]

I'm just looking for references in the literature for some observations I made for fun about the Collatz conjecture.

The Collatz conjecture states that any positive integer $$n$$ can eventually be reduced to $$1$$ by applying this sequence $$n_{i+1}=3 \cdot n_i+1$$ if $$n_i$$ is odd and $$n_{i+1}=n_i/2$$ if $$n_i$$ is even.

Considering that if $$n=2^a$$ then it is obviously verified.

Considering that if $$n=2^a \cdot m$$ with $$m$$ odd then the verification of only odd numbers can be reduced.

Considering that if $$m$$ odd and $$m=\frac{4^a-1}{3}$$ with $$a>1$$ then is verified, in fact $$3 \cdot m+1=4^a$$

If $$m$$ odd and $$m \not = \frac{4^a-1}{3}$$ I tested up to $$100000$$ that the sequence always reaches a number equal to $$n_i=\frac{4^b-1}{3}$$ with an appropriate $$b>1$$ .

What I noticed is that considering $$m$$ odd the sequence can be modified in this way:

$$n_{i+1}=\frac{3 \cdot n_i+1}{2} \quad$$ if $$\quad n_i \equiv 3 \pmod 4$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{4} \quad$$ if $$\quad n_i \equiv 1 \pmod 8$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{8} \quad$$ if $$\quad n_i \equiv 13 \pmod {16}$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{16} \quad$$ if $$\quad n_i \equiv 5 \pmod {32}$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{32} \quad$$ if $$\quad n_i \equiv 53 \pmod {64}$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{64} \quad$$ if $$\quad n_i \equiv 21 \pmod {128}$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{128} \quad$$ if $$\quad n_i \equiv 213 \pmod {256}$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{256} \quad$$ if $$\quad n_i \equiv 85 \pmod {512}$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{512} \quad$$ if $$\quad n_i \equiv 853 \pmod {1024}$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{1024} \quad$$ if $$\quad n_i \equiv \frac{2^{10}-1}{3} \pmod {2048}$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{2048} \quad$$ if $$\quad n_i \equiv \frac{5 \cdot 2^{11}-1}{3} \pmod {4096}$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{4096} \quad$$ if $$\quad n_i \equiv \frac{2^{12}-1} {3} \pmod {8192}$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{8192} \quad$$ if $$\quad n_i \equiv \frac{5 \cdot 2^{13}-1}{3} \pmod {16384}$$

$$\cdots$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{2^{2 \cdot x}} \quad$$ if $$\quad n_i \equiv \frac{2^{2 \cdot x}-1} {3} \pmod {2^{2 \cdot x+1}}$$

$$n_{i+1}=\frac{3 \cdot n_i+1}{2^{2 \cdot x+1}} \quad$$ if $$\quad n_i \equiv \frac{5 \cdot 2^{2 \cdot x+1}-1}{3} \pmod {2^{2 \cdot x+2}}$$

Can anyone give me some pointers on where to look further?

Edit: Just to elaborate but if you write the remainders in binary you have

3:   11
13:  1101
53:  110101
213: 11010101
...

1:   1
5:   101
21:  10101
85:  1010101
...


to find the next element of the sequence, a simple algorithm can be implemented which analyzes the binary number starting from the least significant bit in pairs and stops when 11, 00 or 01 is reached.

Example:

void collatz(unsigned long long n) {
while ((n & 1) == 0 && n > 1)
n >>= 1;
while (n != 1)
{
while ((n & 3) == 1 && n > 3)
n >>= 2;
if ((n & 3) == 3)
n = (3 * n + 1) / 2;
else if (n != 1)
n = 3 * n + 1;
}
std::cout << n << '\n';
}

• Note that you also have that $\quad n_{i+1} \equiv 1 \pmod {6}$ in the first case and $\quad n_{i+1} \equiv 5 \pmod {6}$ in the second (math.stackexchange.com/questions/2527924/…) Dec 1, 2022 at 19:21
• for the edit: This is linked to the well known fact that the branch values are found by multiplying by 4 (a shift of 2 bits) and adding 1 to the previous value (13=4*3+1, 53=13*3+1,...) Dec 2, 2022 at 16:11
• @Collag3n I mean how to find the remainder modulus 2^a of any odd number and compare it to one of the ones in the formula. Dec 2, 2022 at 16:15
• Simply transform $n_{i+1}^*=3n_i+1$ and use the "valuation" $A=\nu_2(n_{i+1}^*)$ and then the $A$ gives you the group-index/modular class .... Dec 2, 2022 at 21:49