69 lines
1.5 KiB
C++
69 lines
1.5 KiB
C++
#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;
|
|
}
|