小练习： 20160828 找出所有等于各位数阶乘之和的数字之和

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

                               
登录/注册后可看大图

好了言归正传，我们开始做小练习。




题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
题目比较简单，注重程序效率和创意。
答题在一周内完成，即9.5 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。

----除列出程序外，请给出输出的结果。----


题目：

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

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

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

mather

1. dics = {}
   
2. for x in range(10):
   
3.     if x==0:
   
4.         dics[0]=1
   
5.     else:
   
6.         dics[x] = dics[x-1]*x
   
7. 
   
8. res = 0
   
9. for i in range(11,10**7):
   
10.     sums = 0
    
11.     tem = i
    
12.     while tem>0:
    
13.         sums = sums + dics[tem%10]
    
14.         tem = tem//10
    
15.         if sums>i:
    
16.             break
    
17.     if sums==i:
    
18.         res = res+i
    
19. print(res)

复制代码

先占楼，计算速度略慢
结果：40730

冬雪雪冬

先考虑上限是多少：
即使每位都是9，如果是8为则9!*8=2903040，只有7位。所以不可能是8位。
如果是7位则9!*7=2540160，因最前一位只能最大是2，所以只能到达9！*6+2，即2177282

1. import math
   
2. list1 = [math.factorial(i) for i in range(0, 10)]
   
3. sum2 = 0
   
4. for i in range(10, 2177283):
   
5.     j = i
   
6.     sum1 = 0
   
7.     while j > 0:
   
8.         sum1 += list1[j % 10]
   
9.         j //= 10
   
10.     if sum1 == i:
    
11.         sum2 += sum1
    
12. print(sum2)
    

复制代码

结果是40730

wangzhenas

1. from math import factorial as fac
   
2. from time import time
   
3. 
   
4. s,t = 0,time()
   
5. fac_dict = {str(i):fac(i) for i in range(10)}
   
6. get_fac = fac_dict.get
   
7. 
   
8. for n in range(3,50000):
   
9.     if n == sum(map(get_fac,str(n))):
   
10.         s+=n
    
11.         
    
12. print(s,time()-t)

复制代码

无下限HENTAI

用最笨的办法写了一个遍历，用时好长……

1. from time import time
   
2. start = time()
   
3. 
   
4. def factorial(n):
   
5.     product = 1
   
6.     while n:
   
7.         product *= n
   
8.         n -= 1
   
9.     return product
   
10. 
    
11. member = []
    
12. for i in range(10,2177280):#7个9是2177280
    
13.     j = str(i)
    
14.     summary = 0
    
15.     for each in j:
    
16.         summary += factorial(int(each))
    
17.     if i == summary:
    
18.         member.append(i)
    
19. 
    
20. print('所有符合要求的数字是：',end = '')
    
21. for k in range(len(member)-1):
    
22.     print(member[k],end = ',')
    
23. print(member[-1])
    
24. print('它们的和是：%d'%sum(member))
    
25. 
    
26. print('总用时：%.5fs'%(time()-start))
    

复制代码

结果：
所有符合要求的数字是：145,40585
它们的和是：40730
总用时：37.74016s

过河的小卒

1. #计算0~9的阶乘
   
2. def count09():
   
3.     i = 1
   
4.     count = 1
   
5.     d = {}
   
6.     d[0] = 1
   
7.     while count<10:
   
8.         i = i*count
   
9.         d[count] = i
   
10.         count += 1
    
11.     return d
    
12. 
    
13. dict1 = count09()
    
14. def func(n,m):#n为位数，m为需要用到的阶乘数
    
15.     numlist = []
    
16.     for i in range(10**(n-1),10**n):
    
17.         s = 0
    
18.         for j in str(i):
    
19.             if int(j) not in range(m+1):
    
20.                 break
    
21.             s = s + dict1[int(j)]
    
22.         else:
    
23.             if s == i:
    
24.                 numlist.append(i)
    
25.     return numlist
    
26. 
    
27. l1 = func(2,4) + func(3,6) + func(4,7) + func(5,8)
    
28. print(l1,sum(l1))

复制代码

结果：
[145, 40585] 40730
算法效率很差

bacon6581

1. from time import time
   
2. start=time()
   
3. result=0
   
4. fact={0:1}
   
5. 
   
6. for j in range(1,10):
   
7.     x=j
   
8.     tot=1
   
9.     while x>1:
   
10.         tot=tot*x
    
11.         x-=1
    
12.     fact[j]=tot
    
13. print(fact)
    
14. 
    
15. for i in range(3,2999999):
    
16.     tot=0
    
17.     n6=int(i/1000000)
    
18.     n5=int((i-n6*1000000)/100000)
    
19.     n4=int((i-n6*1000000-n5*100000)/10000)
    
20.     n3=int((i-n6*1000000-n5*100000-n4*10000)/1000)
    
21.     n2=int((i-n6*1000000-n5*100000-n4*10000-n3*1000)/100)
    
22.     n1=int((i-n6*1000000-n5*100000-n4*10000-n3*1000-n2*100)/10)
    
23.     n0=i-n6*1000000-n5*100000-n4*10000-n3*1000-n2*100-n1*10
    
24. 
    
25.     if i>1000000 and i==fact[n6]+fact[n5]+fact[n4]+fact[n3]+fact[n2]+fact[n1]+fact[n0]:
    
26.         result+=i
    
27.     elif 1000000>i>100000 and i==fact[n5]+fact[n4]+fact[n3]+fact[n2]+fact[n1]+fact[n0]:
    
28.         result+=i
    
29.     elif 100000>i>10000 and i==fact[n4]+fact[n3]+fact[n2]+fact[n1]+fact[n0]:
    
30.         result+=i
    
31.     elif 10000>i>1000 and i==fact[n3]+fact[n2]+fact[n1]+fact[n0]:
    
32.         result+=i
    
33.     elif 1000>i>100 and i==fact[n2]+fact[n1]+fact[n0]:
    
34.         result+=i
    
35.     elif 100>i>10 and i==fact[n1]+fact[n0]:
    
36.         result+=i
    
37.     elif i<10 and i==fact[n0]:
    
38.         result+=i
    
39. print(result)
    
40. print(time()-start)

复制代码

1. >>>
   
2. {0: 1, 1: 1, 2: 2, 3: 6, 4: 24, 5: 120, 6: 720, 7: 5040, 8: 40320, 9: 362880}
   
3. 40730
   
4. 171.1605212688446

复制代码

lugewin

1. #-------新手请指导--------
   
2. def jiecheng(m):
   
3.     '计算出m的阶乘!'
   
4.     if m ==1 or m ==0:
   
5.         return 1
   
6.     return m*jiecheng(m-1)
   
7. 
   
8. def add(n):
   
9.     '算出n每位的阶乘之和'
   
10.     b = str(n)
    
11.     x =0
    
12.     for i in range(0,len(b)):
    
13.         y =jiecheng(int(b[i]))
    
14.         i +=1
    
15.         x += y
    
16.     return x
    
17. 
    
18. q = 3
    
19. while True:
    
20.     if q == add(q):
    
21.         print(q)
    
22.     q += 1
    

复制代码

小剑剑

1. from math import factorial
   
2. from time import time
   
3. from itertools import combinations_with_replacement,permutations
   
4. string1,string2,a,time1,su='123456789','0123456789',[],time(),0
   
5. for i in range(10):
   
6.        a.append(factorial(i))
   
7.       
   
8. for i in range(2,6):
   
9.        b=list(combinations_with_replacement(string2,i))
   
10.        for ii in b:
    
11.               value=(sum(map(lambda x:a[int(x)],ii)))
    
12.               if value==i:
    
13.                      continue
    
14.               possible_value=map(lambda x:int(''.join(x)),permutations(ii))
    
15.               for iii in possible_value:
    
16.                      if iii<10**(i-1):
    
17.                             continue
    
18.                      if iii==value:
    
19.                             su+=value
    
20.                             break
    
21. 
    
22. time2=time()
    
23. print(time2-time1,su)
    
24. 40730

复制代码

huomqh

1. def g(x):
   
2.     s=0
   
3.     for i in str(x):
   
4.         t=1
   
5.         for j in range(1,int(i)+1):
   
6.             t *= j
   
7.         s+=t
   
8.     return s
   
9. list1=[]
   
10. ss=0
    
11. for f in range(3,999999):
    
12.     if f==g(f):
    
13.         ss+=f
    
14. print(ss)
    
15. 
    

复制代码

低调的人！

1. def Fac(num):
   
2.     for each in range(1,num):
   
3.         num=each*num
   
4.     return num
   
5. result=0
   
6. for num in range(3,2540160):
   
7.     for each in str(num):
   
8.         result=Fac(int(each))+result
   
9.     if num==result:
   
10.         print(num,end=' ')
    
11.     result=0

复制代码

老忘

经分析n位数的阶乘和，当n>7时，阶乘和位数终始小于n，所以代码如下：

1. -*- coding:Utf-8 -*-
   
2. import itertools
   
3. import time
   
4. start = time.clock()
   
5. 
   
6. def js(i): # 计算i的阶乘
   
7.     pd=1
   
8.     for a in range(1,i+1):
   
9.         pd*=a
   
10.     return pd
    
11. def js_sum(numbers): #计算numbers各位数阶乘和
    
12.     pd_sum=0
    
13.     for each in numbers:
    
14.         pd_sum+=dict_js[int(each)]
    
15.     return pd_sum
    
16. 
    
17. def check_num(str_num):
    
18.     if int(str_num)==js_sum(str_num):
    
19.         return 1
    
20.     return 0
    
21. 
    
22. dict_js={}
    
23. for j in range(1,10):
    
24.     dict_js[j]=js(j)
    
25. for i in range(2,8):
    
26.     for each in list(itertools.product(['1','2','3','4','5','6','7','8','9'],repeat = i)):
    
27.         s = ''
    
28.         for eachone in each:
    
29.             s = s + eachone
    
30.         if check_num(s):
    
31.             print(s)
    
32. 
    
33. 
    
34. 
    
35. end = time.clock()
    
36. print ("read: %f s" % (end - start))

复制代码

最后结果如下：

1. 145
   
2. read: 36.527411 s

复制代码

效率很低啊！

无下限HENTAI

lugewin 发表于 2016-8-30 09:29

我想问一下，迭代和递归的时间复杂度应该都是O(n)吧

老忘

wangzhenas 发表于 2016-8-28 22:48

请问

1. for n in range(3,50000):
   
2. .......

复制代码

这里的范围(3,50000)是怎么分析出来的呢？特别是上限50000

低调的人！

我的答案的错误原因不是因为result的位置放错了，而是我的阶乘函数里忘记考虑了0的阶乘是1这个问题。答案的截图是我用以前的一个阶乘函数的文件来修改的。只不过后来就自己重新做了一个答案，没验证就就放上去了。希望把点评改一下，避免其他人不理解啊

冬雪雪冬

低调的人！ 发表于 2016-9-7 13:59
我的答案的错误原因不是因为result的位置放错了，而是我的阶乘函数里忘记考虑了0的阶乘是1这个问题。答案的 ...

好的，删除了。

老忘

低调的人！ 发表于 2016-9-7 13:59
我的答案的错误原因不是因为result的位置放错了，而是我的阶乘函数里忘记考虑了0的阶乘是1这个问题。答案的 ...

我和你一样，没有考虑0，但我是因为举的例子中没有0，所以以为不用考虑

mather

wangzhenas 发表于 2016-8-28 22:48

这个50000的上限怎么确定的？

过河的小卒

老忘 发表于 2016-9-7 08:47
请问

很显然作者是跑完结果后修改的上限（我也是这样。。。），单从理论分析只能判断出符合题意的数字在7位数以下