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
@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
@Thijs Good point. Thank you! –  FUZxxl Aug 29 '11 at 19:22
Not only can you skip testing $n$ if $2n\le 10^9$, but you can also skip $n$ whenever $n=3m+1$ or $2n=3m+1$, because $m$ would give you a longer sequence. So, you only need to test multiples of 3. Only problem is that this would miss cycles, which give an infinite sequence... –  George Lowther Aug 29 '11 at 23:39
@Thijs: Yes, you're correct. You can only skip $n=3m+1$ and $2n=3m+1$ for odd $m$. So, skip $n=2$ (mod 3) and $n=4$ (mod 6). –  George Lowther Aug 30 '11 at 0:06

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.