Wu Yudong's Blog

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则可能不太为人所知，尽管从169开始不断地取各位数字的阶乘之和构成了最长的循环回到169；事实上，只存在三个这样的循环：

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

不难证明，从任意数字出发最终都会陷入循环。例如，

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

从69开始可以得到一个拥有五个不重复项的链，但是从一个小于一百万的数出发能够得到的最长的无重复项链包含有60项。

从小于一百万的数出发，有多少条链恰好包含有60个不重复项？

//（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;
}

Answer:402

Completed on Tue, 18 Feb 2014, 12:21