Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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
1  
@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

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer

I'm not used to this way of looking at the collatz-problem and seem to be unable to really open my mind for this at the moment. But possibly the following observations help anyway.
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.

I don't know immediately, whether such a representation helps when the focus is on the consideration of an interval as is in the current question, but maybe I can come back to that problem later again with a fresh idea...

share|improve this answer

For an interval $1..b$, all number congruent 2, 4, 5, or 8 modulo 9 can be ignored because of these productions staring with a smaller number:

$$6z + 1 \rightarrow 18z + 4 \rightarrow 9z + 2$$ $$6z + 3 \rightarrow 18z + 10 \rightarrow 9z + 5$$ $$6z + 5 \rightarrow 18z + 16 \rightarrow 9z + 8$$

$$8z + 3 \rightarrow 24z + 10 \rightarrow 12z + 5 \rightarrow 36z + 16 \rightarrow 18z + 8 \rightarrow 9z + 4$$

Similarly, all numbers congruent 5 modulo 8 can be ignored as these two paths coalesce after three steps:

$$8z + 5 \rightarrow 24z + 16 \rightarrow 12z + 8 \rightarrow 6z + 4$$ $$8z + 4 \rightarrow 4z + 2 \rightarrow 2z + 1 \rightarrow 6z + 4$$

This way we reduce the set of numbers to be checked by a factor of $\frac59\cdot\frac78 = \frac{35}{72}$.

Also the lower half of the interval can be skipped (as even numbers will "fall" into them), again saving factor 2. So a reduction to about one quarter can be gained(*).

But the more important speedup can be obtained by doing multiple steps at once as described in the Wikipedia. With a small table of $2^{17}$ elements, 17 steps at once can be done, leading to a speed up of maybe 10 (the steps are a bit more complicated than a direct computation). AFAIK this is the biggest table fitting into cache.

When searching for the maximizer, the number of yet needed steps to overreach the current maximum can be used for a lookup in a a table derived from this one to determine if the current value needs to be expanded further. This gives an additional factor 2 for the interval $1..10^{10}$.

This fantastic link gives a lot of more complicated optimization tips allowing to skip checking most of remaining numbers.


(*) For a general interval $a..b$, this applies only partially.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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