题目74：包含60个不重复项的阶乘链有多少个？

欧拉计划

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 不像 145 那么有名，但是 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 开始可以产生一条有 5 个不重复元素的链，但是以一百万以下的数开始，能够产生的最长的不重复链包含 60 个项。

一共有多少条以一百万以下的数开始的链包含 60 个不重复项？

jerryxjr1220

进度：5 %  用时：9.589秒 >>>进度：10 %  用时：19.738秒 >>>进度：15 %  用时：29.751秒 >>>进度：20 %  用时：40.014秒 >>>进度：25 %  用时：50.148秒 >>>进度：30 %  用时：60.717秒 >>>进度：35 %  用时：70.462秒 >>>进度：40 %  用时：80.854秒 >>>进度：45 %  用时：90.833秒 >>>进度：50 %  用时：101.681秒 >>>进度：55 %  用时：111.471秒 >>>进度：60 %  用时：122.204秒 >>>进度：65 %  用时：133.301秒 >>>进度：70 %  用时：144.257秒 >>>进度：75 %  用时：154.717秒 >>>进度：80 %  用时：165.559秒 >>>进度：85 %  用时：176.494秒 >>>进度：90 %  用时：187.150秒 >>>进度：95 %  用时：198.313秒 >>>进度：100 %  用时：209.492秒 >>>答案： 402 总共用时：209.820秒

算法时间蛮长的，应该可以优化的。

1. from math import factorial as fct
   
2. def chain(n):
   
3.     chains = [n]
   
4.     count, calc = 1, 0
   
5.     for i in str(n):
   
6.         calc += fct(int(i))
   
7.     while calc not in chains:
   
8.         chains.append(calc)
   
9.         count += 1
   
10.         n1 = calc
    
11.         calc = 0
    
12.         for i in str(n1):
    
13.             calc += fct(int(i))
    
14.     return count
    
15. 
    
16. chainlist = []
    
17. for i in range(1,1000001):
    
18.     if i % 50000 == 0:
    
19.         middle = clock()
    
20.         print ('进度：%d' % int(i/10000), '%',' 用时：%.3f秒 >>>' % (middle-start), end ='')
    
21.     if chain(i) == 60:
    
22.         chainlist.append(i)
    
23. end = clock()
    
24. print ('答案： %d' % len(chainlist), '总共用时：%.3f秒' % (end-start))

复制代码

逗逼小龙

新手学习  很多地方很幼稚
答案  402

1. # -*- coding: utf-8 -*-
   
2. import math
   
3. import time
   
4. start=time.clock()
   
5. list2=[]
   
6. list3=[]
   
7. list4=[]
   
8. def fen_2(m):
   
9.     list1=[]
   
10.     list2.append(m)
    
11.     for n in str(m) :
    
12.         n=int(n)
    
13.         list1.append(math.factorial(n))
    
14.     if len(list2)!=len(set(list2)):
    
15.         list2.pop()
    
16.         return len(list2)
    
17.     return  fen_2(sum(list1))
    
18. def fen(x):
    
19.     global list2
    
20.     list2 =[]
    
21.     return(fen_2(x))
    
22. for i in range(1,1000000):
    
23.     if fen(i)>=60:
    
24.         list3.append(i)
    
25. print(len(list3) )
    
26. for i in list3:
    
27.     fen(i)
    
28.     list4.extend(list(set(list2)&set(list3 )))
    
29. print(list4 == list3)
    
30. end=time.clock()
    
31. print('运行耗时:%f'%(end-start ))

复制代码

芒果加黄桃

1. # encoding:utf-8
   
2. # 寻找100万以下60项的阶乘链  145 = 1！+2！+3！
   
3. from time import time
   
4. from math import factorial
   
5. 
   
6. def getFac(n):
   
7.     result = 0
   
8.     while n >= 10:
   
9.         result += factorial(n % 10)
   
10.         n = n // 10
    
11.     return result + factorial(n)
    
12. 
    
13. def euler072(N=100):
    
14.     d_facs = {}
    
15.     s_facs = set()
    
16.     count = 0
    
17.     for n in range(1, 1000001):
    
18.         if str(sorted(str(n))) in s_facs:
    
19.             count+=1
    
20.         else:
    
21.             l_tmp = [n]
    
22.             tmp,k = 0,n
    
23.             while True:
    
24.                 tmp = getFac(k);
    
25.                 if tmp not in l_tmp:
    
26.                     l_tmp.append(tmp)
    
27.                     k = tmp
    
28.                 else:
    
29.                     break
    
30.             if len(l_tmp)>=60:
    
31.                 count+=1
    
32.                 d_facs[str(sorted(str(n)))] = l_tmp
    
33.     print(count)   
    
34.    
    
35. if __name__ == '__main__':
    
36.     start = time()
    
37.     euler072()
    
38.     print('cost %.6f sec' % (time() - start))
    

复制代码

402
cost 62.502249 sec

najin

用了新解法：
程序是matlab
结果是
   402

时间已过 0.771700 秒。
>>

wyp02033

1. from time import perf_counter
   
2. 
   
3. 
   
4. def factorial(n):
   
5.     if n == 0 or n == 1:
   
6.         return 1
   
7.     else:
   
8.         return n * factorial(n-1)
   
9. 
   
10. def generate_unrepetition_link(n):
    
11.     unrepetition_link = [n]
    
12.     num_str = str(n)
    
13.     while True:
    
14.         sum_ = 0
    
15.         for each in num_str:
    
16.             sum_ += factorial(int(each))
    
17.         if sum_ not in unrepetition_link:
    
18.             unrepetition_link.append(sum_)
    
19.             num_str = str(sum_)
    
20.         else:
    
21.             break
    
22.     return unrepetition_link
    
23. def main():
    
24.     n = 0
    
25.     for i in range(5, 1000000):
    
26.         if len(generate_unrepetition_link(i)) == 60:
    
27.             n += 1
    
28.     print(n)
    
29. 
    
30. 
    
31. if __name__ == '__main__':
    
32.     start = perf_counter()
    
33.     main()
    
34.     end = perf_counter()
    
35.     print("time uesd:", end - start)

复制代码

结果：
402
time uesd: 103.1872067770146s

永恒的蓝色梦想

记录下思路,以后再写
0.出现过的不重复计算

debuggerzh

402

Process returned 0 (0x0)   execution time : 0.219 s
Press any key to continue.
动态规划+记忆化搜索
设f(x)为x各位数阶乘之和
设集合

                               
登录/注册后可看大图

设len(x)为以x开始的链的不重复项数，则状态转移方程

                               
登录/注册后可看大图

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. 
   
5. const int f[] = {1,1,2,6,24,120,720,5040,40320,362880};
   
6. 
   
7. const int len3[] = {169,1454,363601};
   
8. const int len2[] = {871,872,45361,45362};
   
9. const int len1[] = {0,1,2,145,40585};
   
10. 
    
11. const int M = 1e6;
    
12. int dp[M*10] = {0};
    
13. int mx = 0;
    
14. 
    
15. int f_sum(int x){
    
16.   int res = 0;
    
17.   if (x == 0) return 1;
    
18.   while(x){
    
19.     res += f[x % 10];
    
20.     x /= 10;
    
21.   }
    
22.   return res;
    
23. }
    
24. 
    
25. int len(int x){
    
26.   //mx = max(mx,x);
    
27.   int & ans = dp[x];
    
28.   if (ans)  return ans;
    
29. 
    
30.   if (find(len3,len3 +3,x) != len3 +3)  return ans = 3;
    
31.   if (find(len2,len2 +4,x) != len2 +4)  return ans = 2;
    
32.   if (find(len1,len1 +5,x) != len1 +5)  return ans = 1;
    
33. 
    
34.   return ans = len(f_sum(x)) + 1;
    
35. }
    
36. 
    
37. int main(){
    
38.   int cnt = 0;
    
39.   for (int i = 0;i <= M;i++)
    
40.     if (len(i) == 60) ++cnt;
    
41. 
    
42.   //cout << mx << endl;
    
43.   cout << cnt << endl;
    
44.   return 0;
    
45. }
    

复制代码

guosl

1. /*
   
2. 答案：402
   
3. 耗时：4.07265秒（单核）
   
4.       0.658726秒（六核）
   
5. */
   
6. #include <iostream>
   
7. #include <unordered_set>
   
8. #include <omp.h>
   
9. using namespace std;
   
10. 
    
11. const int f[] = { 1,1,2,6,24,120,720,5040,40320,362880 };
    
12. 
    
13. int GetFS(int n)
    
14. {
    
15.   int nS = 0;
    
16.   while (n > 0)
    
17.   {
    
18.     nS += f[n % 10];
    
19.     n /= 10;
    
20.   }
    
21.   return nS;
    
22. }
    
23. 
    
24. int main(void)
    
25. {
    
26.   double t = omp_get_wtime();
    
27.   int nCount = 0;
    
28.   unordered_set<long long> us;
    
29. #pragma omp parallel for private(us) reduction(+:nCount)
    
30.   for (int i = 1; i <= 1000000; ++i)
    
31.   {
    
32.     us.clear();
    
33.     int k = i;
    
34.     while (true)
    
35.     {
    
36.       auto itr = us.find(k);
    
37.       if (itr != us.end())
    
38.         break;
    
39.       us.insert(k);
    
40.       k = GetFS(k);
    
41.     }
    
42.     if (us.size() >= 60)
    
43.       ++nCount;
    
44.   }
    
45.   t = omp_get_wtime() - t;
    
46.   cout << nCount << endl << t << endl;
    
47.   return 0;
    
48. }

复制代码

TLM

储存计算过的数值，阶乘也提前算好
402
Time:1.909942865371704s

1. import time
   
2. st=time.time()
   
3. n=1000000
   
4. # 获取阶乘数列
   
5. jiecheng=[1]
   
6. for i in range(1,10):
   
7.     jiecheng.append(jiecheng[-1]*i)
   
8. # 创建dict()
   
9. data=dict()
   
10. def getl(n):
    
11.     if n in data:
    
12.         return data[n]
    
13.     data2=dict()
    
14.     nn=n
    
15.     u=0
    
16.     while nn not in data2:
    
17.         num=0
    
18.         ii=nn
    
19.         while ii>0:
    
20.             num=jiecheng[ii%10]+num
    
21.             ii=ii//10
    
22.         data2[nn]=len(data2)+1
    
23.         nn=num
    
24.         if nn in data:
    
25.             u=data[nn]-1
    
26.             data2[nn]=len(data2)+1
    
27.             break
    
28.     for j in data2:
    
29.         if data2[j]>=data2[nn]:
    
30.             data[j]=len(data2)+1-data2[nn]+u
    
31.         else:
    
32.             data[j]=len(data2)+1-data2[j]+u
    
33.     return data[n]
    
34. numsum=0
    
35. for i in range(69,n+1):
    
36.     # print(getl(i))
    
37.     if getl(i)>=60:
    
38.         numsum=numsum+1
    
39. print(numsum)
    
40. # print(data)
    
41. print('Time:{}s'.format(time.time()-st))

复制代码