collatz conjecturereference-request
This question is with reference to the collatz conjecture. It is known that a number $A$ in a collatz cycle is of the form:
$$A = \sum_{i=1}^k \frac{ 3^{k-i} \cdot 2^{k_i}}{2^n – 3^k},$$
$0 = k_1< k_2 < k_2 …k_k < n$.
Here, $n$ represents the number of divisions by $2$ in the cycle and $k$ represents the number of odd numbers in the cycle. For the trivial cycle $n = 2k$.
My question is this: has it been shown that there are no non-trivial cycles with $n = 2k$? If so, could i get a reference?
Consider the "compacted" formula (as also used in the "Syracuse"-version of the Collatz), defining one "step" beginning on $a$ going to $b$ (both odd $\ge 1$):
$$ b = {3a+1\over 2^A } \tag 1$$ where $A$ contains the number of halving-steps.
$$\begin{array}{} 2^{A+B} = (3+{1\over a}) \cdot (3+{1\over b })
\end{array} \tag 5$$
This shows, we can only have a solution if the rhs becomes at least integer, which is difficult enough , but actually must even equal a perfect power of 2, larger than $3^2=9$ and namely must equal $16$. Now what values must $a,b$ have such that the rhs equals $16$? Both must contain $a=b=1$ and that is the already known trivial cycle, and no other solution in possible.
Unfortunately, for several $N$ the possibility for small $a,b,c,...$ exists "theoretically", which means, that the rhs-product can reach a perfect power of 2 by some $1 \lt (a_1 \ne a_2 \ne a_3 \cdots \ne a_N)$ - one might just try some $N$ by hand, remembering the conditions that all members of an assumed cycle should be greater than $1$, should be odd, should not be divisible by $3$ and that all involved $a_k$ should be different from each other, to get a better intuition.
Now to proceed more we introduce the knowledge, that by simple heuristics we already know, that $a_k \gt 1000$ (can be done manually with a programming language) or $a_k \gt 1 000 000 $ and even $a_k \gt 2^{60} $ (the latter by an extensive numerical search by de Oliviera and by Rosendaal).
If we introduce that knowledge and assume the minimal $a_1$ being, say $a_1=1+2^{60} $ , $a_2 = {3a_1+1\over 2^{A_1}} $ and so on , we find that for all manually reachable $N$ the rhs is disappointingly near to the value of $3^N$ and no perfect power of $2$ is only in any realistic distance from that. One can find, using the continued fraction of $\beta = \log(3)/\log(2)$, we need $N \gt 150 000 $ (or even much more don't have the actual value at hand).
Or proceed and compare the $5x+1$ problem with this: we find actually two or three possible cycles for small $N$ and $a_1 \lt 100 $ but after that the above method can be used to say much more about the nonexistence of certain $N$-step cycles. I've even found two cycles for the $181 x+1$-version having $N=2$ and small $a_1 \lt 100$ but after that, the formula comparing the rhs-product for $N$ steps to perfect powers of $2$ indicates the same "difficulty" for cycles to exist.
However, and this leads to the observation that we need for the general solution of the cycle-problem some deeper thinking, there are some $N$ for which $2^S$ is comfortably near to $3^N$ so we can allow a set of small $a_k$ such that the rhs can approach the lhs. The continued fraction of $\beta$ gives us pairs of $N$ and $S$ where $2^S$ are especially near to $3^N$ and for which a cycle cannot be excluded by this method alone.
N S lhs=2^S rhs = (3+1/a_k)*()... lhs/rhs a_m
1, 2, 4 , 3.2 , 1.25 1 ~ 2^0
5, 8, 256 , 292.571428571, 0.875 31.81 ~ 2^5
41, 65, 3.68934881474 E 19, 5.44736223436 E 19, 0.677 1192.08 ~ 2^10
306, 485, 9.98959536101 E 145, 5.57867460455 E 146, 0.179 99780.79 ~ 2^16
15601, 24727, 3.70427126979 E 7443, 1.06756786898 E 7444, 0.346 285817586.21 ~ 2^28
79335, 125743, 2.59863196329 E37852, 8.97264176433 E37852, 0.289 7216102492.69 ~ 2^33
and we see, that the RHS can reach the LHS for that specific $N$ and thus the assumption of the smallest possible values for the $a_k$ does not suffice to exclude the possibility of a cycle. The "mean" $a_m$, estimated by the geometric mean of all parentheses as proposed above, are in the last column; they increase with the size of $N$ and we get an impression as at which cyclelength $N$ this allows values of $a_1 >2^{60}$ and thus this method has its heuristical limit: the last entry in the last row means $a_m \approx 2^{33}$ and this means, that the knowledge that $a_1>2^{60}$ suffices to have disproved all cycles of steps $N \le 79335$.
But it might anyway be interesting to see, what explicitely smallest value for $a_1$ (which we can assume to be the smallest of the cycle) and the following sequence of consecutive possible members would suffice to have the LHS smaller than the RHS. That would surely be a nice exercise ...
This should not be seen as new answer; it is meant as an explanative comment to the Collag3n's answer, due to OP's additional comments
The following way to express things with the focus the OP has, is my favorite, and I think that scheme as especially clear.
The one-step formula can be expressed as ("Syracuse style"): $$ a_{k+1} = { 3a_k+1\over 2^{A_k}} \tag 1$$ $ \qquad \qquad $ where the $A_k = \nu_2(3 a_k+1)$ .
a.1) For a cycle of 1 step we can write $$ a_1 = { 3a_1+1\over 2^{A_1}} \qquad \qquad \implies \quad 2^{A_1}=\left( 3+ {1\over a_1} \right) \tag {2.1} $$ a.2) For a cycle of 2 step we can write $$ a_2 = { 3a_1+1\over 2^{A_1}} \qquad \qquad a_1 = { 3a_2+1\over 2^{A_2}} \\ a_1 \cdot a_2 = { 3a_1+1\over 2^{A_1}}\cdot{ 3a_2+1\over 2^{A_2}} \implies \quad 2^{A_1}2^{A_2}=\left( 3+ {1\over a_1} \right)\left( 3+ {1\over a_2} \right) \tag {2.2} $$ b) Generalizing: Let's use the symbols $N$ for the (n)umber of $a_k$, and $S$ for the (s)um of the $A_k$, so we have here $N=2$ and we see immediately that in $$ 2^S=\left( 3+ {1\over a_1} \right)\left( 3+ {1\over a_2} \right) \tag 3$$ (assuming all $a_k>0$) the rhs can only be in the interval $\{9 .. 16\}$ = $\{3^N .. 4^N\}$. In the general case for any $N$ and all $a_k>0$ we have thus $$3^N \lt \text{rhs} \le 4^N = 2^{2N} \tag 4$$
The minimal case $\text{rhs}=3^N$ can only occur as limit, when all $a_k "=" \infty$ and the maximal case $\text{rhs}=2^{2N}$ only if all $a_k=1$ (and by the formula (1) thus all $A_k=2$). Introducing the lhs in the inequality means $$3^N \lt 2^S \overset?= \text{rhs} \le 4^N = 2^{2N}$$ The lower bound for $S$ is by this $S \ge \lceil N \cdot \log_2(3) \rceil $ and we have immediately $$ \lceil N \cdot \log_2(3) \rceil \le S \le 2N \tag 5 $$
The second part of your question, whether for some cycle of -perhaps large- $N$ it can happen, that $S$ exceeds it lower bound, for instance such that $S=\lceil N \cdot \log_2(3) \rceil+1$ is not easily to answer here; this depends on the approximability of $2^S$ and $3^N$ and the distance must be very small relative to $N$ resp $3^N$.
But in your last command you additionally ask, whether it can happen that all $A_k=1$: this can only happen if all $a_k=-1$ such that we have $$ 2^S \overset?=\left( 3+ {1\over -1} \right)^N = (3-1)^N=2^N \\ \implies S=N \implies \text{all } A_k=1 \tag 6$$ For all other cases where any $a_k \ne -1$ it is necessary that $S>N$ and thus some $A_k>1$ (and for positive $a_k$ the lower bound for the number of $A_k \ge 2$ can be calculated for each $N$ individually) .
Update The question whether it might be possible, that a cycle sums the $A_k$ to $S=C+1$ where $C=\lceil N \cdot ß\rceil$ and $ß=\log_2(3)$ can be answered by the assumption of a roughly (fractional) mean value of all $a_k$, say "$\alpha$". We look at the generalization of eq (3), but in the better to handle form
$$ {2^S \over 3^N } = (1+\frac1{3a_1})\cdot(1+\frac1{3a_2})\cdots(1+\frac1{3a_N}) = (1+\frac1{3 \alpha})^N \tag 7$$
From this we can get the "mean" value
$$ {2^{S/N} \over 3} = 1+\frac1{3 \alpha} $$
$\phantom{-----}$ and assuming $S=C+1$
$$
\alpha = {1 \over 3} \cdot {1\over 2^{(C+1)/N - ß}-1} \tag 8
$$
$\qquad \qquad \qquad \qquad $ Note: Here the exponent at $2$ can be better rewritten as
$$ \qquad \qquad \qquad \qquad \small {C+1\over N}-ß = {\lceil N ß \rceil +1 \over N} - ß = { 2+ N ß - \{N ß \} \over N } - ß = { 2 - \{N ß \} \over N } $$
$\qquad \qquad \qquad \qquad $ where the notation $ \{ x \} $ means the fractional part of $x$ and this latter form is better to use when $N$ and thus $C$ become very large numbers.
We have then that the "mean" values $\alpha$ in most cases are very small, and since the minimal value in the assumed cycle (assumed to be in $a_1$ ) must be smaller than that "mean" value $\alpha$ we have that $a_1 \lt 5$ and thus an a priori forbidden value.
But the convergents of the continued fractions of $ ß=\log_2(3)$ indicate those $N$ where the denominator in eq (8) becomes small and thus $\alpha$ arrives at meaningful values. A short list of this, taken from $N$ and $C$ from that convergents, shows this:
N*1.0 alpha N/alpha
5, 2.07381859665, 2.41101126592
41, 19.2298809957, 2.13209847784
306, 146.771589110, 2.08487215991
15601, 7502.13151589, 2.07954232300
79335, 38151.7019781, 2.07946161997
190537, 91628.7531413, 2.07944551757
10781274, 5184696.58678, 2.07944164515
171928773, 82680262.3510, 2.07944155124
397573379, 191192380.562, 2.07944154381
6586818670, 3167590209.94, 2.07944154182
1.37528045312 E11, 66137009651.3, 2.07944154169
5.40930392448 E12, 2.6013253 E12, 2.07944154168
1.15717186888 E13, 5.5648203 E12, 2.07944154168
...
Interestingly, the ratio $N/\alpha$ seems to converge to something a bit over $2$, and if $\alpha$ were a sort of median then we were lucky here with the disproof: then $N/2$ of the members of a cycle must be smaller than that median, and by an average stepping of $a_{k+1}-a_k \sim 3$ we had $a_1 \sim \alpha - 3/2 N \sim N/2-3N/2 \sim - N$. But unfortunately, $\alpha$ is of course not a median.
Anyway, I've played with that more precise idea and up to $N=190537$
This shows, that we need more information to exclude the possibility of a cycle with $S \ge C+1$ . Here is a table to show, if we fill in eq (3), extended up to $N$ parentheses, into the $a_k$ the lowest possible values $a_k \in \{5,7,11,13,...\}$ beginning with $a_1=5$ and look, whether in the rhs would occur a value $2^{S^*}$ equal or larger than $2^{S}=2^{C+1}$. We check for this the value $S^*(N,a_1)=\log_2(\text{rhs})$ and the criterion $crit= S^* - C$.
Table 1:
a1=5
N C S*(N,a1) S* - C
--------------------------------
2, 4, 3.33, -0.669
3, 5, 4.95, -0.041
5, 8, 8.19, 0.192
10, 16, 16.21, 0.214
17, 27, 27.38, 0.387
29, 46, 46.48, 0.488
41, 65, 65.56, 0.562
We show, up to $N=41$, only that $N$ for which the criterion increases, and although we've taken the smallest possible value $5$ into $a_1$ the rhs does not go up to $S^* \ge C+1$. Here $N=41$ is already an entry from the convergents of the cont.frac. and so I show the next $N$ from that convergents only:
Table 2
a1=5 a1=7
N C S*(N,a1) S*-C S*(N,a1) S*-C
----------------------------------------------------
41, 65, 65.56, 0.562 63.82, -1.179
306, 485, 485.89, 0.895 484.15, -0.848
( 612, 970, 971.01, 1.005 ) N=612 not in cvgts, but is first case for S*>C+1
15601, 24727, 24728.52, 1.527 24726.78, -0.218
79335, 125743, 125744.78, 1.787 125743.04, 0.042
190537, 301994, 301995.92, 1.928 301994.18, 0.183
... ... ... ... ... ...
At least, for $N=15601$ and $a_1=5$, we see that $S^* \ge C+1$, and for $N=190537$ we arrive nearly $S^* = C+2 - \varepsilon$ and of course this shall continue and extend for the following convergents.
Unfortunately, the Q&d-procedure with which I compute this values cannot handle significantly larger $N$ (a more sophisticated procedure for N to arbitrary size is possible if Hurwitz-zeta is employed but I don't have my older studies at hand) so we have only a tendency. But I've supplied as well the results, when we begin with $a_1=7$ instead of $a_1=5$ in the previous table. This small step invalidates already all found solutions so far: we have $S^* \lt C+1$ for all $N \le 190537$.
Conclusion: after we know, that any cycle cannot have a minimal element $a_1 \lt 2^{64}$ (or so, see wikipedia) we might have an idea how large any $N$ must be to allow $S^* \ge C+1$ at all. (I've not yet checked the idea of @collagen, maybe that arguments suffice to really exclude the possibility of $S* \ge C+1$ at all).
Best Answer
A cycle of $a_i$ for $k$ odd steps and $n$ even steps must satisfy a product formula $$ 2^n = (3+{1\over a_1})(3+{1\over a_2})\cdots (3+{1\over a_k}) $$ Because the rhs is larger than $3^k$ we must have that $n \ge \lceil k \cdot \ln_2(3) \rceil \approx \lceil 1.5 k \rceil $
If we want $n=2k$ then we have $$ 2^{2k} = (3+{1\over a_1})(3+{1\over a_2})\cdots (3+{1\over a_k}) \\ 4^{k} = \underset{ k \text{ - parentheses}}{\underbrace{(3+{1\over a_1})(3+{1\over a_2})\cdots (3+{1\over a_k})}} \\$$ and from this, since no parenthese on the rhs can be larger than $4$, no other one can be smaller than $4$ and thus all of them must equal $4$ and finally all $a_i=1$ is required.
So this all defines the "trivial cycle" $1 \to 1 \to \cdots $ of length $k$ and no other solutions are possible.
I have a bit of discussion in my text on my homepage which might interest you although this is no (serious) "reference". (Unfortunately I do not know any reference which discusses this detail explicitely but of course the product formula and some consequences of it are well known at least since R.Crandall1 in the 70'ies)
1 Crandall, R. E., On the ”3x+1” problem, Math. Comput. 32, 1281-1292 (1978). ZBL0395.10013.