scosant
12/17/2012 - 11:24 AM

## projecteuler014 - longest collatz sequence

projecteuler014 - longest collatz sequence

``````/* Scott Santarromana
* projecteuler014 - longest collatz sequence
*
* 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?
*/

#include <iostream>

const unsigned int ONE_MILLION = 1000000;

int main(int argc, char *argv[])
{
unsigned int max_n = 13;
unsigned int max_length = 10;;
for (unsigned int x = 13; x < ONE_MILLION; x++) {
unsigned int n = x;
unsigned int n_length = 0;
while (n != 1) {
if (n % 2 == 0) {
n /= 2;
} else {
n = 3*n + 1;
}
n_length++;
}
std::cout << x << " has chain length " << n_length << std::endl;
if (n_length > max_length) {
max_length = n_length;
max_n = x;
}
}

std::cout << max_n << " has max chain length " << max_length;
return 0;
}
``````