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.
Now to have a (very) simple cycle of just one step we must have:
$$ a = {3a+1\over 2^A } \tag 2$$
It is simple to show, there is no solution except when $a=1$ only by rearranging:
$$ a = {3a+1\over 2^A } \\
2^A = {3a+1\over a } $$
$$ 2^A = 3+{1\over a } \tag3\\
$$
and having the rhs a perfect power of $2$ requires $a=1$, thus allowing (only) the well known "trivial" cycle $1 \to 1$.
Now extending this to a two-step cycle we need to have
$$\begin{array}{} b = {3a+1\over 2^A } & a = {3b+1\over 2^B }\\ \end{array} \tag 4$$ with some so far undetermined $A$ and $B$.
To see better the space of possible solutions we can take the product of the lhs's $a \cdot b$ and which must equal the product of the rhs's:
$$\begin{array}{} a \cdot b = {3a+1\over 2^A } \cdot {3b+1\over 2^B }
\end{array}$$ resulting in the required equality
$$\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.
Now you see the pattern, how this generalizes to the disproof of the 3-step-cycle, 4-step-cycle, and so on for the N-step-cycle.
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).
Well, this shall just give an
intuition as to why cycles are much unlikely.
If you like to do more, allow
negative numbers for $a_1,a_2,...$ and see how and which solutions for small $N$ you can get.
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.
[Update]
Just to have an example, how a (possibly infinite, don't know at the moment) set of $N$ can be ruled out for a solution to exist.
Assume for example $N=12$. So we have on the rhs 12 parentheses of the form $(3+1/a_k)$, whose product should equal $2^S$ (where I use in general the letter $S$ for $S=A_1+A_2+...A_{12}$, just the sum of exponents, which is also the number of even-steps). Then what is the next possible perfect power of 2 above $3^{12}$? we get, using $\beta=\log(3)/ \log(2)$: $S=\lceil N \cdot \beta \rceil = 20$,thus we have the condition
$$2^{20} =(3+ {1\over a_1})(3+ {1\over a_2})...(3+ {1\over a_{12}}) \tag 6$$and the solution for smallest $1 \ne (a_1 \ne a_2 ... \ne a_{12})$ is
$$2^{20} \overset?=(3+ {1\over 5})(3+ {1\over 7})(3+ {1\over 11})...(3+ {1\over 37}) \tag 7$$
Of course we could simply compute the values of the LHS and the RHS getting
$$ 2^{20}= 1048576 \gt 697035.738776 $$
and because increasing the values for the $a_k$ would even decrease the value of the rhs there is no solution and thus no $N=12$-step cycle.
But for the sake of generality we proceed differently.
Instead we do a rough estimate for the
mean-value of the $a_k$. Assume all $a_k$ are equal to their "mean" $a_m$, then we can rewrite the equation
$$ 2^S = (3+{1\over a_m})^N \\
2^{S/N} = (3+{1\over a_m})\\
2^{S/N} -3 = {1\over a_m}\\
{1 \over 2^{S/N} -3} = a_m \tag 7 $$ $$
a_m = {1 \over 2^{20/12}-3}\approx 5.72075494219... \tag 8
$$
and because $a_m$ is somehow a rough mean, some $a_k$ must be smaller and some must be larger. But there is only
one possible value for any $a_k \lt a_m$ namely $a_1=5$.
After that, rearranging one parenthese with that value assumed to the lhs in eq(6) we get
$$ 2^S/(3+1/5) = (3+{1\over a_m})^{N-1} \\
2^{20} \cdot 5/16 = (3+{1\over a_m})^{11} \\
a_m \approx 5.79638745091$$
and we find, that there is no way that $a_m$ can be a rough mean of the remaining $11$ $a_k$ since there is no more odd integer $a_k$ in $1 \ne 3 \ne 5 \lt a_k $ so a $N=12$-step-cycle cannot exist.
We see nicely, that for some $N$ we can exclude the possibility of a cycle just based on the basic assumptions on the form of the members of a possible cycle $a_k$ by the formula (6) and for such $N$ do not need to recurse to the $a_k \gt 2^{60}$ found by de Oliviera and Rosendaal.
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.
[update 2]
I've not done this before explicitely, but trying the continued fraction-convergents and filling into $a_k$ the set of consecutive smallest possible integers ($5,7,11,13,...)$ we get the following small table
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 is intended as a comment, but too long for the comment-field
A simple table gives infinite modular classes of odd numbers $a_1$, which always decrease by one step of the $(3x+1)/\nu_2(3x+1)$ iteration to $a_2$. This is, with $k \in \{0,1,2,3,...\}$:
Table 1:
$$ \begin{array}{r|r|r||r|r|r}
A &a_1 &a_2&& A & a_1 & a_2\\ \hline
\color{red} {1} & \color{red} { 2^1\cdot 2k+3\phantom {1}} & \color{red} {3\cdot 2k+5} && \color{green} {2}& \color{green} {2^2\cdot 2k+1 \phantom {1}} &\color{green} { 3\cdot 2k+1} \\
3 & 2^3\cdot 2k+13 & 3\cdot 2k+5 && 4& 2^4\cdot 2k+5 \phantom {1} & 3\cdot 2k+1 \\
5 & 2^5\cdot 2k+53 & 3\cdot 2k+5 && 6& 2^6\cdot 2k+21 & 3\cdot 2k+1 \\
\vdots & \vdots &\vdots && \vdots &\vdots & \vdots & \\
A & 2^A\cdot 2k+r_A & 3\cdot 2k+5 && A& 2^A\cdot 2k+r_A & 3\cdot 2k+1 \\
\vdots & \vdots &\vdots && \vdots &\vdots & \vdots & \\
\end{array}$$
where $r_A = { 2^A-1\over 3}$ if $A$ is even, and $r_A = { 5 \cdot 2^A-1\over 3}$ if $A$ is odd.
From this table it is easily visible, that
- only for numbers $\color{red} {a_1}$ with $\color{red} {A=1}$ the iteration to $a_2$ is increasing.
- For $k=0$ we have with $A=2$ the trivial cycle with $a_1=a_2=1$ and
- for all other cases the iteration decreases.
This shows that the least element $a_1$ of a divergent sequence must be of the form $4k+3$ .
Out of couriosity I've tried to tabular the subforms of $a_1=4k+3$ in a comparable way($ b_1=16k+3$ and $c_k=16k+11$ and so on) to pinpoint the distinction between increasing and decreasing iterations - but this leads soon to another representation scheme, which becomes more complicated. (And I've not yet put that together in a nicely-readable essay.)
update: I see that the list (or better:tree) that I've created for this aspect is just that list, that user @Vepier mentions in his/her comment.
The beginning of this list, ordered for the powers-of-2 in the $a_1$ variable, looks like this. It is a systematic list of modular classes for $a_1$ which are decreasing after a small number $n$ of iterations (here $n$ is also the length of the exponents-vector $E$). The exponents-vector $E$ (here printed as compacted string) of the exponents $A_1,A_2,A_3,...A_n$ for "dropping time" $n$ is generated by a recursive tree structure.
Table 2:
E a_1 --> a_j
----------------------------------------------
2 1 +k* 4 --> 1 +k* 3 a_1 mod 4 = 1
- - - - - - - - - - - - - - - - - - - - -
13 3 +k* 16 --> 2 +k* 9 a_1 mod 4 = 3, but decreasing
122 11 +k* 32 --> 10 +k* 27
113 23 +k* 32 --> 20 +k* 27
1123 7 +k* 128 --> 5 +k* 81
1114 15 +k* 128 --> 10 +k* 81
1213 59 +k* 128 --> 38 +k* 81
11213 39 +k* 256 --> 38 +k* 243
11132 79 +k* 256 --> 76 +k* 243
11114 95 +k* 256 --> 91 +k* 243
12122 123 +k* 256 --> 118 +k* 243
11123 175 +k* 256 --> 167 +k* 243
11222 199 +k* 256 --> 190 +k* 243
12113 219 +k* 256 --> 209 +k* 243
111124 287 +k* 1024 --> 205 +k* 729
121123 347 +k* 1024 --> 248 +k* 729
111214 367 +k* 1024 --> 262 +k* 729
112123 423 +k* 1024 --> 302 +k* 729
121213 507 +k* 1024 --> 362 +k* 729
111115 575 +k* 1024 --> 410 +k* 729
... ... ...
The still increasing (and so hopefully diverging) cases are that where the last entry in $E$ is smaller than the shown one.
Here is a table, where in the above list I measure the covering of the odd numbers in residue-classes sequentially up to a given residue class. From this I calculate the relative number of residue classes not covered so far, which means, that part of a residue-class whose members $a_1$ increase after that $n$ steps. Over the residueclasses we find, that the number of those potential divergent $a_1$ decreases with $n$ (P.s.: this is just barely observation and no final interpretation so far):
- $cov =$ all displayed (weighted) occurences of residues in class $2^S$
- $miss= 1 - cov/(2^S/2)$ - the relative number of missing residue classes (relative number of potential divergent $a_1$)
- $crit= S \cdot miss $ - just something which might be a significant coefficient
Table 3:
S 2^S cov: miss: crit:
--------------------------------------------------------------
2, 4, 1, 0.500000000000, 1.00000000000
4, 16, 5, 0.375000000000, 1.50000000000
5, 32, 12, 0.250000000000, 1.25000000000
7, 128, 51, 0.203125000000, 1.42187500000
8, 256, 109, 0.148437500000, 1.18750000000
10, 1024, 448, 0.125000000000, 1.25000000000
12, 4096, 1822, 0.110351562500, 1.32421875000
13, 8192, 3729, 0.0895996093750, 1.16479492188
15, 32768, 15089, 0.0790405273438, 1.18560791016
16, 65536, 30654, 0.0645141601563, 1.03222656250
18, 262144, 123577, 0.0571823120117, 1.02928161621
...
Best Answer
Any sequence of parities corresponds to specific composition of the two possible linear transformations, hence to a transformation of the form $n\mapsto \frac{3^an+b}{2^c}$ with non-negative integers $a,b,c$. For this to produce an integer, it must be the case that $2^c\mid 3^an+b$, i.e., $n$ must be in one specific residue class modulo $2^c$. As we can consider several periods instead of one, it follows that $n$ must be in a specific residue class modulo $2^{kc}$ for every $k\in\Bbb N$. This means that there can be only one such $n$. But then $\frac{3^an+b}{2^c}$ must be the same number and hence the sequence does not diverge.