# 工学1号馆

home

## Project Euler 74–Digit factorial chains

Wu Yudong    August 20, 2018     欧拉计划   679

Digit factorial chains

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

1! + 4! + 5! = 1 + 24 + 120 = 145

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

145之所以广为人知，是因为它的各位数字的阶乘之和恰好等于本身：

1! + 4! + 5! = 1 + 24 + 120 = 145

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

//（Problem 74）Digit factorial chains
// Completed on Tue, 18 Feb 2014, 04:21
// Language: C11
//
// 版权所有（C）wu yudong
// 博客地址：http://www.wuyudong.com

#include<stdio.h>
#include<math.h>
#include<stdbool.h>

#define N 1000000
long long fac[10];  //保存1~ 9阶乘的数组

long long factorial(int n)  //计算阶乘函数
{
if(n == 1 || n == 0) return 1;
else return n * factorial(n - 1);
}

void init()  //初始化数组
{
int i;
for(i = 0; i <= 9; i++) {
fac[i] = factorial(i);
}
}

long long sum(long long n)   //计算整数n各位的阶乘的和
{
int ans = 0;
while(n) {
ans += fac[n % 10];
n /= 10;
}
return ans;
}

bool fun(int n)
{
int i, count, t;
bool flag = false;
count = 0;
while(1) {
switch(n) {
case 1: count += 1; flag = true; break;
case 2: count += 1; flag = true; break;
case 169: count += 3; flag = true; break;
case 1454: count += 3; flag = true; break;
case 871: count += 2; flag = true; break;
case 872: count += 2; flag = true; break;
case 145: count += 1; flag = true; break;
default: t = sum(n);
if( n == t) {
flag = true;
break;
} else{
n = t;
count++; break;
}
}
if(flag) break;
}
if(count == 60) return true;
else return false;
}

void solve()
{
int i, count;
count = 0;
for(i = 2; i <= N; i++) {
if(fun(i)) count++;
}
printf("%d\n", count);
}

int main()
{
init();
solve();
return 0;
}

Completed on Tue, 18 Feb 2014, 12:21