2
$\begingroup$

The hailstone sequence for a number $n$ has you repeatedly replacing it with $\frac{n}{2}$ (if even) or $3n + 1$ (if odd), until you reach 1, at which point the sequence stops. Let's call the length of this sequence $L(n)$.

So, for example, $L(3) = 8$ because the hailstone sequence from 3 goes $3\to 10\to 5\to 16\to 8\to 4\to 2\to 1$ (8 different numbers).

My question is, what is the rough growth order of $L(n)$, in terms of Big-O or Big-$\Theta$ notation. For example, I could say that the probability a number $n$ is prime grows as as $\Theta\left(\frac{1}{\ln (n)}\right)$. I want a similar statement about the growth order of $L(n)$.

I know $L(n)$ can vary wildly from number to number, so feel free to define "roughly" in any reasonable way to provide an answer (e.g. "roughly" could mean the moving average of $L(n), L(n+1), \ldots, L(n+100)$, or anything like that). Or else, feel free to give an upper limit in terms of big-O notation.

Bonus points if you could provide a simple intuition for the answer.

I'm sure there's not really a proof for anything I'm asking for, so the apparent/empirical answer is totally fine.

$\endgroup$
2
  • 1
    $\begingroup$ This is just the Collatz-sequence and it is unknown whether there are divergent sequences (sequences with infinite many entries). No idea how we can estimate the length assuming Collatz is true. $\endgroup$
    – Peter
    Aug 14 at 17:17
  • $\begingroup$ @Peter like I say at the end of my post: I'm sure there's no proved answer (as that'd probably be akin to proving the Conjecture itself @.@). But any apparent/empirical answer would be nice, if one has found one. $\endgroup$
    – chausies
    Aug 14 at 19:45

1 Answer 1

Reset to default
0
$\begingroup$

Using a probabilistic argument, the ratio of successive odd integers in a Collatz sequence is on average $3/4$. http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/node3.html So starting with an odd integer the number of odd integers in the sequence to get to $1$ is given by $$ n\left(\frac{3}{4}\right)^{L_{odd}(n)} = 1$$ To get from one odd integer to the next takes 3 steps on average ($1$ $3n+1$ and $2$ divide by $2$'s) so $$L(n) = 3L_{odd}(n) = \frac{-3ln(n)}{ln\left(\frac{3}{4}\right)} \approx 10.428ln(n)$$ See Average number of steps in the Collatz conjecture.

$\endgroup$
2
  • $\begingroup$ Perfect answer! Can confirm it's accurate up to 10^8 i.imgur.com/IquTVtS.png . As a follow-up, it seems that the "variance" also seems to increase at a regular rate. I wonder if anyone has characterized the growth rate of the variance (or any higher moments, or just outright, what the distribution of L(n) is @.@). $\endgroup$
    – chausies
    Aug 14 at 21:29
  • $\begingroup$ @chausies I'd be really surprised if any statistical test yielded anything different than "it's like as if the number of powers of 2 is randomly chosen from the discrete exponential distribution after a 3N+1 step." $\endgroup$
    – Jake Mirra
    Aug 14 at 22:27

You must log in to answer this question.

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