3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Yes, the set $\{1,2,3,\ldots,2^{64}\}$. en.wikipedia.org/wiki/Collatz_conjecture#Experimental_evidence $\endgroup$ – Rahul Mar 31 '18 at 15:21
  • $\begingroup$ As well as 5 times any of those numbers. $\endgroup$ – Ittay Weiss Mar 31 '18 at 15:22
  • $\begingroup$ But this has been done by brute force computation, hasn't it? $\endgroup$ – Mister Set Mar 31 '18 at 15:24
  • 1
    $\begingroup$ You should edit your question if you want to exclude that; a proof is just an expression that undeniably verifies whatever you are claiming; in this case, writing out the sequence that the algorithm generates and showing it terminates is a perfectly valid proof. (You may find it to be quite inelegant though) $\endgroup$ – E-A Mar 31 '18 at 15:40
  • 3
    $\begingroup$ Possible duplicate of Are there any partial proofs for the collatz conjecture? $\endgroup$ – samerivertwice Jul 1 '18 at 8:35
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I like this, but you should explain why you have to give up on "reducing" a class, and split it into 2 classes, when the coefficient on k becomes odd. When I tried it this way, eventually the powers of 3 in the coefficient overcame the powers of 2 and you stopped being able to reduce any classes at all. $\endgroup$ – Spencer Nov 12 '18 at 19:55
  • $\begingroup$ Yes, that's exactly what happens. I guess I thought that was apparent from the examples, where the coefficients start as numbers like $8$ and $16$, and gradually lose all their $2$'s in favor of $3$'s, turning into numbers like $9$ and $27$. $\endgroup$ – G Tony Jacobs Mar 7 at 11:05
1
$\begingroup$

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.

image

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.