Could this odd insight help explain part of the difficulty in proving the Collatz Conjecture?

Background: Here's a crash course on the Collatz Conjecture. Basically, you take a number and if it is even you divide it by two. If a number is odd, you multiply it by three and then add one. You keep doing this until the number becomes 1. The conjecture says that performing this operation for any number eventually results in 1. A quick note on the numbers used, they must be positive non-zero integers. As pointed out by Gottfried, there are contradictions otherwise. Stating the above in mathematical form,

$$n_{t+1} = \begin{cases} n_t/2, & \text{if $n_t$ is even} \\ 3 \cdot n_t+1, & \text{if $n_t$ is odd} \end{cases}$$

What I found: Here's what was kind of surprising to me. If you perform $3 \cdot x+1$, where $x$ is odd, then you will always get an even number. However, ${x \over 2}$ doesn't always result in an odd number, if $x$ is even. My assumption is this, if one could figure out how many times you have to divide an even number by two to get an odd number, headway could be made in proving the conjecture. However, when I went to find $v_2(e)$, where $e$ is an even number, and $v_2(e)$ is the number of times you can divide the number by 2, I discovered a fractal like pattern! If you plot the values of this function, you get,

$$1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,\ldots$$

The first value is $v_2(2)$. The second is $v_2(4)$, and so on. The sequence corresponds to sequence A001511.

If you define an L-system with,

$$C_n \rightarrow C_n (+)^{n-1} P (-)^{n-1} C_n$$

Where $P$ is a plot move right command, $+$ is a move up command, $-$ is a move down command, and $C_n$ is the string. The up/down commands just add/substract from a counter. The plot command will actually plot the value, and move the independent variable up one. The values of $v_2(e)$ can be extracted from $C_n$ by "reading" $C_n$ left to right and adding $1$. The exponents, denote moving up/down $n-1$ times. Graphically, we have,

The graph

Questions: Since this function $v_2(e)$ has a self-similar (fractal-like) nature, does that mean that the Collatz Problem is related to fractals? Could this be used to study the problem? Since fractals are inherently complex to compute in a linear fashion, could this explain why the conjecture is so hard to prove? I believe it explains some of the complex behavior of the iterates under the Collatz system.

Addendum:

Given an odd number, the next odd number in the Collatz iteration is given by,

$$(1) \quad o_{t+1}={{3 \cdot o_t+1} \over {2^{v_2(3 \cdot o_t+1)}}}$$

Since any even number fed into the iteration is reduced to an odd number under the iteration, we need only consider odd numbers. Therefore, the Collatz conjecture is equivalent to the conjecture that the Dynamical System $(1)$ has one and only one fixed point and that this fixed point is $1$ and attractive. In addition, the basin of attraction for this fixed point is the entire set of positive odd numbers. Now we can finally see relevance of the self-similarity of $v_2(o_n)$. Its highly complex behavior results in unusually a complex behavior for the Dynamical System.

Solution 1:

I think -although the problem has some "fractal" or "self-similar" structure- there is (at least) one more aspect to be looked at.

Consider the related problem where you insert "$3x-1$" for "$3x+1$" . (This is also simply looking at the negative integers in the original Collatz problem).
You'll have a very similar structure, again "fractal" looking. But now you'll have (at least) 3 cycles.

So we must introduce one more property which allows us to distinguish between a "1 existent cycle" fractal (with the $3x+1$) and a "3 different cycles exist" fractal (with the $3x-1$) problem.

What I think helps here is, to look at the inverse iteration.

For the original Collatz-problem this means: starting from $x_0=1$ we can construct all positive numbers by the iterative rule $$ x_{k+1,m} = {x_k \cdot 2^m - 1 \over 3} \text{for all $m$ where this is possible} $$ (only roughly defined) so $x_0=1$ defines somehow a root from where a stem, infinitely many twigs and leaves can be constructed - and with their rises and falls reach all positive numbers.

But for the $3x-1$-problem (the Collatz on the negative integers) this means: we need 3 roots, and each of the $3$ roots constructs its own specific tree with its own infinite sets of twigs and leaves - with their own risings and falls, but not overlapping and all 3 trees are needed to cover/construct all negative (in the Collatz-problem) numbers!

After that, the question of L. Collatz might be specified: "is it true, that on the positive numbers one root is sufficient, while on the negative numbers we need $3$ roots (even partially organized in cycles) to construct all (negative) numbers?"

So the "fractality" alone does not suffice; we need also an explanation for the question why the the set of positive numbers needs only one root and not -for instance- three as in the $3x-1$ problem.

Solution 2:

As has been noted in the comments, this is called the $2$-adic valuation of $n$ and is noted as $v_2(n)$. In particular, if we take some $n<2^k$ we can notice the identity: $$v_2(n)=v_2(2^k-n)=v_2(2n)-1$$ which basically tells us that the function, in the interval $(0,2^{k+1})$ is composed of two copies of itself scaled by half on the $x$-axis and translated $1$ down (one of the copies gets reflected according to the above identity, but the reflection is along a symmetry of the function). Along with the fact that $v_2(2^k)=k$ this defines the function, as well as explains its fractal nature.

Something which you've not noted, but which is also true, is that if we consider the map $$f(x)=\begin{cases}\frac{3x+1}2&&\text{if }x \text{ is odd}\\ \frac{x}2 &&\text{if }x \text{ is even}\end{cases}$$ which is often how the Collatz conjecture is expressed*, then we can get sequences of odd numbers. In fact, noting that $$\frac{3x+1}2=\frac{3}2(x-1)+1$$ we find that iterating that function $n$ times starting from $x$ gives $\left(\frac{3}2\right)^n(x-1)+1$ so the number of times we hit odd numbers is $v_2(x-1)$ under this definition. It should be noted that using both "shortcuts" to define: $$\hat f(x)=\begin{cases}\left(\frac{3}2\right)^{v_2(x-1)}(x-1)+1&&\text{if }x \text{ is odd}\\\frac{x}{2^{v_2(x)}}&&\text{if }x\text{ is even}\end{cases}$$ then it is a result of Simon and De Weger that this map has no cycles of length $2\times 68$ or less (over the positive integers).

I would suggest that the appearance of the 2-adic valuation does not suggest a fractal nature to the problem itself except than to express the fact that the problem relates, somehow to factoring, where such structures naturally arise. Really, what may worry us is the appearance of both $v_2(x)$ and $v_2(x-1)$. This suggests that we care about the factorization both of $x$ and $x-1$ (but the relationship of these factorizations is not well understood). It also suggests a sensitivity to initial conditions - under the first $f$ I gave, we see that if $n$ will be halved many times before hitting an odd number, then $n+1$ will be increased many times before hitting an even number - so the best and worst cases are right next to each other.

(*A prime reason why this is a favored expression is that if we choose some $k$ and some sequence of parities (even/odd), then the portion of positive numbers $n$ such that $n,\,f(n),f^2(n),\,\ldots,\,f^{k-1}(n)$ matches that sequence of parities is asymptotically $\frac{1}{2^n}$. In particular, we can thus imagine that we randomly choose to multiply by $\frac{3}2$ or $\frac{1}2$ at each step - which would tell $f$ should be making things smaller when applied many times.)

Solution 3:

I don't know if this answers your question, but it sure is fascinating. The Collatz function has been analytically extended to the complex numbers, and the plot of which points on the complex plane converge and which don't after successive iterations of the extended function (the same technique was famously used on the Mandelbrot set) forms a fractal, and a particularly beautiful one at that. Here are some pictures from the fractal made from the "shortcut" function pointed out by Milo Brandt, which is defined as

$$f(x)=\begin{cases}\frac{3x+1}2&&\text{if }x \text{ is odd}\\ \frac{x}2 &&\text{if }x \text{ is even}\end{cases}$$

extended to the complex numbers as

$$ f(z) = \frac{1}{4} (1 + 4z - (1 + 2z) cos (\pi z)) $$

Centered at the origin with a radius of 3: enter image description here