Collatz conjecture: Largest number in sequence with starting number $n$

Question

This question is inspired by a C.S. course, and it only tangentially relates to the actual content of the exercise.

Say in a hailstone sequence (Collatz conjecture) you start with a number $n$. For any positive integer $n$, if $n$ is even, divide it by 2; otherwise multiply it by 3 and add 1. If you iterate this rule, for any $n$, you’ll get to 1 (or so Collatz conjectures).

What can we say, if anything, about the size of the highest number in the resulting sequence in relation to $n$?

Answer 1

We can say that if $m$ is $2^n$ it is $m$. Of course this is a rather cheap answer, we can say a lot of stuff like that about special numbers (Like numbers of the form $\frac{2^n-1}{3}$, or other numbers which we can obtain working backwards after a fixed sequence of moves).

We cannot say anything just knowing the size of $m$, this would come very close to proving the conjecture and such strong results aren't available at the time.

Answer 2

If you look at your considerations in terms of the notation $$a_{k+1}={3a_k+1\over 2^{A_k}} $$ where $a_k$ is odd and $A_k$ is such that also $a_{k+1}$ is odd then we can write for a number $a_k$ of the form $$ a_k = 4j_k+3 \to a_{k+1}=6j_k+5 $$ so this is an increase of about $3/2 a_k$ per iteration, as long as the form $6j_k+5$ can again be expressed by the form $4j_{k+1}+3$
Putting this initial observation in some table we can write $$\begin{array} {rrr|r|r|rrr|r} a_k & \to & a_{k+1} &A&& a_k & \to & a_{k+1}&A \\ \hline \color{red} {4j+3} & \color{red} {\to }&\color{red} { 6j+5 }&\color{red} {1}&& \color{orange} {8j+1} & \color{orange} {\to} & \color{orange} {6j+1} &\color{orange} {2}\\ 16j+13 & \to & 6j+5 &3&&32j+5 & \to & 6j+1 &4\\ 64j+53 & \to & 6j+5 &5&&128j+21 & \to & 6j+1 &6 \\ \vdots &&& \vdots&& \vdots&&& \vdots \end{array} $$ and get a (hopefully) obvious scheme for the translation of any (positive) odd number $a_k$ into its hailstone-follower $a_{k+1}$ via the exponent $A_k$
Only the numbers of the form $a_k = 4j+3$ increase (red color), only the number $a_k=8j+1$ with $j=0$ stays constant (the "trivial" and only cycle) (orange color), all other numbers decrease by the transformation.

For me, this is a nice illustration of the core of the transformation-process in terms of one step. It says to me, that, as long as the result $6j_k \pm 1$ is representable by another definition $2 \cdot 2^{A_{k+1}}j_{k+1} + r_{k+1}$ then this iterates go up and/or down in the indicated way, and especially, the possible number of iterates of type $A=1$ can be arbitrary as long as the resulting numbers are again of the form defined by $A=1$ (in the other answer it was said that this is for numbers $a_0 = 2 \cdot 2^m j_0 + 3$ which shall grow up to $a_m = 2 \cdot 3^m j_0 + 3$ and then - at least one time - fall down. But no more general prognose can be made today - otherwise the Collatz conjecture would be decided.

Answer 3

For every initial value, the recurrence relation leads to either one of the following cases:

1. Converge to the $4,2,1$ cycle
2. Converge to some other cycle
3. Diverge (i.e., never reach a previous value)

At present, only case #1 is known to happen.

If there exists an initial value of $n$ which leads to case #3, then the highest value is unbounded.

Until you prove that no such initial value exists, nothing else can be stated about the highest value.