# Reducing the time to calculate Collatz sequences

I am solving the classical problem of calculating for which number in an interval $[a,b]$ the Collatz sequence takes the most steps to reach $1$. Is there an algorithm that needs less than $\cal O(n)$ time, to calculate the number of steps to reach $1$, where $n$ is the number of steps needed?

Additionally, I am interested in whether it is possible to achieve speedup by ruling out certain candidates of the input interval. I already do calculate some steps at once by viewing the input $a \bmod 2^k$ for some $k$, but the extra memory that is needed is quite much.

-
When you run the Collatz recursion you get much more than just information about how long it takes for your starting number to terminate: you also know how long it takes for any number you ran into along the way to terminate, so you can eliminate all of those numbers as candidates. Furthermore, if on any subsequent computation you run into a number you've seen before, you're done with that computation as well. –  Qiaochu Yuan Aug 29 '11 at 18:59
I don't think any more efficient method of calculating this number of steps is known. In any case, you could try browsing through Lagarias' annotated bibliographies (1,2) and see if anything of interest is listed there. –  TMM Aug 29 '11 at 19:03
@Qiachu But then, I would need to save all that information. Assume, that I want to test all $n$ in the intervall $[1,1\,000\,000\,000]$ - I would need about 1 GiB just for caching! But otherwise, a good idea. –  FUZxxl Aug 29 '11 at 19:04
Actually, one trivial but perhaps useful fact is that the sequence starting at $2n$ is longer than the one starting at $n$. So instead of checking $[1,1000000000]$ for the maximum, it suffices to check only $[500000001,1000000000]$. –  TMM Aug 29 '11 at 19:21
@Thijs Good point. Thank you! –  FUZxxl Aug 29 '11 at 19:22
show 3 more comments

The expert on large-scale Collatz computations is Tomás Oliveira e Silva, who has a website with much information. Also worth a look is Eric Roosendaal's website.

-
If we look at the inverse operation, for odd $\small a_k$ define $\small a_{k+1,A} = (2^A*a_k -1)/3$ with all A that keep $a_{k+1,A}$ odd and integer and beginning at $\small a=1$ then this forms a tree which should contain all odd positive integers if the collatz-conjecture is true.
Then we see, that with some $\small a_k$ also all $\small 4 a_k + 1, 4(4 a_k+1)+1, ... ,{4^j a_k -1 \over 4-1 }, \ldots$ are in that tree. Similarly, this can be expressed using 64 instead of 4 and so on. See the graphic at http://go.helms-net.de/math/collatz/aboutloop/collatzgraphs.htm where I collected some types of tree-representations and particularly at the one which is expressed in the base-4-numbersystem.