C++ Euler-Problem 14 Program Freezing

Question

I'm working on Euler Problem 14: http://projecteuler.net/index.php?section=problems&id=14

I figured the best way would be to create a vector of numbers that kept track of how big the series was for that number... for example from 5 there are 6 steps to 1, so if ever reach the number 5 in a series, I know I have 6 steps to go and I have no need to calculate those steps. With this idea I coded up the following:

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
int main()
{
    vector<int> sizes(1);
    sizes.push_back(1);
    sizes.push_back(2);
    int series, largest = 0, j;
    for (int i = 3; i <= 1000000; i++)
    {
        series = 0;
        j = i;
        while (j > (sizes.size()-1))
        {
            if (j%2)
            {
                j=(3*j+1)/2;
                series+=2;
            }
            else
            {
                j=j/2;
                series++;
            }
        }
        series+=sizes[j];
        sizes.push_back(series);
        if (series>largest)
            largest=series;
        cout << setw(7) << right << i << "::" << setw(5) << right << series << endl;
    }
        cout << largest << endl;
    return 0;
}

It seems to work relatively well for smaller numbers but this specific program stalls at the number 113382. Can anyone explain to me how I would go about figuring out why it freezes at this number?

Is there some way I could modify my algorithim to be better? I realize that I am creating duplicates with the current way I'm doing it: for example, the series of 3 is 3,10,5,16,8,4,2,1. So I already figured out the sizes for 10,5,16,8,4,2,1 but I will duplicate those solutions later.

Thanks for your help!

Answer 1

Have you ruled out integer overflow? Can you guarantee that the result of (3*j+1)/2 will always fit into an int?

Does the result change if you switch to a larger data type?

EDIT: The last forum post at http://forums.sun.com/thread.jspa?threadID=5427293 seems to confirm this. I found this by googling for 113382 3n+1.

Answer 2

I would try using a large array rather than a vector, then you will be able to avoid those duplicates you mention as for every number you calculate you can check if it's in the array, and if not, add it. It's probably actually more memory efficient that way too. Also, you might want to try using unsigned long as it's not clear at first glance how large these numbers will get.

Answer 3

I think you are severely overcomplicating things. Why are you even using vectors for this?

Your problem, I think, is overflow. Use unsigned ints everywhere.

Here's a working code that's much simpler and that works (it doesn't work with signed ints however).

int main()
{

    unsigned int maxTerms = 0;
    unsigned int longest = 0;
    for (unsigned int i = 3; i <= 1000000; ++i)
    {
        unsigned int tempTerms = 1;
        unsigned int j = i;
        while (j != 1)
        {
             ++tempTerms;

             if (tempTerms > maxTerms)
             {
                 maxTerms = tempTerms;
                 longest = i;
             }

             if (j % 2 == 0)
             {
                 j /= 2;
             }
             else
             {
                 j = 3*j + 1;
             }
        }
    }

    printf("%d %d\n", maxTerms, longest);

    return 0;
}

Optimize from there if you really want to.

Answer 4

When i = 113383, your j overflows and becomes negative (thus never exiting the "while" loop).

I had to use "unsigned long int" for this problem.

Answer 5

The problem is overflow. Just because the sequence starts below 1 million does not mean that it cannot go above 1 million later. In this particular case, it overflows and goes negative resulting in your code going into an infinite loop. I changed your code to use "long long" and this makes it work.

But how did I find this out? I compiled your code and then ran it in a debugger. I paused the program execution while it was in the loop and inspected the variables. There I found that j was negative. That pretty much told me all I needed to know. To be sure, I added a cout << j; as well as an assert(j > 0) and confirmed that j was overflowing.