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;
}