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

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?

• You might want to add the definitions of a "hailstorm" sequence. – Teoc Jan 27 '15 at 2:47
• I believe he means the Collatz conjecture. 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). But how high will your sequence go for a given $n$? That is what is being asked. – David G. Stork Jan 27 '15 at 2:51
• The term is hailstone mathworld.wolfram.com/HailstoneNumber.html – Fred Kline Jan 27 '15 at 2:52
• Thank you all for the clarifications! I have edited to reflect them. – Kyle Jan 27 '15 at 2:54
• This paper has a vaguely related result (assuming the Collatz conjecture is true) - it proves certain bounds on a certain rational function of the terms of the hailstone sequence. – Milo Brandt Jan 27 '15 at 3:12

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. • I see! So since we have no proof of the conjecture, my question is unanswerable. I will instead focus on a certain range of inputs and confirm they are within an acceptable size. – Kyle Jan 27 '15 at 5:16 •$n$can't be$2^n$, can it? But if$n$is$2^m$, then the highest number reached is$n$, not$n+1$(or$m+1$). – TonyK Jan 28 '15 at 10:12 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.