Project Euler:#14 Integer overflow and Stack overflow

Question

unsigned long long terms;
unsigned long long test;
unsigned long long digit = 1;
unsigned long long max = 0;

//cout<<sizeof(long)<<" "<<sizeof(int)<<endl;
//cout<<digit<<endl;
for(;digit<1000000;++digit)
{
    terms = 1;
    test = digit;
    while(test>1)
    {
        if(0==(test%2))
        {
            test /=2;
        }else{
            test = test *3 +1;
        }
        terms ++;
    }   
    if(terms>max)
        max = terms;
}
//terms = get_chain_length();

/*if(terms>max)
        max = terms;*/
//cout<<sizeof(long long)<<endl;
cout<<max<<endl;

It is out of INT_MAX, how can I correct it? I try to use Hash_map in a recursive way, but stack over.

though the problem is well known, this looks like a spoiler solution for everyone wasting time on Project Euler! — ShinTakezou, Jul 20 '11 at 17:55

score 2 · Accepted Answer · answered Jul 20 '11 at 11:00

2

This is the Collatz Conjecture. Consider using memoization to solve the problem by storing the lengths of the chains you've seen for (e.g. if 6 gives a chain length of 7 and you encounter 6 when processing change N, then you can just add 7 to the chain length so far and immediately return).

answered Jul 20 '11 at 11:00

Jeff Foster

43,770
11
86
103

I used to utilize a buffer to store the results got before when processing between 0 and 1,000,000,but stack over occured . – sinjon666 Jul 20 '11 at 11:15
Perhaps add that code to the ticket? See related ticket http://stackoverflow.com/questions/2643260/project-euler-question-14-collatz-problem for an example solution. – Jeff Foster Jul 20 '11 at 11:58

Project Euler:#14 Integer overflow and Stack overflow

1 Answers1