#include <iostream>
#include <cmath>
#include <chrono>

using namespace std;
int factorials[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int cycleLength[2200000];

inline int digitFactorial(int a)
{
    int sum = 0;
    while (a > 0)
    {
        sum += factorials[a % 10];
        a /= 10;
    }
    return sum;
}

int cycle(int n, int depth)
{
    if (depth > 1000)
        cout << "{ \"depth\": " << depth << ", \"n\": " << n << " }" << endl;
    int cl = cycleLength[n];
    if (cl < 0)
        return -cl;
    if (cl == 0)
    {
        cl = cycle(digitFactorial(n), depth+1);
        cycleLength[n] = cl;
    }
    return cl+1;
}

int main()
{
    auto start = chrono::system_clock::now();

    cycleLength[0] = -1;
    cycleLength[1] = -1;
    cycleLength[2] = -1;
    cycleLength[169] = -3;
    cycleLength[145] = -1;
    cycleLength[871] = -2;
    cycleLength[872] = -2;
    cycleLength[1454] = -3;
    cycleLength[40585] = -3;
    cycleLength[45361] = -2;
    cycleLength[45362] = -2;
    cycleLength[363601] = -3;

    cout << "cycle length 69: " << cycle(69,0) << endl;

    int sixties = 0;
    for (int n = 0; n < 1000000; n++)
    {
        if (cycle(n,0) == 60)
            sixties++;
    }

    auto end = std::chrono::system_clock::now();

    std::chrono::duration<double> elapsed_seconds = end - start;
    cout << "cycles took: " << elapsed_seconds.count() << endl;

    cout << "numbers with 60 cycles: " << sixties;
    return 0;
}