Grind Report 14

Problem 14

The following iterative sequence is defined for the set of positive integers:

n -> n/2 (n is even)
n -> 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

*WARNING: This contains the solution!*

As you can guess this could be a lot of calculations. But all of the numbers eventually cross at some point (4 -> 2 -> 1). So my first thought was to use memoization but before I did this I implemented a fairly straightforward method (for the most part brute force). I got this to work almost immediately so I decided to attempt the memoization.

Along side the memoization, I used a recursive method. Basically I had a map that stored the number as a key and the value was the number of terms in the chain the key would produce. Overall I think this was a good direction to come from; however, there was two things I did not take into consideration.

One thing is that the overhead for each function call in the recursion added up thus slowing the program. The other problem is that mapping each value to a key took a toll on the speed as well. I ended up scrapping this attempt because the brute force method was pretty fast (1.5~ seconds to solve this problem). In retrospec, I think I could have fixed up this memoization method and gotten it to be faster than 1.5~ seconds.

First, if I inlined the function *I think* that would take out some? most? of the overhead for calling the function. The other thing I could have done is been smarter with mapping the numbers. Such as only mapping the more common numbers; however, I am not sure how to distinguish the common numbers from the other numbers. Even numbers would be a guess of mine, but that is something I'd have to consider more for a good answer.

So I reverted back to my first attempt. Two things I used to make this attempt more effecient were: only consider odd numbers, only consider numbers 500,000-999,999. The reason for the first one is somewhat obvious. Odd numbers make it become larger; even numbers make it become smaller. The reason for the second one is because all numbers 1-499,999 can be multiplied by 2 and be found within the range I was considering - therefore adding an extra number to the chain. :)

Here is my brute force method.

#include <string>
#include <iostream>

using std::string;
using std::cout;

const int MAX = 999999;

int main()
{
int answer = 0;
int highestCount = 0;
for (int i = (MAX + 1) / 2; i < MAX; i += 2)
{
 long long number = i;
 int count = 1;
 while (number != 1)
 {
  if (number % 2 == 0)
   number /= 2;
  else
   number = number * 3 + 1;
  ++count;
 }
 if (count > highestCount)
 {
  highestCount = count;
  answer = i;
 }
}
cout << "Highest Number is " << highestNumber << std::endl;
cout << answer << " with count of " << highestCount << std::endl;
}

*saved game*