Euler 14 Help

[adam webb]

Hi All,

Hope you don't mind me asking this here. I'm new to C++ having learnt Python and BASIC years ago at school I figured it was time to learn a 'real' programming language.

I've been working my way through the Euler problems, but problem 14 is stumping me... The problem (http://projecteuler.net/problem=14) is Collatz' Problem, which should (I thought) be fairly simple to solve using an iterative method.

I have googled and googled, but haven't found anyone else with a similar problem with me. I am 95% sure that the problem doesn't involve integer overloads or similar (but I am using long long int just incase).

I know this is probably not the quickest of methods, and if I was going to speed I would have used a dynamic method, storing solutions as I went.

So here is my code:

#include <iostream>

using namespace std;

long long int noIts(long long int n)
{
    /* This itterative function returns the number of iterations to get to n = 1.
    The only variable which we are working with is n, the current number in the Collatz
    Sequence.
    The function returns the number of iterations which it takes n to get to n = 1
    */

    if (n == 1)
        //Have we reached the end of the sequence?
        return 1;

    if (n % 2 == 0)
        //If n is even
        return (noIts(n/2) + 1);
    else
        //If n is odd
        return (noIts(3*n + 1) + 1);

}

int main()
{
    //the maximum number which we will loop to
    long int const maxStart = 1e6;

    //to store the number with the most iterations so far
    long int iMax = -1;

    //loop through all numbers bellow maxStart
    for (long int i = 1; i <= maxStart; i++)
    {
        if (iMax < noIts(i))
            iMax = i;
    }

    //display the final solution
    cout << iMax << endl;

    return 0;
}

Now this code keeps giving me the solution 35655 (after about a second of working), which apparently uses 324 iterations to get to 0, but the Euler website keeps telling me I'm wrong.

I have spent a long time looking over this, making small changes, and trying to debug, but I can't find where I have gone wrong.

If anyone can give me a hint as to where I should be looking, it would be very much appreciated!

Cheers

Adam

PS. If it helps, I am using Ubuntu 11.10, gpp to compile, and Code::Blocks to write

[ne555]

Read aloud

        if (iMax < noIts(i))
            iMax = i;

[JLBorges]

Sequence lengths for many of the smaller values would be needed millions of times. Expending a little memory for remembering the values which have been computed earlier would be worth while.

@adam webb - do not read any further before you have fixed the error pointed out by ne555 and got your program to work.

#include <iostream>
#include <vector>

enum { N = 1000000 + 1 } ;

inline long long next( long long n ) { return n%2==0 ? n/2 : n*3+1 ; }

int seq_length( long long n, std::vector<int>& remembered )
{
    if( ( n <  N ) && remembered[n] ) return remembered[n] ;
    int len = 1 + seq_length( next(n), remembered ) ;
    if( n <  N ) remembered[n] = len ;
    return len ;
}

int main()
{
    std::vector<int> remembered(N) ;
    remembered[1] = 1 ;

    int longest = 1 ;
    int max_len_so_far = 1 ;
    for ( int i = 1 ; i <  N ; ++i )
    {
        int len = seq_length( i, remembered ) ;
        if( len > max_len_so_far )
        {
            max_len_so_far = len ;
            longest = i ;
        }
    }

    std::cout << longest << " sequence length: " << max_len_so_far << '\n' ;
}

[adam webb]

Thanks chaps, I'd found the error after ne555s first comment, I knew it would be something simple like that, but no matter how many times I read through the code I could not find it...

And JL, thanks very much for your input... I know that a dynamic approach would be better, but given my code still runs in a little over a second, I figured it wasn't worth the while... But thankyou very much for your snippit, it's good to see an example like that at my stage in learning!

THanks again

AW