3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You might want to add the definitions of a "hailstorm" sequence. $\endgroup$ – Teoc Jan 27 '15 at 2:47
  • $\begingroup$ 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. $\endgroup$ – David G. Stork Jan 27 '15 at 2:51
  • $\begingroup$ The term is hailstone mathworld.wolfram.com/HailstoneNumber.html $\endgroup$ – Fred Kline Jan 27 '15 at 2:52
  • $\begingroup$ Thank you all for the clarifications! I have edited to reflect them. $\endgroup$ – Kyle Jan 27 '15 at 2:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Milo Brandt Jan 27 '15 at 3:12
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kyle Jan 27 '15 at 5:16
  • $\begingroup$ $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$). $\endgroup$ – TonyK Jan 28 '15 at 10:12
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.