2
$\begingroup$

Consider

$$n \rightarrow ... \rightarrow an+b$$

to be a sequence of natural numbers to which we apply $3n+1$ or $\frac{n}{2}$ operations.

This sequence is called a cycle, if and only if $an+b=2n$.

(one can define it as $an+b=\frac{n-1}{3}$ as well, but it is the same thing, just shifted to other place)

If we use operations above and rewrite the necessary condition of a cycle, we get its general form

$$ \frac{3^k}{2^l}n+\frac{3^{k-1}}{2^{l_1}}+\frac{3^{k-2}}{2^{l_2}}+...+\frac{1}{2^{l_k}}=2n, $$ where $l \geq l_1 \geq l_2 \geq ... \geq l_k \geq 0$ are natural numbers, including $k$.

Let's define $m=2 \cdot 2^l$ and $m_k=2 \cdot 2^{l_k}$, so we get the final form:

$$ \frac{3^k}{2^m}n+\frac{3^{k-1}}{2^{m_1}}+\frac{3^{k-2}}{2^{m_2}}+...+\frac{1}{2^{m_k}}=n $$

and $\frac{3^k}{2^m} \in (0; 1)$.

$\mathbf Question:$ Is there any progress on solving such exponential diophantine equations?

From the first look it feels like a solid approach to the cycle problem, but perhaps it's way more difficult complication than it seems.

By intuition, can you think of a reason why only $n=1;2$ would be the solutions to this problem? Why $n=3$ has no solution?

$\mathbf Edit:$ To make things more clear, $n \rightarrow ... \rightarrow an+b$ sequence precisely follows the Collatz Conjecture and its procedure (when and which operation to apply). Also the question is mainly aimed at the constructed diophantine equation and its behaviour.

$\endgroup$
2
  • 1
    $\begingroup$ Hmm, would you mind to specify the comparision/basic status with "progress"? Of course there's progress since the 1970ies, for instance, that if a cycles is n steps long, its smallest element must be at least so-and-so, or if the smallest possible element is (must be) at least a certain value, then the length of the cycle must be at least so-and-so. (Crandall 78, Elihaou ??) If the type of the cycle is restricted to be "circuit" (or "1-cycle") then there is no solution (Steiner, 76; Simons since 2000 strong improvements) So do you mean "progress from that" or something else? $\endgroup$ Apr 2, 2022 at 9:56
  • $\begingroup$ (...) btw. just to avoid misunderstanding: the math behind the proofs has been diophantine, in the end plus transcendence n.thy. (diophantine approximation to logarithms). I've once looked for the cycles of the generalized Collatz $mx+1$, and to have a chance at all to solve any solvable small subproblem I asked for the 2-step-cycle $b=(ma+1)/2^A \to a=(mb+1)/2^B$ restricted to $a=1$ ;-) Difficult enough for an amateur, but for this there was a solution, see my Q&A here in MSE and solution in MO mathoverflow.net/q/374382/7710 . (So as well a small progress...) $\endgroup$ Apr 2, 2022 at 10:02

2 Answers 2

3
$\begingroup$

If we allow ourselves to apply $n_{i+1} = 3n_i + 1$ even when $2 \mid n_i$, then we can find other cycles, for instance:

$$4 \xrightarrow{*} 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8$$

However, there is no solution to $3m+1 = 2^j \cdot 3k$ in the integers. That means there's no way to get to $6$ except from $12$, and no way to get there but from $24$, etc. Similarly, you can only get to $9$ from $18$, etc. So no $2^j \cdot 3k$ can never be a solution to this cycle.

I'm not sure anything other than multiples of $3$ are excluded from this "wonky" Collatz cycle, though cycles will get big. If we start with $5 \xrightarrow{*} 16 \xrightarrow{*} 49$, after another $20$ or so (standard) steps, we get to $10$.

But this only answers your final question; I know of no progress on that sort of Diophantine equation.

$\endgroup$
3
  • 1
    $\begingroup$ My edit was for a typo (a missing word). "However there is $no$ solution ..." $\endgroup$ Apr 1, 2022 at 4:08
  • $\begingroup$ Excellent catch, thank you. $\endgroup$ Apr 1, 2022 at 4:31
  • $\begingroup$ Great observation about multiples of 3. I know that I didn't specify good enough, but the last part of my question was in the context of the diophantine equation: Can we get any intuition why equation fails for some $n$? If we can find a reason to that, then maybe other $n$ follow similar conclusions. Or in the best case, we could see why $n=1; 2$ solutions are in some way special. $\endgroup$ Apr 1, 2022 at 7:17
1
$\begingroup$

In case you start your question from simplest state, then I can show you a "progress" in proving of nonexistence of (nontrivial) 2-step and 3-step cycle, and from this method an extension to a handful of more $n$.

I write the transformation on odd $a$ such that $ b = {3a+1\over 2^A}$ with $A = \nu_2(3a+1)$, so $a$ and $b$ are both odd, and $A$ contains the number of steps of division-by-2.

1-step cycle

  • Now look at a $1$-step cycle: $$ a = { 3a+1 \over 2^A} \tag {1.1}$$ rewrite $$ 2^A = { 3a+1 \over a} = 3+ {1 \over a} \tag {1.2}$$ With simple diophantine arguments we see that we can only have the cycle with $a=1$ and $A=2$ and no others.

2-step cycle

  • Now look at a $2$-step cycle: $$ b = { 3a+1 \over 2^A} \to a = { 3b+1 \over 2^B} \tag {2.1}$$ rewrite $$ 2^{A+B} = { 3a+1 \over a} \cdot {3b+ 1 \over b} \\ = (3+{ 1 \over a})\cdot(3+{1 \over b}) \tag {2.2}$$ With still simple diophantine arguments we see that we can only have the cycle with $a=b=1$ and $A=B=2$ and no others (the rhs can only be in the interval $9 \ldots 16$ and $16=4^2$ is the only perfect power of $2$ in this interval and thus in both parentheses the fraction must equal $1$).

3-step cycle

  • In the same way we look at a $3$-step cycle. But here, we get that the rhs could become a power of $2$ which is not $4^3=64$, but larger than $3^3=27$ namely $32=2^5$.
    Here we introduce the additional diophantine arguments, that

    • the elements $a,b,c$ cannot be $1$,
    • and must be $\pm 1 \pmod 6$
    • and must be pariwise different

    so can at least be $(a,b,c)=(5,7,11)$. Inserting this in the rhs gives something smaller than $32$ and increasing any of the $(a,b,c)$ would furtherly decrease the rhs below $32$.
    This shows by diophantine arguments only, that a nontrivial $3$-step cycle cannot exist.


In that way we can try other $n$ for the $n$-step-cycle and it is easy to generate a list for $n$ up to -say- $200$ for which the cycle cannot exist - purely based on diophantine arguments.

(I hope I didn't misread the intention of your question)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .