题目34：找出所有等于各位数阶乘之和的数字之和

欧拉计划

Digit factorials

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

题目：

145 是一个奇怪的数字, 因为 1! + 4! + 5! = 1 + 24 + 120 = 145.

找出所有等于各位数字阶乘之和的数字之和。

注意: 因为 1! = 1 和 2! = 2 不是和的形式，所以它们不算在内。

迷雾少年

用大数算了  100!很长的数

愤怒的大头菇

1. #当8个9组成的8位数，各位阶乘的和是一个7位数，所以不可能相等.范围确定在10000000
   
2. list1 = []
   
3. for i in range(10,10000000):
   
4.       temp = i
   
5.       total = 0
   
6.       while temp:
   
7.             tmp = 1
   
8.             for j in range(1,temp%10+1):
   
9.                   tmp *= j
   
10.             total +=tmp
    
11.             temp = temp//10
    
12.             
    
13.       if total == i:
    
14.             list1.append(i)
    
15. 
    
16. print(sum(list1))

复制代码

结果是:40730

芒果加黄桃

1. # encoding:utf-8
   
2. # 1! + 4! + 5! = 145 找类似组合
   
3. from time import time
   
4. from math import factorial
   
5. from itertools import permutations
   
6. def euler034():
   
7.     l_facs = [factorial(x) for x in range(0, 10)]
   
8.     print(l_facs)
   
9.     for f in range(2, 7):
   
10.         l_temp = [k for (k, v) in enumerate(l_facs) if v < 10 ** f]
    
11.         for each in permutations(l_temp, f):
    
12.             n_t = ''
    
13.             nums = 0
    
14.             for t in each:
    
15.                 n_t += str(t)
    
16.                 nums += l_facs[t]
    
17.             if nums == int(n_t):
    
18.                 print(nums)
    
19. def euler034_1():
    
20.     l_facs = [factorial(x) for x in range(0, 10)]
    
21.     print(l_facs)
    
22.     for i in range(11, l_facs[9] * 7):
    
23.         tmp = list(str(i))
    
24.         sums = sum([l_facs[int(k)] for k in tmp])
    
25.         if i == sums:
    
26.             print(i)
    
27. if __name__ == '__main__':
    
28.     start = time()
    
29.     euler034()
    
30.     print('cost %.6f sec' % (time() - start))
    
31.     start = time()
    
32.     euler034_1()
    
33.     print('cost %.6f sec' % (time() - start))

复制代码

一种用排列，不含重复数字的；一种暴力求解，可以喊重复数字。结果如下：
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
145
cost 0.481362 sec
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
145
40585
cost 8.705163 sec

渡风

%% Problem34.m
% 最后编辑时间：17-06-05 0:18
% 问题：找到所有满足一下条件的数，这个数的值等于各个位数阶乘的和，再求和
% 分析：这些书一定在100w之内
% Problem34所用时间为7.2159秒
% Problem34的答案为40730

1. function Output = Problem34()
   
2. tic
   
3. n = 1000000;
   
4. Value = ones(1,n)*(-1);
   
5. Value(1:9) = factorial([1 2 3 4 5 6 7 8 9]);
   
6. for ii = 1:n
   
7.     if Value(ii) == -1
   
8.         %disp(ii)
   
9.         Perms = str2num(perms(num2str(ii)));  %用于矢量
   
10.         value = sum( factorial(num2str(ii) - '0'));
    
11.         L = length(Perms);
    
12.         for jj = 1:L
    
13.             if Value(Perms(jj)) == -1
    
14.                 Value(Perms(jj)) = value;
    
15.             end
    
16.         end
    
17.     end
    
18. end
    
19. 
    
20. %Set = find(Value == Value);
    
21. All = Value == 1:n;
    
22. for ii = 1:n
    
23.      if All(ii) == 1
    
24.          disp(ii)
    
25.      end
    
26. end
    
27. Output = sum(Value(All)) - 3; %去掉 1！ = 1 和 2！ = 2
    
28. toc
    
29. disp('此代码使用matlab编程')
    
30. disp(['Problem34所用时间为',num2str(toc),'秒'])
    
31. disp(['Problem34的答案为',num2str(Output)])
    
32. end
    

复制代码

Trami

结果40730
运行时间：11.8960258961
import time

start = time.time()

def fac(x):
    if x == 0:
        return 1
    else:
        return x * fac(x-1)

c = []
result = []
temp = 0
for i in range(10, 1000000):
    for item in str(i):
        c.append(item)
    # print(c)
    for j in range(0, len(c)):
        temp += fac(int(c[j]))
    # print(temp)
    if temp == i:
        result.append(i)
    # print(c)
    for k in range(0, len(c)):
        c.pop()
    temp = 0
print(sum(result))

end = time.time()
print(end - start)

王小召

结果是:[145, 40585]
用时：3.04秒

1. import functools
   
2. import math
   
3. import time
   
4. 
   
5. 
   
6. def get_result(value):
   
7.     result = []
   
8.     # 一个n 位数的值最大的阶乘和为a_max = x*9!,而一个n位数的最大值为10的n-1次方:b_max = 10**n，所以增长速度存在差异,
   
9.     # 在b首次大于a时 ，a再也追不上了；
   
10.     while 10**value/value < math.factorial(9):
    
11.         for num in range(10**(value-1), 10**value):
    
12.             res = functools.reduce(lambda x, y: x+y, [math.factorial(int(i)) for i in str(num)])
    
13.             if res == num:
    
14.                 result.append(num)
    
15.         value += 1
    
16.     return result
    
17. print("结果是:{}\n用时：{:.2f}秒".format(get_result(2), time.process_time()))

复制代码

永恒的蓝色梦想

C++ 854ms

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. 
   
5. int main() {
   
6.     const static unsigned int map[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
   
7.     unsigned int sum = 0, temp, i, j;
   
8. 
   
9.     for (i = 10; i < 10000000; i++) {
   
10.         temp = 0;
    
11.         j = i;
    
12. 
    
13.         while (j) {
    
14.             temp += map[j % 10];
    
15.             j /= 10;
    
16.         }
    
17. 
    
18.         if (temp == i) {
    
19.             sum += i;
    
20.         }
    
21.     }
    
22. 
    
23.     cout << sum << endl;
    
24.     return 0;
    
25. }

复制代码

debuggerzh

40730

Process returned 0 (0x0)   execution time : 0.393 s
Press any key to continue.
先确定上界，位数为7时，各位阶乘和的最大值为9！* 7 = 2540160 < 1e7，因此上界为1e7(因为指数函数增长更快）

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. const int M = 1e7;
   
5. const int factorial[] = {1,1,2,6,24,120,720,5040,40320,362880};
   
6. 
   
7. int judge(int x){
   
8.   int x0 = x;
   
9.   int sum = 0;
   
10.   while(x){
    
11.     int current_digit = x % 10;
    
12.     sum += factorial[current_digit];
    
13.     x /= 10;
    
14.   }
    
15.   return x0 == sum ? x0 : 0;
    
16. }
    
17. 
    
18. int main(){
    
19.   int ans = 0;
    
20. 
    
21.   for (int i = 3;i < M;i++){
    
22.     ans += judge(i);
    
23.   }
    
24. 
    
25.   cout << ans << endl;
    
26.   return 0;
    
27. }
    

复制代码

a1351468657

1. #include <stdio.h>
   
2. 
   
3. int fact(int);
   
4. int fact(int n)
   
5. {
   
6.         if (n == 0)
   
7.         {
   
8.                 return 1;
   
9.         }
   
10.         else
    
11.         {
    
12.                 return n * fact(n - 1);
    
13.         }
    
14. }
    
15. 
    
16. main()
    
17. {
    
18.         int i, j, a, sum = 0, count;
    
19.        
    
20.        
    
21. 
    
22.         for (i = 10; i < 1000000; i++)
    
23.         {
    
24.                 count = 0;
    
25.                 j = i;
    
26.                 while (j)
    
27.                 {
    
28.                         a = j % 10;
    
29.                         count += fact(a);
    
30.                         j /= 10;
    
31.                 }
    
32.                 if (i == count)
    
33.                 {
    
34.                         sum += count;
    
35.                         printf("%d ", count);
    
36.                 }
    
37.         }
    
38.         printf("\n%d\n", sum);
    
39. }

复制代码

用了递归的方式求阶乘

guosl

当数字是8位数时，其各位数字的阶乘之和最大为：2903040；它小于这个数本身。所以只需在范围1到10000000之间查找即可。

1. /*
   
2. 答案：40730
   
3. 耗时：0.055327秒（单核）
   
4.       0.009392秒（六核）
   
5. */
   
6. #include <cstdio>
   
7. #include <cstring>
   
8. #include <omp.h>
   
9. using namespace std;
   
10. 
    
11. const int b[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
    
12. 
    
13. int main(void)
    
14. {
    
15.   int nSum = 0;
    
16. #pragma omp parallel for reduction(+:nSum)
    
17.   for (int n = 10; n < 10000000; ++n)
    
18.   {
    
19.     int nS = 0;
    
20.     int k = n;
    
21.     while (k > 0)
    
22.     {
    
23.       nS += b[k % 10];
    
24.       k /= 10;
    
25.     }
    
26.     if (nS == n)
    
27.       nSum += nS;
    
28.   }
    
29.   printf_s("%d\n", nSum);
    
30.   return 0;
    
31. }
    

复制代码

TLM

[145, 40585]
40730
Time:0.17680621147155762s

1. """
   
2. k<=8
   
3. 将数字分成前4位后5位的结构，计算后五位结果并记录误差（输出误差为零的数据）
   
4. 计算前四位误差，在前面五位结果中【查询】误差的相反数（误差和为零，即为相等）
   
5. 此方法复杂度为O(sqrt(n)),n=10**9
   
6. 实际上应该是n取10**8，后面想明白了，但是屎山已成
   
7. """
   
8. # import random
   
9. import time
   
10. st=time.time()
    
11. a=[]
    
12. ans=0
    
13. jiecheng=[]
    
14. num=1
    
15. jiecheng.append(num)
    
16. # 获取前100000项的数据与误差数
    
17. num2err=dict()
    
18. num2err[0]=jiecheng[0]+4
    
19. err2num=dict()
    
20. err2num[num2err[0]]=[0]
    
21. for i in range(1,10):
    
22.     num=num*i
    
23.     jiecheng.append(num)
    
24.     num2err[i]=jiecheng[i]-i+4
    
25. ii=1
    
26. for i in range(1,5):
    
27.     ii=ii*10
    
28.     for j in range(1,10):
    
29.         for k in range(ii):
    
30.             num2err[j*ii+k]=num2err[k]+jiecheng[j]-j*ii-1
    
31.             if num2err[j*ii+k] in err2num:
    
32.                 err2num[num2err[j*ii+k]].append(j*ii+k)
    
33.             else:
    
34.                 err2num[num2err[j*ii+k]]=[j*ii+k]
    
35.             if num2err[j*ii+k]+i==4:
    
36.                 a.append(j*ii+k)
    
37.                 ans=ans+(j*ii+k)
    
38. # data0=dict()
    
39. ii=1
    
40. jj=10**4
    
41. for i in range(4):
    
42.     ii=ii*10
    
43.     for j in range(1,10):
    
44.         for k in range(ii):
    
45.             err=-(num2err[k]-5+i+k+jiecheng[j]-(j*ii+k)*jj)
    
46.             if err in err2num:
    
47.                 for data in err2num[err]:
    
48.                     if data>=jj:
    
49.                         break
    
50.                     a.append((j*ii+k)*jj+data)
    
51.                     ans=ans+((j*ii+k)*jj+data)
    
52.             # data0[j*ii+k]=-err
    
53. print(a)
    
54. print(ans)
    
55. print('Time:{}s'.format(time.time()-st))
    
56. # u=random.randint(1,10000-1)
    
57. # w=random.randint(1,1000-1)
    
58. # print((u,w))
    
59. # print(data0[w]+num2err[u])
    
60. # uu=(w)*jj+u
    
61. # v=0
    
62. # while uu>0:
    
63. #     v=v+jiecheng[uu%10]
    
64. #     uu=uu//10
    
65. # print(v-((w)*jj+u))

复制代码

mathtimes

1. fn bits_factorial(x: u128) -> u128 {
   
2.     let mut x = x;
   
3.     let mut sum = 0;
   
4.     while x != 0 {
   
5.         sum += (1..=(x%10)).product::<u128>();
   
6.         x /= 10;
   
7.     }
   
8.     sum
   
9. }
   
10. 
    
11. fn main () {
    
12.     let mut sum = 0;
    
13.     for i in 1..99999999 {
    
14.         if i == bits_factorial(i) {
    
15.             sum += i;
    
16.         }
    
17.     }
    
18.     println!("{}", sum - 3);
    
19. }

复制代码