Project Euler #14

[mcr99]

I'm a beginner, I'm trying to solve problem 14 of Project Euler (https://projecteuler.net/problem=14). Here is my code; Can anyone help me to figure out what I'm doing wrong?

#include <iostream>
#include <vector>

int main() {
    
    std::vector<int> chain;
    std::vector<int> biggestChain;
    

    for(int i = 1000000; i > 13; i--) {
        
        int numToTest = i;
        
        while(numToTest > 1) {
            
            if(numToTest % 2 == 0) {
                numToTest /= 2;
                chain.push_back(numToTest);
            }
            
            else {
                numToTest = numToTest * 3 + 1;
                chain.push_back(numToTest);
            } 
        }
            
        if(chain.size() > biggestChain.size()) {
            
            biggestChain.clear();
            
            for(auto i : chain) {
                biggestChain.push_back(i);
            }
        }
        chain.clear();
    }
    
   std::cout << biggestChain.front() << std::endl;
   
}

[dutch]

Your mistake is to assume that all the values in the sequence will fit in an int (usually 32 bits). Try long (should be 64 bits on a 64 bit computer) or long long (guaranteed to be 64 bits on any system) instead. Even though you are starting with numbers that easily fit in 32-bits, some intermediate numbers don't.

There's no reason to store the chain. You just need a counter for the current and max sizes, and a place to store the current max starting number.

And there's no reason to count backwards (and if you do you should start at 999999 since the problem doesn't include a million). And you really should test 2 to 12 as well.

#include <iostream>

const int Limit = 1000000;

int main() {
    int maxi = 0, maxlen = 1;
    for (int i = 2; i < Limit; ++i) {
        int len = 1;
        for (long n = i; n > 1; ++len)
            n = n % 2 ? n * 3 + 1 : n / 2;
        if (len > maxlen) {
            maxlen = len;
            maxi = i;
        }
    }
    std::cout << maxi << ": " << maxlen << '\n';
}

[mcr99]

Thank you!

[dutch]

You're welcome. You can speed it up quite a bit (although it's not really necessary) by "memoizing" the answers as you generate them:

#include <iostream>
#include <vector>

const int Limit = 1000000;

int main() {
    std::vector<int> lens(Limit); // All values initialized to 0.
    lens[1] = 1; // Answer for 1 is length 1.

    int maxi = 1, maxlen = 1; // Initialize to the answer for 1.

    for (int i = 2; i < Limit; ++i) {

        int len = 0;

        long n = i;
        while (true) {
            if (n < Limit && lens[n] != 0)
                break; // Break when we find an answer in the table.
            n = n % 2 ? n * 3 + 1 : n / 2;
            ++len;
        }

        len += lens[n]; // Add in answer from table.
        lens[i] = len;  // Store this answer in the table.

        if (len > maxlen) {
            maxlen = len;
            maxi = i;
        }
    }

    std::cout << maxi << ": " << maxlen << '\n';
}