1
$\begingroup$

My original method was different from the method shown here. Instead of working my way backward through the iterations as below, I worked my way forward. I choose against doing that here despite of it giving more insight into the problem in a more general case. The post simply got to long.

Letting $k,m,n,p\in\mathbb{N}$, we start with a refresher of what Collatz conjecture states:

Given the function $f:\mathbb{N}\rightarrow\mathbb{N}$,


$$ \begin{align} &f(n)= \begin{cases} 3n+1 & \quad \text{if } n \text{ is odd}\\ n/2 & \quad \text{else}\\ \end{cases}\\ \end{align} $$


there exist for any number $n$ a number $p$ such that $p$ iterations of $f$ evaluated at $n$ is equal to $1$.

As I find it easy to get blind with my own work, my questions are simple; is this known, and is what's done here valid?

Given a function $g:\mathbb{N}\rightarrow\mathbb{N}$, a number $n$ is said to be part of a cycle if there exist a number $p$ such that $p$ iterations of $g$ evaluated at $n$ is equal to $n$.

The result in the title is quite easy to verify using the function $f$ in reverse, which is why I'm surprised I haven't been able to find it written down anywhere. If we evaluate $6k-3$ we get:


$$ \begin{align} &o_1,o_2\in\mathbb{O}\\ \\ &\frac{3o_1+1}{2^m}=o_2 \implies o_1=\frac{2^mo_2-1}{3}\\ \\ &\frac{2^m(6k-3)-1}{3}=2^{m+1}k-2^m-\frac{1}{3}\\ \end{align} $$


We can see that this will never be an integer. It's therefore impossible to iterate the function $f$ evaluated at any number $n$ and get $6k-3$ with the exception of $2^m(6k-3)$, showing that $2^{m-1}(6k-3)$ cannot be part of any cycle.

$\endgroup$
  • 3
    $\begingroup$ No multiple of 3 can be part of a cycle because the prime factorisation of 3n+1 does not contain any "3" factor (and dividing by $2^k$ only remove "2" factors). That's why multiple of 3 are leaves in the collatz tree. $\endgroup$ – Collag3n May 24 at 17:42
2
$\begingroup$

The statement is correct. I think the reason you can't find it in the literature is that it is fairly obvious as well:

If $2^{m-1}(6k-3)$ is part of a cycle, then there must exist a largest $r$ such that with the same $k$, $2^r(6k-3)$ is part of that cycle. What can its predecessor be?

It can't be $2^{r+1}(6k-3) > 2^r(6k-3)$ because $r$ was the largest exponent with that property. So it would have to be some $n$ such that $$ 2^r(6k-3) = 3n+1 $$ But the LHS of that equation is divisible by $3$ and the RHS is not.

Now if you showed that $2^m(8k-3)$ cannot be part of a cycle, that would be non-trivial enough to be worth mentioning in the literature.

$\endgroup$
0
$\begingroup$

More generally no multiple of $3$ sits within any cycle, because a) no multiple of $3$ is in the image of $3x+1$, and b) $x/2$ is nullipotent over the property of being a multiple of $3$.

Another way of looking at this is that considering the subgraph consisting only of odd numbers, the multiples of three are the leaves of the graph - obviously no leaf can be within a cycle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy