EulerProblem14.cpp

#include <iostream>
#include <cstdint>

using namespace std;


//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.


namespace {

	enum class NumParity {
		EVEN,
		ODD
	};

	NumParity getNumParity(uint64_t n)
	{
		return (n % 2 == 0)
			? NumParity::EVEN
			: NumParity::ODD;
	}

	uint64_t getNextNum(uint64_t n)
	{
		uint64_t nextNum = 0;

		switch(getNumParity(n)) {
			case NumParity::EVEN:
				nextNum = n / 2;
				break;
			case NumParity::ODD:
				nextNum = (3 * n) + 1;
				break;
		}

		return nextNum;
	}

	int countSteps(int startNum)
	{
		uint64_t n = startNum;
		int numSteps = 1;

		while(n != 1) {
			n = getNextNum(n);
			++numSteps;
		}

		return numSteps;
	}

}


void Problem14::run()
{
	int maxSteps = 0;
	int maxNum = 1;

	for(int n = 1; n < 1000000; ++n) {
		auto numSteps = countSteps(n);
		if(numSteps > maxSteps) {
			maxSteps = numSteps;
			maxNum = n;
		}
	}
		
	cout << "Value of n for longest chain: " << maxNum << endl;
}