C ++ Euler-Problem 14 Freeze Program

Question

I am working on Euler 14 issue: http://projecteuler.net/index.php?section=problems&id=14

I decided that the best way would be to create a vector of numbers that tracks how big the row was for that number ... for example, from 5 there are 6 steps to 1, so if I ever reach the number 5 in a series, I know that I have 6 steps and I don’t need to calculate these steps. With this idea, I encoded 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 special program stops at 113382. Can someone explain to me how I will understand why it hangs on this number?

Is there a way to change my algorithm to be better? I understand that I am creating duplicates using the current way that I do it: for example, a series of 3 is 3,10,5,16,8,4,2,1. Therefore, I already figured out the sizes for 10,5,16,8,4,2,1, but I will duplicate these solutions later.

Thanks for your help!

Answer 1

Have you excluded integer overflow? Can you guarantee that the result (3*j+1)/2 will always match int ?

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

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

Answer 2

I think you greatly exaggerate things. Why do you even use vectors for this?

Your problem, I think, is crowded. Use unsigned int everywhere.

Here is the working code, which is much simpler and works (it does not 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 3

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

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

Answer 4

The problem is overflow. Just because a sequence starts below 1 million does not mean that it cannot exceed 1 million later. In this particular case, it overflows and goes negatively, as a result, your code goes into an infinite loop. I changed my code to use "long long" and this makes it work.

But how did I know that? I compiled your code and then ran it in the debugger. I paused the program while it was in a loop and checked the variables. There I discovered that j was negative. That pretty much told me everything I needed to know. Of course, I added cout << j; as well as assert(j > 0) and confirmed that j is full.

Answer 5

I would try to use a large array, not a vector, then you can avoid the duplicates that you mentioned, because for every number you calculate, you can check if it is in the array, and if not, add it. This is probably actually more. In addition, you can try using unsigned long, since at first glance it is not clear how large these numbers are.

Answer 6

I saved the chain length for each number in the array .. and during brute force, whenever I got a number less than estimated, I just added the chain length for this lower number and broke out of the loop.
For example, I already know that the Collatz sequence for 10 has a length of 7 lengths. now when i rate 13 i get 40, then 20, then 10 .. which i have already rated. therefore, the total score is 3 + 7.
the result on my car (up to 1 million) was 0.2 seconds. with a sheer brute force of 5 seconds.