# Collatz Conjecture: Checking my reasoning about the sum of the powers of $2$ if a cycle exists

Apologies on the length of this question. I found it surprisingly difficult to take even this baby step with the Collatz Conjecture.

If you see any step that is unclear, please let me know in a comment and I will update.

Let:

• gcd$$(a,b)$$ be the greatest common divisor of $$a$$ and $$b$$

• $$C(x) = \dfrac{3x+1}{2^w}$$ where $$w$$ is the highest power of $$2$$ that divides $$3x+1$$

• $$x_1>1, x_2>1, \dots, x_n>1$$ be the sequence of $$n$$ distinct odd integers for each application of $$C(x_i)$$ so that:

• for $$i > 1$$, $$x_i = C(x_{i-1})$$
• $$x_i > 1$$
• $$C_1(x) = C(x)$$
• $$C_n(x) = C(C_{n-1}(x))$$
• for each $$x_i$$, there exists $$w_{x_i,1}\ge 1, w_{x_i,2} \ge 1, \dots w_{x_i,n} \ge 1$$ such that:

$$C_n(x_i) = \dfrac{3^n x_i + 3^{n-1} + \sum\limits_{i=1}^{n-1}\left(3^{n-i-i}2^{\left(\sum\limits_{k=1}^i w_{x_i,k}\right)}\right)}{2^{\left(\sum\limits_{k=1}^n w_{x_i,k}\right)}}$$

Note 1: Details for this equation can be found here.

• $$m \ge n$$ be an integer with $$m = \sum\limits_{k=1}^{n}w_{x_1,k}$$

• Let integers $$c_1 > 0, c_2 > 0, \dots, c_n > 0$$ form an n-cycle so that each $$c_{i+n} = c_i$$

• $$\text{avg}(c_1, c_2, \dots, c_n) = \dfrac{\sum\limits_{k=1}^n c_k}{n}$$

Observation:

• Given an n-cycle: $$c_1, c_2, \dots, c_n$$, there exists $$1 \le k \le n$$ such that for all $$k \le j < k+n$$:

$$\sum\limits_{i=k}^{j} c_i \le \text{avg}(c_1, c_2, \dots, c_n)$$

Argument

• Base Case: $$n=2$$: either $$c_1 \le \text{avg}(c_1, c_2)$$ or $$c_2 \le \text{avg}(c_1,c_2)$$
• Assume that $$k$$ exists for any $$n$$-cycle up to $$n \ge 2$$
• Inductive Case:
• Let $$d_1, d_2, \dots, d_n, d_{n+1}$$ be an $$(n+1)$$-cycle with $$d_{n+1+i} = d_i$$
• There exists $$1 \le m \le n$$ with $$d_m < \text{avg}(d_1, d_2, \dots, d_n, d_{n+1})$$. Otherwise, all values are equal to $$\text{avg}(d_1, d_2, \dots, d_{n+1})$$ and any $$1 \le i \le n$$ will serve as $$k$$.
• Let $$c_1, c_2, \dots, c_n$$ be an $$n$$-cycle such that: $$c_i = \begin{cases} d_i, & i < m\\ d_{i+1}-\text{avg}(d_1,\dots,d_{n+1}) + d_i, & i = m\\ d_{i+1}, & i > m\\ \end{cases}$$
• Since $$c_1, c_2, \dots, c_n$$ forms an $$n$$-cycle, there exists $$1 \le k \le n$$ such that for all $$k \le j < k+n$$:

$$\sum\limits_{i=k}^{j} c_i \le \text{avg}(c_1, c_2, \dots, c_n) = \text{avg}(d_1, d_2, \dots, d_n, d_{n+1})$$

• Case 1: $$k = m$$ $$d_k = d_m < \text{avg}(d_1, d_2, \dots, d_{n+1})$$
• Case 2: $$1 \le j \le n$$ and $$k+j < m$$
• By assumption: $$\sum\limits_{i=k}^{k+j} c_i = \sum\limits_{i=k}^j d_i \le \text{avg}(c_1, c_2, \dots, c_n) = \text{avg}(d_1, d_2, \dots, d_n, d_{n+1})$$
• Case 3: $$1 \le j \le n$$ and $$k+j = m$$ $$\sum\limits_{i=k}^{k+j} d_i = \left(\sum\limits_{i=k}^{k+j-1} d_i\right) + d_m \le \text{avg}(d_1, d_2, \dots, d_n, d_{n+1})$$
• Case 4: $$1 \le j \le n$$ and $$k+j > m$$ $$\sum\limits_{i=k}^{k+j} d_i = \left(\sum\limits_{t=k}^{k+j-1} c_t\right) - \text{avg}(d_1,d_2,\dots,d_{n+1}) + d_{m} \le \text{avg}(d_1, d_2, \dots, d_{n+1})$$

Question:

Does it now follow that if $$x_1, x_2, \dots, x_n$$ form an n-cycle, then either $$2^{m-1} < 3^n$$ or there exists $$x_i$$ where $$x_i < n$$

If yes, is there a simpler or more straight forward way to make the same argument?

Argument:

(1) Assume that $$x_1, x_2, \dots, x_n$$ forms an n-cycle.

(2) For each $$x_i$$, it follows that:

$$x_i = C_n(x_i) = \dfrac{3^n x_i + 3^{n-1} + \sum\limits_{i=1}^{n-1}\left(3^{n-i-i}2^{\left(\sum\limits_{k=1}^i w_{x_i,k}\right)}\right)}{2^{\left(\sum\limits_{k=1}^n w_{x_i,k}\right)}}$$

Which implies that:

$$x_i\left(2^{m}-3^n\right) = 3^{n-1} + \sum\limits_{i=1}^{n-1}\left(3^{n-i-i}2^{\left(\sum\limits_{k=1}^i w_{x_i,k}\right)}\right)$$

(3) $$2^m > 3^n$$

This follows since $$2^m - 3^n = \dfrac{3^{n-1} + \sum\limits_{i=1}^{n-1}\left(3^{n-i-i}2^{\left(\sum\limits_{k=1}^i w_{x_i,k}\right)}\right)}{x_i}$$

Since, clearly: $$\dfrac{3^{n-1} + \sum\limits_{i=1}^{n-1}\left(3^{n-i-i}2^{\left(\sum\limits_{k=1}^i w_{x_i,k}\right)}\right)}{x_i} > 0$$

(4) Assume that $$2^{m-1} > 3^n$$

(5) $$2^m - 3^n > 2^m - 2^{m-1} = 2^{m-1}$$

(6) The average of each $$w_{x_i,k}$$ is $$\dfrac{m}{n}$$ with $$2^{\frac{m}{n}} > 3$$ since:

• $$m \ln 2 > n \ln 3$$
• $$\frac{m}{n}\ln 2 > \ln 3$$
• $$2^{\frac{m}{n}} > 3$$

(7) Since $$x_1, x_2, \dots, x_n$$ forms an $$n$$-cycle, from the Observation above, there exists an $$x_i$$ such that for each $$1 \le u \le n$$, $$\left(\sum\limits_{k=1}^{u} w_{x_i,k}\right) \le \dfrac{um}{n}$$

Note: The argument in the observation is derived from the solution to the well known gas stations on a circular trek problem.

(8) $$2^{m-1}n > 3^{n-1} + \sum\limits_{i=1}^{n-1}\left(3^{n-i-i}2^{\left(\sum\limits_{k=1}^i w_{x_i,k}\right)}\right)$$ since:

• $$2^{m-1} > 3^{n-1}$$ from step(3) above
• $$2^{m-1} \ge 2^{\left(\sum\limits_{k=1}^{n-1} w_{x_i,k}\right)}$$
• $$2^{m-1} > 2^{(n-1)\frac{m}{n}} > 3\times2^{\left(\sum\limits_{k=1}^{n-2} w_{x_i,k}\right)}$$ since: $$\dfrac{m}{n} > 1$$ from $$2^{\frac{m}{n}} > 3$$ and $$\frac{m}{n} + (n-1)\frac{m}{n} = m < m-1 + \frac{m}{n}$$
• $$2^{(n-1)\frac{m}{n}} \ge 3^2\times2^{\left(\sum\limits_{k=1}^{n-3} w_{x_i,k}\right)}$$
• $$\dots$$
• $$2^{(n-1)\frac{m}{n}} \ge 3^{n-2}\times2^{w_{x_i,1}}$$

(9) $$x_i < \dfrac{2^{m-1}n}{(2^m - 3^n)} < \dfrac{2^{m-1}n}{2^{m-1}} = n$$

Edit 1:

I found a mistake in my reasoning which led me to change the title slightly and change the question in order to fix the mistake in reasoning.

Edit 2:

• I haven't finished reading all of your question yet, but note your "$C_n(x) = C_1(C_2(\dots(C_n(x))\dots))$" is self-referential, and unclear, as stated. For $n=1$, we get $C_1(x) = C_1(x)$. For $n = 2$, we get $C_2(x) = C_1(C_2(x))$, i.e., $C_2(x)$ must be a value so $C_1$ of it returns that value. However, $C_1$ is not explicitly defined. Based on your previous question & the context, I believe you mean $C_n(x)$ is the composition of $C(x)$ $n$ times. One explicit, unambiguous way to state this is "$C_1(x)=C(x)$" and "$C_n(x)=C(C_{n-1}(x)) \; \forall \; n \gt 1$". Sep 27 '20 at 0:43
• Your "Note 2" of "Each set of $w_{x_i,1}, w_{x_i,2}, \dots w_{x_i,n}$ will consist of the same set of values with a shifted order ...", plus the later note of "$x_1$ was used but this sum will be the same for all $x_i$" will only necessarily be true if you have an $n$-cycle starting at $x_1$. You don't state this previously as being a requirement, with your question later asking about if we have $n$-cycle. It seems you're implicitly assuming an $n$-cycle initially, so if this is your intent, you should state this then & reword the rest of the question accordingly. Sep 27 '20 at 1:09
• You're welcome. Here's one more issue. In your (7) list of bullet points, there's "Since $v_{x_1,1}, \dots, v_{x_1,n}$ is a sequence of $n$ values, by assumption, there exists $j$ where $v_{x_j,1}, v_{x_j,2}, \dots v_{x_j,n}$ have the properties and $\dfrac{\sum\limits_{k=1}^n v_{x_j,k}}{n} = \text{avg}$". However, the assumption is only valid for a set of $n$ positive integers adding to $m$. In your case, this requires $\text{avg} = w_{x_j,l}-w_{x_j,n+1}$, where $\text{avg}$ is as defined earlier, which will usually be false. Also, you don't define it, but I assume $w_{x_j,n+1}=w_{x_j,1}$. Sep 27 '20 at 2:03
• @JohnOmielan Great points. I will attempt to revise the argument to address your comments. Sep 27 '20 at 2:49

from $$(3+\frac{1}{e_0})(3+\frac{1}{e_1})...(3+\frac{1}{e_n})=\frac{e_{n+1}}{e_0}\prod_{k=0}^n2^{\nu_2(3e_k+1)}$$ you can see that for a cycle: $$2^m\leq (3+\frac{1}{x_{min}})^n$$
If you state that $$2\cdot3^n<2^m$$ than you have
$$2\cdot3^n< (3+\frac{1}{x_{min}})^n$$ $$2^\frac{1}{n}\cdot3<3+\frac{1}{x_{min}}$$ $$x_{min}<\frac{1}{3(2^\frac{1}{n}-1)}