Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
This question is inspired by a CS 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 conjectures Collatz).
What can we say, if anything, about the size of the highest number in the resulting sequence in relation to n?
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.
We can say that if $m$ is $2^n$ it is $n$. 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^m-1}{3}, or other numbers which we can obtain working backwards).
Of course we cannot say anything just knowing the size of $n$, since this would essentially be the same as proving the conjecture.
For every initial value, the recurrence relation leads to either one of the following cases:
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.
