# Rough average length for the hailstone sequence produced from $n$?

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.

• 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. Aug 14 at 17:17
• @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. Aug 14 at 19:45

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.