Project Euler #14

Question

I am currently solving, Project Euler problem 14:

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)  

Using the rule above and starting with 13, we generate the following sequence:
               13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1  

Which starting number, under one million, produces the longest chain?

I devised the following algorithm to solve the problem:

• Instead of finding series for each number separately, which will contain lots of redundant calculation, I try to develop the series backwards from 1. That is, start from number and predict the element before it.
• Since multiple series can be generated, store the recent number of all series using a linked list. (The idea is to store only those elements that have longer series.)
• I will loop this, until I find all the numbers under the given limit; the last number under the limit will have the longest series.

Here is my code:

void series_generate(long num)
{
    long n = 1;
    addhead(n);             //add 1 to list.
    while (n < num) 
    {
            series *p;
            for (p = head; p != NULL; p = p->next)
            {
                    long bf = p->num - 1;
                    if (p->num%2 == 0 && bf != 0 && bf%3 == 0) {
                            bf /= 3;
                            if (bf != 1)
                                    addhead(bf);
                            if (bf < num)
                                    n++; 
                    }
                    p->num *= 2;
                    if ( p->num < num)
                            n++;

            }       
    }       
}

Here is the link to complete code. However, I don't get the answers as I expected. Can anyone expain why this algorithm won't work?

Answer 1

You're trying to build the Collatz tree backwards, level per level. Thus after the k-th iteration of the inner loop, the list contains (while no overflow occurred) all numbers needing exactly k steps to reach 1 in their Collatz sequence.

That approach has two serious problems.

1. The size of the levels increases exponentially, the size doubles roughly every three levels. You don't have enough memory to store levels past not much over 100.
2. The largest member in level k is 2^k. Depending on the used type for the num member, you get overflow at level 31, 32, 63 or 64. Then, if you use a signed type, you have undefined behaviour, probably negative numbers in the list, and all goes haywire. If you use unsigned types, your list contains a 0, and all goes haywire.

Since 27 needs 111 steps to reach 1, you have overflow whenever num > 27, therefore you get wrong results.