Are there specific numbers for which the Collatz Conjecture is proven?

Question

Obviously it is proven that all powers of 2 fall to one after applying the rules an arbitrarily large number of times. But are there some other subsets of natural numbers, for which the Collatz Conjecture has been proven? As some comments have pointed out there are some proofs by brute force for at least the natural numbers to 2^64. Are there other known subsets, not proved by brute forcing but because of a rigorous mathematical proof?

Answer 1

Odd numbers that are $k$ steps away from $1$ can be written that way: $$n_k=\frac{2^{l_1+l_2+...+l_k}}{3^k}-\frac{2^{l_2+l_3+...+l_k}}{3^k}-\frac{2^{l_3+l_4+...+l_k}}{3^{k-1}}-\frac{2^{l_4+l_5+...+l_k}}{3^{k-2}}-...-\frac{2^{l_{k-1}+l_k}}{3^3}-\frac{2^{l_k}}{3^2}-\frac{2^0}{3^1}$$ (see my comment here)

your case is a special case with $k=1$ and you already applied Collatz function "$3n+1$" on the odd number $n_1$, and you only need to apply the "$\frac{n}{2^{l_1}}$" function to your $n$ (a power of 2).

It can be easily proven that Applying the collatz rules on $n_k$ for any $k$ will lead to 1 (just apply $3n+1$ and $\frac{n}{2^{l_{k_i}}}$ to the $n_k$ till you reach 1) since the equation is build in reverse from 1.

The hard part is to prove that all odd integers are covered by this equation (for all $k$).

Answer 2

Let's look at congruence classes, modulo powers of $2$. We're interested in whether $f^{[k]}(n)<n$, for some positive $k$, where $f^{[k]}$ denotes the $k$-th iterate of the Collatz function. Choosing the least $k$ for which this inequality holds, we say that such a number "reduces in $k$ steps".

Does showing that a number $n$ reduces prove that $n$ eventually reaches $1$? Not quite. However, it does show that $n$ is not the smallest number that fails to reach $1$. If the Collatz conjecture is false, there is a least natural number $n_0$ for which it fails. That number has the property that $f^{[k]}(n_0)\ge n_0$ for all $k$. For numbers greater than $n_0$, reducing does not imply reaching $1$.

$2^1$:

Any number of the form $2k$ reduces in one step. We only need concern ourselves with numbers congruent to $1$, modulo $2$.

$2^2$:

The numbers from above are all congruent to $1$ or $3$ modulo $4$.

$n=4k+1 \rightarrow 12k+4\rightarrow 6k+2\rightarrow3k+1<n$,

so numbers congruent to $1$ modulo $4$ reduce in $3$ steps. With numbers congruent to $3$, though, we can't say:

$n=4k+3\rightarrow 12k+10\rightarrow6k+5\rightarrow 18k+16\rightarrow 9k+8\rightarrow \,\,\,???$,

so we lift again.

$2^3$:

The remaining numbers are all congruent to $3$ or $7$ modulo $8$.

$n=8k+3\rightarrow 24k+10\rightarrow 12k+5\rightarrow 36k+16\rightarrow 18k+8\rightarrow 9k+4\rightarrow \,\,\,???$

$n=8k+7\rightarrow 24k+22\rightarrow 12k+11\rightarrow 36k+34\rightarrow 18k+17\\\;\;\;\;\; \rightarrow 54k+52\rightarrow 27k+26\rightarrow \,\,\,???$

Bummer. Let's try $16$

$2^4$:

Everything is either $3,7,11$ or $15$, so...

$n=16k+3\rightarrow 48k+10\rightarrow 24k+5\rightarrow 72k+16\rightarrow 36k+8\rightarrow 18k+4\rightarrow 9k+2<n$

That reduced in $6$ steps, still need to check $16k+7, 16k+11$ and $16k+15$. None of them reduces here, so you end up starting with $6$ congruence classes to check, modulo $32$. Of those $6$, you'll find that $2$ of them reduce in $8$ steps, leaving $4$ congruence classes to lift to $8$ congruence classes, modulo $64$.

---

You can keep going this way, but it's like fighting Hercules' hydra, from Greek mythology. Extra heads keep growing faster than you can cut them off. However, this does feel like a result in the right direction. So far here, we've shown that anything equivalent to $1\pmod2, 1\pmod4$ or $3\pmod{16}$ reduces in a known number of steps.

Answer 3

If you ask for odd numbers $a$ which reduce in one odd step to $1$ then you can solve the equation $$\begin{array} {} {3a+1 \over 2^A} &=& 1\\ 3a+1 &=& 2^A \\ 3a &=& 2^A-1\\ a &=& {2^A-1\over 3} \end{array}$$ and you get an infinite set of numbers $a_A$ depending on any $A$'s which make the last rhs an odd integer.
For the infinite set of $A \in \{2,4,6,...\}$ we get an infinite set of $a \in \{1,5,21,85,341,... \}$ .

One can now observe, that the numbers of the (infinite) subsets $\{5,341,... \}$ and $\{1,85,...\}$ which are proven to fall down to $1$ by one odd step, can be taken as endpoint of another odd step, for instance $5$ $$\begin{array} {} {3b+1 \over 2^B} &=& 5\\ 3b+1 &=& 5 \cdot 2^B \\ 3b &=& 5 \cdot 2^B-1\\ b &=& {5 \cdot 2^B-1\over 3} \end{array}$$ and of course for the set $B \in \{1,3,5,7,...\}$ we get the infinite set $b \in \{ 3,13,53,... \}$
So this is another infinite set which is proven to fall down to $1$ - in this case by two odd steps.

Of course this can be done for $85$ instead of $5$ and it is very easy to define a lot of infinite sets of numbers which fall down to $1$ by one odd step, by two odd steps, by three odd steps and so on.

All these sets are infinite and thus do not have some "largest" element which must be determined empirically ...

For more illustration of this you might be interested in my small collection of textual and grafical trees at my early collatz-pages with the subpage on "grafical and textual trees".

See a screenshot of the "numerical tree" page. All rows in this Excel-generated sheet show the heads of infinite sequences of simple classes of numbers with geometric progression $a_{k+1}=4a_k + 1$ . For all those infinite sequences the Collatz-conjecture is immediately proven - the Collatz-transformation (in its Syracuse-formulation) goes in reverse direction of the arrows, for instance $3 \to 5$ and then inside the row which contains the $5$ left towards its head, which is $1$ and which is thus the root of the whole doubly infinite tree.

Answer 4

It can be easily shown that all numbers of the form $4k + 1$ will satisfy the conjecture provided that $k$ satisfies it.

$2^kn + 1$ also satisfies the conjecture if $n$ satisfies it, trivially.

Numbers of the form $$\frac{4^m - 1}{3}$$ lead to powers of $2$ and therefore to $1$.

$$\frac{4^mn - 1}{3}$$ leads to $1$ if $n$ leads to $1$.