2
$\begingroup$

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';
}
Improve this question
$\endgroup$
4
  • $\begingroup$ 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/…) $\endgroup$
    – Collag3n
    Dec 1, 2022 at 19:21
  • $\begingroup$ 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,...) $\endgroup$
    – Collag3n
    Dec 2, 2022 at 16:11
  • $\begingroup$ @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. $\endgroup$
    – user140242
    Dec 2, 2022 at 16:15
  • $\begingroup$ 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 .... $\endgroup$
    – Gottfried Helms
    Dec 2, 2022 at 21:49

1 Answer 1

Reset to default
15
$\begingroup$

A source book for serious study of the problem (as opposed to amateur)

Lagarias, Jeffrey C. (ed.), The ultimate challenge. The (3x+1) problem. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4940-8/hbk). (2010).

Improve this answer
$\endgroup$
1

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