# 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
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 50, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://mathoverflow.net/questions/435652/reference-on-the-collatz-conjecture", "fetch_time": 1674898784000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2023-06/segments/1674764499541.63/warc/CC-MAIN-20230128090359-20230128120359-00778.warc.gz", "warc_record_offset": 386416908, "warc_record_length": 21856, "token_count": 1511, "char_count": 3776, "score": 3.5625, "int_score": 4, "crawl": "CC-MAIN-2023-06", "snapshot_type": "latest", "language": "en", "language_score": 0.4672603905200958, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00039-of-00064.parquet"}