Collatz Function – Is It Possible to Describe in One Formula?

collatz conjectureelementary-number-theoryfunctions

This is related to Collatz sequence, which is that
$$C(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}$$

Is it possible to describe the Collatz function in one formula? (without modular conditions)

Best Answer

$$f(n)=\frac74n+\frac12+(-1)^{n+1} \left(\frac54n+\frac12\right)$$

Related Solutions

Collatz Conjecture – Is It the Only Stable Solution of Its Type?

Here are some pictures for your/our intuition. I graphed the trajectories for initial values $x=5,15,25,...$ for the first $256$ steps of $x_{k+1}=(5x_k+1)/2^A$.
To get the curves to a meaningfully visual interval I show logarithmic scales. The pictures show how most trajectories begin to diverge (not really a safe indication of what characteristic the infinite curves really have) but some show cycling already at early iteration indexes $k$ .

I find $2$ cycles besides the "trivial" one.

$x=5,15,25,35,...,95$ detail of the first few iterations . At the bottom we see the "trivial" cyle (brown curve):

$x=5,15,25,35,...,95$ first $2^8 = 256$ iterations. At later iteration-indexes $k$ a first "non-trivial" cycle occurs (red line):

$x=105,115,125,135,...,195$ first $2^8 = 256$ iterations .

$x=205,215,225,235,...,295$ first $2^8 = 256$ iterations . Here a second "non-trivial" cycle becomes visible:

$x=205,215,225,235,...,295$ first $2^{11} = 2048$ iterations
It seems really that all trajectories which are divergent up to iteration $k=256$ are also divergent up to iteration $k=2048$ . In general: I doubt that there are "later" cycles:

Collatz Conjecture: Reasoning about the possible divergence of a collatz sequence

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

Related Solutions

Collatz Conjecture – Is It the Only Stable Solution of Its Type?

Collatz Conjecture: Reasoning about the possible divergence of a collatz sequence

Related Question