1 files changed, 57 insertions, 0 deletions
diff --git a/euler74.c b/euler74.c
new file mode 100644
index 0000000..a0020f6
--- /dev/null
+++ b/euler74.c
@@ -0,0 +1,57 @@
+#include <stdio.h>
+#include <string.h>
+
+#define MAXTERM 3000000
+int next[MAXTERM];
+
+const int factorial[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
+
+int sum_fact_digits(int n)
+{
+	int sum = 0;
+	while (n > 0) {
+		sum += factorial[n%10];
+		n /= 10;
+	}
+	return sum;
+}
+
+void init()
+{
+	memset(next, 0, sizeof(next));
+	for (int i = 1; i < 1000000; i++) {
+		if (next[i])
+			continue;
+		next[i] = sum_fact_digits(i);
+		for (int j = next[i]; next[j] == 0; j = next[j]) {
+			next[j] = sum_fact_digits(j);
+		}
+	}
+}
+
+int chainlen(int n)
+{
+	int chain[100], L = 0;
+
+	while (1) {
+		for (int i = 0; i < L; i++) {
+			if (chain[i] == n)
+				return L;
+		}
+		chain[L] = n;
+		L++;
+		n = next[n];
+	}
+}
+
+int main()
+{
+	int count = 0;
+
+	init();
+	for (int i = 1; i <= 1000000; i++) {
+		if (chainlen(i) == 60)
+			count++;
+	}
+	printf("%d\n", count);
+}