Let us start with the list: $\{1\}$.

Every iteration replace every element $x$ in the list with two elements $2x$ and $\frac {x-1}{3}$.

Conjecture: The sum of every element of the set formed by the $N$th iteration is $2^N$.

Also, as a lesser corollary:

Corollary: The number of elements in the $N$th iteration is $2^N$.

I was just messing around with reversal of the Collatz Conjecture and adding together these sets and it kept occurring. I did it for the first 20-30 iterations and it seems to be a valid conjecture. I just don't know how to prove it. Can anyone demonstrate a simple proof showing why this is true? I don't want anything too advanced. I know the basic concepts of number theory/algebraic number theory/modular arithmetic but not much beyond that.

(Please don't tell me this is somehow equivalent to the Collatz Conjecture)


1 Answer 1


Whatever you did with your first 20-30 iterations must have been wrong.

The third iteration gives you the set $$ \left\{-\frac23, -\frac49, -\frac13, -\frac29, 0, \frac23, 1, 8\right\},$$ which has $8$ elements, and yes, the sum of the elements is also $8$.

Now, note that $$2 \cdot 0 = 0 \text{ and } \frac{1-1}{3} = 0,$$ and similarly $$2 \cdot \left(-\frac29\right) = -\frac49 \text{ and } \frac{-\frac13 - 1}{3} = -\frac49.$$ Because of this, the fourth iteration becomes $$ \left\{-\frac43, -\frac89, -\frac23, -\frac59, -\frac{13}{27}, -\frac49, -\frac{11}{27}, -\frac13, -\frac19, 0, \frac43, 2, \frac73, 16\right\},$$ which has $14$ elements and their sum is $148/9$.

  • $\begingroup$ Perhaps the OP is counting elements in a multi-set, with multiplicity, so that the fourth iterate has two $0$'s and two $-4/9$'s. (If so, the question should be edited to say so.) $\endgroup$ Jul 9, 2017 at 19:18
  • 1
    $\begingroup$ @BarryCipra In that case, the second corollary would be trivial, though. The first one could then be proven by induction. If $\sum_{i=1}^{2^N}x_i = 2^N$, then $$\sum_{i=1}^{2^N} 2x_i = 2\sum_{i=1}^{2^N} x_i = 2 \cdot 2^N = 2^{N+1}$$ and $$\sum_{i=1}^{2^N} \frac{x_i-1}{3} = \frac{1}{3}\left(\sum_{i=1}^{2^N}x_i - \sum_{i=1}^{2^N}1\right) = \frac{1}{3}\left(2^N - 2^N\right) = 0,$$ hence the total sum is $2^{N+1}$. $\endgroup$
    – sTertooy
    Jul 9, 2017 at 20:01

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.