1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 1. why not simply divide all twos out for the shortcut ? 2. How would we define the dropping time in the case of a divergent trajectory ? $\endgroup$
    – Peter
    Sep 25, 2023 at 15:13
  • 1
    $\begingroup$ @Peter, no specific reason, it's just that dividing all the twos seems less 'algebraic'. If the trajectory is divergent, then there is no number $k > 0$ such that $T^k(x) \le x$, so it would be undefined. $\endgroup$ Sep 25, 2023 at 15:32
  • 1
    $\begingroup$ To my knowledge, there is no proof of that. Terras used some tricks in his proof to overcome this (math.stackexchange.com/questions/4605249/…) $\endgroup$
    – Collag3n
    Sep 25, 2023 at 18:22
  • $\begingroup$ Not really a proof but if you consider the original sequence you have $n_k=\frac{3^k \cdot n +3^{k-1}+\sum\limits_{j=0}^{k-2}{\displaystyle3^j\cdot \displaystyle2^{\sum _{i=1} ^{k-1-j} {a_i}}}}{ 2^{\sum _{i=1}^{k} { a_i}}}$ if we fix the value of $ k$ for which $n_k<n$ the sequence A020914 refers to the number of bits in binary of $3^k$ . See also here $\endgroup$
    – user140242
    Sep 26, 2023 at 16:17
  • $\begingroup$ Also see comments in math.stackexchange.com/questions/3212129/… $\endgroup$
    – Collag3n
    Sep 28, 2023 at 18:04

5 Answers 5

1
$\begingroup$

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) $

$\endgroup$
11
  • $\begingroup$ That's not so simple. Take $4=\frac{3^5\cdot7+347}{2^9}$ bellow $7$ and $2\cdot4=\frac{3^5\cdot7+347}{2^8}$ above $7$. Dropping time would be $9$, but $\lfloor 1+o\cdot \log_2 3\rfloor=8$. I know what you will tell me, and I will respond: That's not detectable by your equations. $\endgroup$
    – Collag3n
    Oct 5, 2023 at 12:23
  • $\begingroup$ @Collag3n What you write is wrong. If $x=7$ the dropping time is $ k=7$ in the first case and $k=11$ in the second case for the non-shortcut version. In both cases $o=4$ and $5=\frac{3^4\cdot 7+73}{2^7}$. You cannot start from any number but you must consider the sequences based on the transformations. $\endgroup$
    – user140242
    Oct 5, 2023 at 13:56
  • 1
    $\begingroup$ Well that was an important part of my comment and I already responded: "I know what you will tell me....". Your equations don't know that, so you can't make them tell you something they don't know. In other word, you can't prove it that way $\endgroup$
    – Collag3n
    Oct 5, 2023 at 14:02
  • $\begingroup$ @Collag3n The equations are derived by adopting the transformations for example S(x) in the first case is a reduced version of $7\rightarrow 11\rightarrow 17\rightarrow 26\rightarrow 13\rightarrow 20\rightarrow 10\rightarrow 5 $. You can't take number $4$ at random as you wrote in the comment. The exact number is $5$ and comes from the Collatz sequence. $\endgroup$
    – user140242
    Oct 5, 2023 at 14:05
  • $\begingroup$ You still don't get it? 4 is perfectly valid in your equations, it is on the path of 7. 4 is bellow, and 8 is above 7....again nothing wrong. What is wrong is: This is the first drop bellow 7. And that parameter is not in your equations. So your equations will never be able to tell you something about that. $\endgroup$
    – Collag3n
    Oct 5, 2023 at 14:07
0
$\begingroup$

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:

CITE

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.):

bild2

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:

bild3

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)

$\endgroup$
0
$\begingroup$

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:

Bild4

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...

$\endgroup$
2
  • 1
    $\begingroup$ Their proof was not correct and the paper was later withdrawn (arxiv.org/abs/1710.01525v2) $\endgroup$
    – Collag3n
    Oct 4, 2023 at 13:27
  • 1
    $\begingroup$ @Collag3n - ufff! Didn't see that, had the paper downloaded a couple of years before. Thank you for inform us. So what is best to do with this "answer". Declare it as well as "comment", inserting the withdrawal-notification? I'd like to keep the fact that again an attempt has been tried, only without success... $\endgroup$ Oct 4, 2023 at 15:29
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ The smallest integer $k$ such that $T^k(n) < n$ is not the same as the smallest integer $k$ such that $2^k > 3^n$. Your proof seems to blend the two. $\endgroup$
    – Collag3n
    Dec 15, 2023 at 19:33
  • $\begingroup$ @Collag3n couldn't fit the comment here, see https://imgur.com/a/1XusZ0A $\endgroup$ Dec 15, 2023 at 22:10
  • $\begingroup$ *the arrows on the example of the image should be $7 \xrightarrow{O} 11 \xrightarrow{O} 17 \xrightarrow{O} 26 \xrightarrow{E} 13 \xrightarrow{O} 20 \xrightarrow{E} 10 \xrightarrow{E} 5 \xrightarrow{O} 8 \xrightarrow{E} 4 \xrightarrow{E} 2 \xrightarrow{E} 1 \xrightarrow{O} 2 \cdots$ $\endgroup$ Dec 16, 2023 at 9:38
  • $\begingroup$ My point still holds, and we could have the exact same conversation as with user140242 bellow $\endgroup$
    – Collag3n
    Dec 16, 2023 at 10:26
0
$\begingroup$

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 enter image description here

$\endgroup$

You must log in to answer this question.

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