Where can i find a proof that the allowable dropping times on the collatz conjecture are $\lfloor1 + n \cdot \log_2(3)\rfloor$

Question

In the shortcut collatz function $$ T(x) = \begin{cases} \frac{x}{2} & \text{if } x \equiv 0 \pmod{2} \\[2ex] \frac{3x + 1}{2} & \text{if } x \equiv 1 \pmod{2} \end{cases} $$

The dropping time of $n$ is the number of steps it takes for $n$ to reach a value smaller than the initial seed. That would make the dropping time of $1$ undefined, so other way you could define the dropping time of $n$ is the number of steps it takes for $n$ to reach a number smaller or equal to the seed, but you need to apply the function at least once.

i.e. $$D(x) = \text{smaller $k$ such that } T^k(x) \le x \text{ for } k \in \mathbb{Z}^{+}$$

Acording to the OEIS sequence A020914, the allowable values that a dropping time can be are $\lfloor1 + n \cdot \log_2(3)\rfloor$, where can i find a proof for that?

---

Edit:

Also, for the non-shortcut version

$$ f(x) = \begin{cases} \frac{x}{2} & \text{if } x \equiv 0 \pmod{2} \\[2ex] {3x + 1} & \text{if } x \equiv 1 \pmod{2} \end{cases} $$

According to the OEIS sequence A122437, the allowable values of dropping time using this original function is $\lfloor 1 + (n - 1)\log_2(6) \rfloor$ which is the same as $\lfloor 1 + (n - 1)(\log_2(3) + 1) \rfloor$

a(n) is also the number of binary digits of 6^(n-1); for example, a(4)=8 since 6^(4-1)=216 in binary is 11011000, an 8-digit number. - Julio Cesar de la Yncera, Mar 28 2009

Answer 1

This is a comment not an answer, but too long for the comment box

Mike Winkler in his text on the "algorithmic structure of the finite stopping time (...)" (see arXiv) should have a proof (or a reference to a proof). Most likely you can go from the following screenshot:

Here it is to mention, that in OEIS.org/A020914 is no proof/link to a proof provided. Don't know, whether in one of [OEIS 5] "The On-Line Encyclopedia of Integer Sequences (OEIS), A020914, A022921, A056576, A076227, A100982, A177789 (http://oeis.org)" such a proof is provided.
And I don't see immediately, that proof of theorem 1 follows from proof of theorem 2; no idea.

---

(I'm currently trying to formulate such a proof on my own, but either it is completely trivial or I don't get the problem correctly, I'm not at an end with this... )

---

Mike Winkler points towards an article by L.E.Garner (1981, available at JStor) who comes near a proof, see one short part from screenshot (coloured enhancements by me, G.H.):

but where he leaves it conditionally on not too many odd terms. (This is where I've got stuck myself and which I'm trying to make explicite/omissible).
Second part of screenshot:

So Garner(1981) left it conjectured that dropping times are not larger than $\lceil N \cdot \log_2(3) \rceil$ ($N$ denoting the number of odd steps)

Answer 2

I don't know if this consideration is trivial but I use the analogous transformation

$S(x) =\begin{cases}\frac{x}{2^{b_0}} \quad \quad\text{if } x \equiv 0 \pmod{2} \quad\text{with } b_0=\nu_2(x) \\ \frac{3\cdot x + 1}{2^{1+b_j}} \quad \text{if } x \equiv 1 \pmod{2}\quad \text{with } b_j=\nu_2(3\cdot x + 1)-1\end{cases}$

then fixed

$b_0 =\begin{cases}\nu_2(x) \: \quad\text{if } x \equiv 0 \pmod{2} \\ 0 \quad\quad\quad\text{if } x \equiv 1 \pmod{2} \end{cases}$

$T^k(x)=\begin{cases} \frac{x}{2^k}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \text{if } k\leq b_0\\ \frac{3^o\cdot \frac{x}{2^{b_0}} +3^{o-1} +\sum\limits_{i=0}^{o-2}{3^{i}\cdot2^{(o-1-i +\sum_{j=1}^{o-1-i} {b_j})}} }{2^{(o +\sum_{j=1}^{o}{b_j})-c}} \quad\quad\text{if } k> b_0 \end{cases}$

with $\: c \:$ chosen to have $ \: T^k(x)< x \:$ and $ \: 2\cdot T^k(x)> x \:$ and $\: o \:$ number of odd elements in the sequence until $2^c \cdot T^k(x)$ excluding $\:\frac{x}{b_0}$

so it must be for $\: k> b_0$

$\frac{3^o\cdot \frac{x}{2^{b_0}} +3^{o-1} +\sum\limits_{i=0}^{o-2}{3^{i}\cdot2^{(o-1-i +\sum_{j=1}^{o-1-i} {b_j})}} }{2^{(o +\sum_{j=1}^{o}{b_j})-c}} <x$

then

$\frac{3^o\cdot \frac{x}{2^{b_0}} }{2^{(o +\sum_{j=1}^{o}{b_j})-c}} <x \quad $ and $\quad 3^o <2^{(b_0+o +\sum_{j=1}^{o}{b_j})-c} $

with dropping time $k=b_0+o+\sum_{j=1}^{o}{b_j}-c $

but also for the condition imposed on $c$

$2 \cdot \frac{3^o\cdot \frac{x}{2^{b_0}} +3^{o-1} +\sum\limits_{i=0}^{o-2}{3^{i}\cdot2^{(o-1-i +\sum_{j=1}^{o-1-i} {b_j})}} }{2^{(o +\sum_{j=1}^{o}{b_j})-c}} >x$

from this I think that the condition $k=\lfloor 1+o\cdot \log_2 3\rfloor$ can be demonstrated.

Edit: in a similar way for the non-shortcut version

$T^{II}(x) =\begin{cases}\frac{x}{2^{b_0}} \quad \quad\text{if } x \equiv 0 \pmod{2} \quad\text{with } b_0=\nu_2(x) \\ \frac{3\cdot x + 1}{2^{b_j}} \quad \text{if } x \equiv 1 \pmod{2}\quad \text{with } b_j=\nu_2(3\cdot x + 1)\end{cases}$

then fixed

$b_0 =\nu_2(x) $

$f^k(x)=\begin{cases} \frac{x}{2^k}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \text{if } k\leq b_0\\ \frac{3^o\cdot \frac{x}{2^{b_0}} +3^{o-1} +\sum\limits_{i=0}^{o-2}{3^{i}\cdot2^{\sum_{j=1}^{o-1-i} {b_j}}} }{2^{(\sum_{j=1}^{o}{b_j})-c}} \quad\quad\text{if } k> b_0 \end{cases}$

with with $\: c \:$ chosen to have $ \: f^k(x)< x \:$ and $\: o \:$ number of odd elements in the sequence until $2^c \cdot f^k(x)$

naturally for $x$ even the dropping time $\: k=1\:$ so it must be for $x$ odd $\: k> b_0 \:$ with $\: b_0=0$

$\frac{3^o\cdot \frac{x}{2^{b_0}} +3^{o-1} +\sum\limits_{i=0}^{o-2}{3^{i}\cdot2^{\sum_{j=1}^{o-1-i} {b_j}}} }{2^{\sum_{j=1}^{o}{b_j}-c}} <x$

then

$\frac{3^o\cdot \frac{x}{2^{b_0}} }{2^{\sum_{j=1}^{o}{b_j}-c}} <x \quad $ and $\quad 3^o <2^{b_0 +\sum_{j=1}^{o}{b_j}-c} $

with dropping time $k=b_0+o+\sum_{j=1}^{o}{b_j}-c $

then $\quad 3^o <2^{k-o} \quad$ and $\quad k > o + o \cdot\log_2(3)=o\cdot\log_2(6) $

Answer 3

update (now another comment) An attempt to a proof, but retracted as noticed by user @Collag3n. Possibly interesting as a proof strategy, see Theorem 2 in Yu/Pei [2017] , screenshot:

The file is at arXiv:1710.01525v1 [math.NT] 4 Oct 2017

Header:

On the Glide of $3x+1$ Problem
Yuyin Yu, Dingyi Pei
(...)
Abstract
For any positive integer $n$, define an iterated function $$f(n) = \begin{matrix} n/2, & \text{ if $n$ even,} \\ 3n + 1, & \text{if $n$ odd.} \end{matrix} $$ Suppose $k$ (if it exists) is the lowest number such that $f^k (n) \lt n$, and there are $O(n)$ “multiply by three and add one” and $E(n)$ “divide by two” from $n$ to $f^k(n)$, then there must be $$2^{ E(n) − 1} < 3^{ O(n)} < 2^{ E(n)}$$ .
Our results confirm the conjecture proposed by Terras in 1976.

Their proof follows on page 7, but I've no time at moment to try to decode/confirm it...

Answer 4

I tried to prove it for the shortcut version myself, please let me know if there are any mistakes

---

Let $E(n) := \frac{1}{2}n$, referred to as even step, and $O(n) := \frac{1}{2}(3n + 1)$, referred to as odd step. Then the Collatz function $T:\mathbb{Z} \rightarrow \mathbb{Z}$ is given by $$ T(n) := \begin{cases} E(n), & \text{if $n$ is even} \\[2ex] O(n), & \text{if $n$ is odd} \end{cases} $$ This function is applied recursively by the notation \begin{align*} T^0(n) &:= n \\ T^k(n) &:= T(T^{k - 1}(n)), k \in \mathbb{Z}^+ \end{align*}

Let $\delta(n)$ (dropping time of $n$) be the smallest integer $k$ such that $T^k(n) < n$.

Every integer follows a certain path of applying the even and odd step functions until it reaches a smaller value, for example, $3$ follows the path $3 \xrightarrow{\text{O}} 5 \xrightarrow{\text{O}} 8 \xrightarrow{\text{E}} 4 \xrightarrow{\text{E}} 2$, so $E(E(O(O(3))))$ is the function that joins all steps in the path it took. Let $L_k$ be the function that takes all steps that $k$ made until it dropped and join into a single function, so for $k = 3$, $L_3(n) = E(E(O(O(n)))) = \frac{1}{2}(\frac{1}{2}(\frac{1}{2}(3(\frac{1}{2}(3(n) + 1)) + 1))) = \frac{9}{16}n + \frac{5}{16}$.

Let $|L_k|$ be the total amount of steps that were joined, and $P(L_k)$ be the amount of odd steps.

Lemma 1. If n is positve and $\delta(n)$ is finite, then $L_k(n) = \frac{3^{P(L_k)}}{2^{|L_k|}}n + c$, where $c$ is some non-negative constant.

Proof. The even step function $\frac{1}{2}n$ can be written as $\frac{3^0}{2^1}n$ and the odd step function $\frac{1}{2}(3n + 1)$ can be written as $\frac{3^1}{2^1}n + \frac{1}{2}$, on both steps the exponent of $2$ in the denominator is incremented by $1$, so the denominator of the coefficient will be $2^{|L_k|}$, and on the the exponent of $3$ on the numerator is incremented by $1$ on the odd step, and by $0$ on the even step, so the numerator will be $3^{P(L_k)}$. And for the constant $c$, the only things that can affect it is the addition of $\frac{1}{2}$ on the odd step and the division by $2$ on the even step, which cannot make it negative.

Lemma 2. The smallest integer $k$ such that $2^k > 3^n$ is $\lfloor n \log_2(3) \rfloor + 1$.

Proof. $2^k > 3^n \implies k > \log_2(3^n) \implies k > n\log_2(3)$. The smallest integer $k$ that satisfies $k > n\log_2(3)$ is $\lfloor n\log_2(3) \rfloor + 1$, this is because $\lfloor n\log_2(3) \rfloor$ is the biggest integer that is less than or equal to $n\log_2(3)$, so $\lfloor n\log_2(3) \rfloor + 1$ is the smallest integer that is bigger than $n\log_2(3)$. Therefore, $\lfloor n\log_2(3) \rfloor + 1$ is the smallest integer solution of $k$ for $2^k > 3^n$.

Theorem. If $n$ is positive and $\delta(n)$ is finite, then $\delta(n) \in \{\lfloor k \log_2(3) \rfloor + 1 \mid k \in \mathbb{N}_0\}$.

Proof. By definition, the first value smaller than $k$ that appear on the sequence of applying the Collatz function is $L_k(k)$, which, as seen in lemma 1, can be written as $\frac{3^{P(L_k)}}{2^{|L_k|}}k + c$, so $$\frac{3^{P(L_k)}}{2^{|L_k|}}k + c < k$$

As $c$ is positive, it is correct to say that

$$\frac{3^{P(L_k)}}{2^{|L_k|}}k < \frac{3^{P(L_k)}}{2^{|L_k|}}k + c$$

And using the transitive property of inequalities, the previous statements imply

$$\frac{3^{P(L_k)}}{2^{|L_k|}}k < k$$

$k$ is positive and therefore can be divided without flipping the sign to get

$$\frac{3^{P(L_k)}}{2^{|L_k|}} < 1$$ $$\implies 3^{P(L_k)} < 2^{|L_k|}$$ $$\implies 2^{|L_k|} > 3^{P(L_k)}$$

As $\delta(n)$ is the minimum amount of steps necessary to reach a smaller value, just the smallest integer solution for $|L_k|$ should be considered, which as proven in lemma 2, is $\lfloor P(L_k) \log_2(3) \rfloor + 1$. Hence, $\delta(n) \in \{\lfloor k \log_2(3) \rfloor + 1\ \mid k \in \mathbb{N}_0\}$.

---

Notice that this does not prove that every number in the form $\lfloor n \log_2(3) \rfloor + 1$, $n \in \mathbb{N}_0$ can be a dropping time, just that every dropping time is in this form. For that it would need a proof that any natural number can be $P(L_k)$, which I could not think of one.

Answer 5

Perhaps these elementary observations can help.

We denote the stopping time by $\quad k $.

If $ n$ is even then $ k = 1 $ and $\quad n\rightarrow \frac{n}{2}$.

If $ n\equiv 1\pmod{2^{2}}$ then $k = 3\quad$and$ \quad n\rightarrow \frac{3\cdot n+1}{2^{2}}$ .

Fixed $\quad o \quad$ with$\quad o>1\quad$if $\quad n\quad$ odd and $ \quad n\equiv r\pmod{2^{k-o}}\quad$with $r>1$ then it is possible to observe that

$ n\rightarrow \frac{3^o\cdot n+b}{2^{k-o}} \quad$

so if $\quad k\quad $ is the stopping time and $ n= r + q \cdot 2^{k-o}$

$ n_k = \frac{3^o\cdot n+b}{2^{k-o}}= \frac{3^o\cdot r+b}{2^{k-o}} +q \cdot 3^o < r + q \cdot 2^{k-o}$ for any value of $q$ and it must be $\quad3^o< 2^{k-o}\quad$

if $\quad q=0\quad$ then $ \frac{3^o\cdot r+b}{2^{k-o}}<r\quad \rightarrow\quad b<r\cdot (2^{k-o} - 3^o)$

but it also must be $n_{k-1}=2\cdot n_k>n$

$ 2\cdot( \frac{3^o\cdot r+b}{2^{k-o}} +q \cdot 3^o) > r + q \cdot 2^{k-o}$

then if $\quad q=r$

$ 3^o\cdot r+b + r \cdot 3^o\cdot 2^{k-o} > r \cdot 2^{k-o-1}+ r \cdot 2^{k-o}\cdot 2^{k-o-1}$

$ 3^o\cdot r+r\cdot (2^{k-o} - 3^o) +r \cdot 3^o\cdot 2^{k-o} > 3^o\cdot r+b +r \cdot 3^o\cdot 2^{k-o-1} > r \cdot 2^{k-o-1}+ r \cdot 2^{k-o}\cdot 2^{k-o-1}$

$ 3^o +2^{k-o} - 3^o+ 3^o\cdot 2^{k-o} > 2^{k-o-1}+ 2^{k-o}\cdot 2^{k-o-1}$

$ 2^{k-o}+ 3^o\cdot 2^{k-o} > 2^{k-o-1}+ 2^{k-o}\cdot 2^{k-o-1}$

$ 1+ 3^o > 2^{-1}+ 2^{k-o-1}\quad$ then $\quad 2^{k-o-1}<3^o < 2^{k-o}$

In this graph you can view the described observations