14 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?

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

#include <iostream>
#include <limits>
#include <vector>
#include <utility>

using namespace std;

void pause() { cin.ignore(numeric_limits<streamsize>::max(), '\n'); }

bool isEven(long long int n)
{
    if (n % 2 == 0) return true;
    else return false;
}

long long int ifEven(long long int n)
{
    return n / 2;
}
long long int ifOdd(long long int n)
{
    return (3 * n + 1);
}

long long int findMaxChain(vector <pair <long long int, long long int>> chain)
{    
    long long int max1 = chain.at(0).first;
    long long int max2 = chain.at(0).second;
    for (long long int i = 1; i < chain.size(); i++)
    {
        if (chain.at(i).first > max1)
        {
            max1 = chain.at(i).first;
            max2 = chain.at(i).second;
        }
    }
    return max2 - 1;
}

int main()
{
    long long int sequence = 1;
    long long int endingNumber = 1000000;
    long long int counterChain = 1;
    long long int helper = 0;
    pair <long long int, long long int> counterChain_sequence;
    vector <pair <long long int, long long int>> counters; // format: (1 - 999999) by index - to - counterChains


    for (long long int i = 0; i < endingNumber; i++)
    {
        while (true)
        {
            if (sequence == 1)
            {
                helper++;
                sequence = sequence + helper;
                counterChain_sequence = make_pair(counterChain, sequence);
                counters.push_back(counterChain_sequence);
                counterChain = 1;
                break;
            }
            if (isEven(sequence))
            {
                sequence = ifEven(sequence);
                counterChain++;
            }

            else
            {
                sequence = ifOdd(sequence);
                counterChain++;
            }
        }
    }

    cout << "Max Number Chain = " << findMaxChain(counters);
    pause();
}

Solution: 837799

Last updated