Why does this cycle of 44 show up in the Collatz Conjecture?

Question

Consider this function:

$$f\left(x\right)=\frac{x-b^{\left(\operatorname{floor}\left(\log_{b}x\right)\right)}}{b^{\left(\operatorname{floor}\left(\log_{b}x\right)\ +\ 1\right)}-b^{\left(\operatorname{floor}\left(\log_{b}x\right)\right)}}$$

Here is a StackExchange post with more information about the function. But basically, you could describe the function as:

A relative measure of how far away a number is from the smallest number with the same number of digits.

or

A relative measure of how far a number 'x' is from the biggest power of 'b' that is still less than or equal to 'x'

So anyways, if we set b=6, then apply f(x) to elements of Collatz orbits that have a length > 44, we see a cycle. It's easy to see this when you graph the points (i, f(x)) on a polar graph.

i = the index of the element in the sequence
x = the value at COLLATZ[i] where COLLATZ is an array created from the elements of the Collatz orbit starting at n and terminating at 1.

Here is the graph for n = 27. The points are labeled (i, COLLATZ[i])

It clearly cycles at 44.

To test this hypothesis further, I tried graphing n = 670617279, which has 949 steps. Here is the result.

I thought it may be simply because I was using polar coordinates, but I see similar symmetry when using cartesian coordinates.

I think I'm on the verge of understanding why, but I just wanted to ask the community for any insight. I find it odd that 44 shows up.

By the way, here is a medium article where I go over the use of this function in more detail as it applies to Collatz.

Answer 1

There are two types of steps involved in a Collatz sequence: One that multiplies a number by $\frac{1}{2}$, and one that approximately multiplies a number by 3. (The “approximately” part is because the “+1” in the step).

If we assume that a Collatz counterexample cycle exists, that means that after m halving steps and n tripling (plus 1) steps, we get back to where we started, i.e.,

$$(\frac{1}{2})^m \times 3^n \approx 1$$

Taking logarithms, we get:

$$n \log 3 - m \log 2 \approx 0$$

or equivalently:

$$\frac{n}{m} \approx \frac{\log 2}{\log 3}$$

The 10 smallest integer solutions to this equation, having $|n \log 3 - m \log 2| < 0.1$, are:

• m=8, n=5 → m+n=13, error=0.052116
• m=11, n=7 → m+n=18, error=0.065667
• m=19, n=12 → m+n=31, error=0.013551
• m=27, n=17 → m+n=44, error=0.038565
• m=30, n=19 → m+n=49, error=0.079218
• m=35, n=22 → m+n=57, error=0.090681
• m=38, n=24 → m+n=62, error=0.027102
• m=46, n=29 → m+n=75, error=0.025014
• m=49, n=31 → m+n=80, error=0.092769
• m=54, n=34 → m+n=88, error=0.077130

So it happens that one of these near-cycle possibilities has 44 steps, with 27 halvings and 17 triplings.

That still leaves the question: Why ask about 44-cycles as opposed to the smaller 13-, 18-, or 31-cycles? And that's because of your choice of the polar coordinate system, using integer values of $\theta$. It happens that 44 radians is 7.002817 turns, very close to an integer. So the cyclic behavior is most visible there.

By adjusting your coordinate system, you should see similar cyclic behavior for the other $m+n$ values I listed above.

Answer 2

Warning: This is more of a comment than an answer and is terribly non-rigorous.

First, $44 \approx 2 \pi *7$, so 44 is 'approximate period' of angles in polar coordinates.

So we need to show that 44 is approximate period of the radii.

Your function is approximately (up to addition of and multiplication by some constants) $f(x) \approx x/6^k$, where $6^k$ is nearest to $x$ power of 6

Let's forget about adding 1, let's just multiply by 3 in Collatz game.

So, if $x_n$ is n-th term of Collatz sequence, we want to show that $$\frac{x_{n+44}}{6^{k_1}} \approx \frac{x_n}{6^{k_2}}$$

If we multiplied by $3$ exactly $a$ times, then we want $$ \frac{x_n * 3^a}{2^{44-a}6^{k_1}} \approx \frac{x_n}{6^{k_2}}$$

That is $$ 6^{a-k_1 - log_6(2^{44})} \approx 6^{-k_2}$$

$$ a - k_1 - 44 log_6(2) + k_2 \approx 0$$

Remember that $$ k_1 = floor(log_6(x_n+44))$$ Note that $$ a + log_6 (x_n) - log_6 (\frac{x_n*3^a}{2^{44-a}}) - 44 log_6(2) = a + log_6 (2^{44}/6^a) - 44log_6(2) = 0$$

So we want $$\{ log_6 (x_{n}) \} - \{log_6 (x_{n+44})\} \approx 0 $$

Now, $floor(x) - floor(y) $ and are either equal to or greater by 1 than $floor(x-y)$ -- Difference of 2 floors vs floor of difference

So either $$ \{ log(x_{n}) \} - \{log(x_{n+44})\} = \{ log_6 (x_n/x_{n+44})\} = \{ log_6 (2^{44}/6^a) \}=$$ $$ = \{log_6(2^{44}) - a\} = \{44log_6(2)\} = \{17.0215...\} \approx 0$$

Or $$ \{ log(x_{n}) \} - \{log(x_{n+44})\} = {17.0215...} - 1 = -0.9784...$$ The second case is bad $-0.9784... << 0$, but it happens rarely. Think of it this way: $log(x_n)$ and $log(x_{n+44})$ differ by $17.0215... - a$. The only way for them to have significantly different fractional parts is this: $log_6(x_{n+44})$ should have fractional part in $(0.9784..;1)$. But if we believe that $\{ log_6(x_{n+44}) \}$ is distributed uniformly random, then this happens with probability 2.1%

(I'm not sure if I handled the second case correctly. Accoring to me, there should be rare defects in the cyclic pattern)

TL;DR: 44 has two properties: it's almost a multiple of $2\pi$ and $log_6(2^{44})$ is almost an integer.

Answer 3

$f(x)$ for $b=6$ (bellow in Cartesian coordinates for $n=27$) is almost equivalent to the fractional part of $log_6(x)$: $g(x)=\{log_6(x)\}$ (second graph bellow) which also measure the distance to the next power of $6$

In red in the graph above (SageMathCell) is the Collatz sequence for $n=27$ with $f(x)$, and in blue, also with $f(x)$, is a random Collatz sequence (randomly apply $3n+1$ or $n/2$) starting with $n=27$ for 111 steps, witch I generated with this little Pari/GP code (didn't took the time to make it in SageMathCell):

n=27;for(g=1,111,print1(floor(n),", ");if(random%2==0,n=3*n+1,n=n/2))

You can see that as long as we apply either $3n+1$ or $n/2$, you will get the same type of graph whatever you do (with a small shift here and there depending on the starting value, the "+1" and which way you go from step to step).

This is because the fractional part of $log_6(x)$ will be nearly the same on step $i$ since you either multiply by $3$ or divide by $2$ from the previous step which land on the same spot (both results being separated by a factor of 6, so having the same fractional part)

Same result for $g(x)$ bellow (can be found in the same SageMathCell linked above)

So a 111 steps Collatz sequence, whatever the path, will always look like this in Polar coordinates (each group of 3 dots are the dots we find horizontally separated by 44 on the Cartesian graph, at different "heights" from 0 to 1) :

Now, if we look at 1 of the 3 dots group (e.g the 3 most outer values in OP first graph, which are the nearest to a power of 6, or near y=1.0 on the Cartesian plot): $[214, 1276, 35]$ We can see that $$1276=\frac{3^{18}}{2^{26}}\cdot 214+\frac{2722925818}{2^{26}}$$ $$35=\frac{3^{15}}{2^{29}}\cdot 1276+\frac{481276588}{2^{29}}$$

To have almost the same value for the fractional part of lets say $\{log_6(214)\}\approx\{log_6(1276)\}$, we must have $\{log_6(\frac{3^n}{2^{m-n}})\}=\{log_6(\frac{1}{2^m})\}\approx 0$ or $1$, which is the case for $m=44$, but also for $\{13, 18, 31, 44, 49, 62, 75, 88, 93\}$ with precision $<.05$, which is mostly the same list as Dan proposed.