/* http://projecteuler.net/
 *
 * 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.
 *
 *
 * Solution by Melkor (Filip Niksic, fniksic@gmail.com)
 *
 **/

#include <iostream>
#include <vector>

using namespace std;

unsigned int const maxn = 1000000u;

int main() {
    vector<unsigned int> lengths(maxn+1, 1);
    unsigned int maxlength(0), maxi(0), n;

    for (unsigned int i = 1; i <= maxn; ++i) {
	n = i;

	while (n > 1) {
	    if (n % 2 == 0)
		n /= 2;
	    else
		n = 3*n+1;
	    if (n <= maxn && lengths[n] != 1) {
		lengths[i] += lengths[n];
		break;
	    }
	    ++lengths[i];
	}

	if (lengths[i] > maxlength) {
	    maxlength = lengths[i];
	    maxi = i;
	}
    }

    cout << maxi << " produces the longest chain." << endl;

    return 0;
}