I was working on the Collatz conjecture(while not expecting to get anywhere) and I suspect that if it is possible to show that $$\dfrac{2^k - (2\cdot3^{n-1} + 2^{t_0}3^{n-2} + 2^{t_0+t_1}3^{n-3} .... + 2^{t_0+t_1+...+t_{n-2}})}{3^n}$$ can represent all integers for some $k, n$ and $t_i$s, it is possible to prove the Collatz conjecture. If $t_0 \geq 1$ and $t_i > 1$ for $i>0$, $i\in \mathbb{Z}^+$

While I am aware that there is no easy way to actually prove this, I was hoping for a recommended method of approaching this problem. If requested, I will put the derivation below. However, even if the derivation is incorrect, I am still interested in whether there is a way to prove or disprove that the above can represent all integers. I have only tried one approach so far and I will put it below(even if I was unsuccessful). If this has not been a simplification, I will appreciate if that was pointed out as well.

Proof by induction

Given $$z = \dfrac{2^k - (2\cdot3^{n-1} + 2^{t_0}3^{n-2} + 2^{t_0+t_1}3^{n-3} .... + 2^{t_0+t_1+...+t_{n-1}})}{3^n}$$ must satisfy $z \in \mathbb{Z}^+$. At $z=1$, as $$1 = \dfrac{2^4-(2\cdot3 + 2^0)}{3^2} = \dfrac{9}{9} = 1$$ I here assumed that at $z=a$, $$a = \dfrac{2^k - (2\cdot3^{n-1} + 2^{t_0}3^{n-2} + 2^{t_0+t_1}3^{n-3} .... + 2^{t_0+t_1+...+t_{n-1}})}{3^n}$$ Here, if we were to look at $z=a+1$, $$a+1 = \dfrac{2^k + 3^n- (2\cdot3^{n-1} + 2^{t_0}3^{n-2} + 2^{t_0+t_1}3^{n-3} .... + 2^{t_0+t_1+...+t_{n-1}})}{3^n}$$ However, I was not able to think about anything from this point.


As it was requested, I will include a derivation. I apologize in advance for the lack of advanced mathematics. Also, since I have not went to university yet, I most likely will be lacking in my techniques of conveying the derivation or the formalness of the proof so I will apologize in advance for that too.

That said, here is the derivation. I tried to look at the number of odd cycles required to reach 1 for a particular number. For example, given an odd number $x$, $$ \dfrac{3x + 1}{2^{t_0}} = 1$$ then all number in the form of x will reach one in one cycle. The x is given by $$x= \dfrac{2^{t_0}-1}{3}$$ Given two cycles, all $x$s in the form $$\dfrac{3\dfrac{3x+1}{2^{t_0}}+1}{2^{t_1}} = \dfrac{9x + 3 + 2^{t_0}}{2^{t_0+t_1}} = 1$$ will lead to 1. The $x$ is given by Thus given n cycles, the x that will lead to reaching 1 can be given by $$\dfrac{3^nx + 3^{n-1} + 2^{t_0}3^{n-2}+2^{t_0+t_1}3^{n-3}...+2^{t_0 +t_1+....+t_{n-2}}}{2^{t_0+t_1+t_2....+t_{n-1}}}=1$$ Thus, when solving for $x$, $$ x = \dfrac{2^{t_0+t_1+t_2....+t_{n-1}}-(3^{n-1} + 2^{t_0}3^{n-2}+2^{t_0+t_1}3^{n-3}...+2^{t_0 +t_1+....+t_{n-2}})}{3^n}$$ To make it account for every integer, given $n \in \mathbb{Z}$ $$ 2n+1 = \dfrac{2^{t_0+t_1+t_2....+t_{n-1}}-(3^{n-1} + 2^{t_0}3^{n-2}+2^{t_0+t_1}3^{n-3}...+2^{t_0 +t_1+....+t_{n-2}})}{3^n}$$ Thus $$n = \dfrac{2^{t_0+t_1+t_2....+t_{n-1}}-3^n-(3^{n-1} + 2^{t_0}3^{n-2}+2^{t_0+t_1}3^{n-3}...+2^{t_0 +t_1+....+t_{n-2}})}{2\cdot3^n}=\dfrac{2^{t_0+t_1+t_2....+t_{n-1}}-(4\cdot3^{n-1} + 2^{t_0}3^{n-2}+2^{t_0+t_1}3^{n-3}...+2^{t_0 +t_1+....+t_{n-2}})}{2\cdot3^n}= \dfrac{2^{t_0+t_1+t_2....+t_{n-1}-1}-(2\cdot3^{n-1} + 2^{t_0-1}3^{n-2}+2^{t_0+t_1-1}3^{n-3}...+2^{t_0 +t_1+....+t_{n-2}-1})}{3^n}$$ Thus, when writing $k= t_0+t_1+t_2....+t_{n-1}-1$ I think it reaches the above expression.

  • $\begingroup$ This ansatz is well known, and there have been several attempts to prove that indeed all numbers can be represented by this structure - but with no success so far. Only with restrictions on the sequence of $t_0,t_1,...$ some progress could be made, for instance if all $t_k$ except the last would equal $1$ this leads to the "1-cycle"-problem and there has been some success with analyses on this (proof of nonexistence etc). $\endgroup$ – Gottfried Helms Jul 24 '18 at 12:25
  • $\begingroup$ Ah, got it. Thank you very much! @GottfriedHelms ! $\endgroup$ – Isamu Isozaki Jul 25 '18 at 21:04
  • $\begingroup$ I'll try another approach! $\endgroup$ – Isamu Isozaki Jul 25 '18 at 21:05
  • $\begingroup$ Yes, this looks equivalent to some previously-discovered representations of the Collatz problem, which are summarised fairly exhaustively by Lagarias' well-known paper. I think this equation is more revealing once you have divided the numerator throughout by $3^n$ and you can also express $t_0..$ as individual terms of a strictly increasing sequence of powers of $2$. My personal opinion is not to give up on this approach, rather I prefer to better understand what forms of such sequences are possible, and how they can be put into bijection with the integers. $\endgroup$ – samerivertwice Jul 26 '18 at 11:37
  • 1
    $\begingroup$ @RobertFrost Oh, that is quite interesting! I have not yet read that famous paper and I do not understand the second portion completely yet I will read it and I will give it another try! I have tried another approach yet while I think I made a bit of progress, I was actually thinking about finding another method like the one here. Thank you! $\endgroup$ – Isamu Isozaki Jul 28 '18 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.