小练习： 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

dics = {}
for x in range(10):
    if x==0:
        dics[0]=1
    else:
        dics[x] = dics[x-1]*x

res = 0
for i in range(11,10**7):
    sums = 0
    tem = i
    while tem>0:
        sums = sums + dics[tem%10]
        tem = tem//10
        if sums>i:
            break
    if sums==i:
        res = res+i
print(res)

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

冬雪雪冬

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

import math
list1 = [math.factorial(i) for i in range(0, 10)]
sum2 = 0
for i in range(10, 2177283):
    j = i
    sum1 = 0
    while j > 0:
        sum1 += list1[j % 10]
        j //= 10
    if sum1 == i:
        sum2 += sum1
print(sum2)

结果是40730

wangzhenas

from math import factorial as fac
from time import time

s,t = 0,time()
fac_dict = {str(i):fac(i) for i in range(10)}
get_fac = fac_dict.get

for n in range(3,50000):
    if n == sum(map(get_fac,str(n))):
        s+=n
        
print(s,time()-t)

无下限HENTAI

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

from time import time
start = time()

def factorial(n):
    product = 1
    while n:
        product *= n
        n -= 1
    return product

member = []
for i in range(10,2177280):#7个9是2177280
    j = str(i)
    summary = 0
    for each in j:
        summary += factorial(int(each))
    if i == summary:
        member.append(i)

print('所有符合要求的数字是：',end = '')
for k in range(len(member)-1):
    print(member[k],end = ',')
print(member[-1])
print('它们的和是：%d'%sum(member))

print('总用时：%.5fs'%(time()-start))

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

过河的小卒

#计算0~9的阶乘
def count09():
    i = 1
    count = 1
    d = {}
    d[0] = 1
    while count<10:
        i = i*count
        d[count] = i
        count += 1
    return d

dict1 = count09()
def func(n,m):#n为位数，m为需要用到的阶乘数
    numlist = []
    for i in range(10**(n-1),10**n):
        s = 0
        for j in str(i):
            if int(j) not in range(m+1):
                break
            s = s + dict1[int(j)]
        else:
            if s == i:
                numlist.append(i)
    return numlist

l1 = func(2,4) + func(3,6) + func(4,7) + func(5,8)
print(l1,sum(l1))

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

bacon6581

from time import time
start=time()
result=0
fact={0:1}

for j in range(1,10):
    x=j
    tot=1
    while x>1:
        tot=tot*x
        x-=1
    fact[j]=tot
print(fact)

for i in range(3,2999999):
    tot=0
    n6=int(i/1000000)
    n5=int((i-n6*1000000)/100000)
    n4=int((i-n6*1000000-n5*100000)/10000)
    n3=int((i-n6*1000000-n5*100000-n4*10000)/1000)
    n2=int((i-n6*1000000-n5*100000-n4*10000-n3*1000)/100)
    n1=int((i-n6*1000000-n5*100000-n4*10000-n3*1000-n2*100)/10)
    n0=i-n6*1000000-n5*100000-n4*10000-n3*1000-n2*100-n1*10

    if i>1000000 and i==fact[n6]+fact[n5]+fact[n4]+fact[n3]+fact[n2]+fact[n1]+fact[n0]:
        result+=i
    elif 1000000>i>100000 and i==fact[n5]+fact[n4]+fact[n3]+fact[n2]+fact[n1]+fact[n0]:
        result+=i
    elif 100000>i>10000 and i==fact[n4]+fact[n3]+fact[n2]+fact[n1]+fact[n0]:
        result+=i
    elif 10000>i>1000 and i==fact[n3]+fact[n2]+fact[n1]+fact[n0]:
        result+=i
    elif 1000>i>100 and i==fact[n2]+fact[n1]+fact[n0]:
        result+=i
    elif 100>i>10 and i==fact[n1]+fact[n0]:
        result+=i
    elif i<10 and i==fact[n0]:
        result+=i
print(result)
print(time()-start)

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

lugewin

#-------新手请指导--------
def jiecheng(m):
    '计算出m的阶乘!'
    if m ==1 or m ==0:
        return 1
    return m*jiecheng(m-1)

def add(n):
    '算出n每位的阶乘之和'
    b = str(n)
    x =0
    for i in range(0,len(b)):
        y =jiecheng(int(b[i]))
        i +=1
        x += y
    return x

q = 3
while True:
    if q == add(q):
        print(q)
    q += 1

小剑剑

from math import factorial
from time import time 
from itertools import combinations_with_replacement,permutations
string1,string2,a,time1,su='123456789','0123456789',[],time(),0
for i in range(10):
       a.append(factorial(i))
       
for i in range(2,6):
       b=list(combinations_with_replacement(string2,i))
       for ii in b:
              value=(sum(map(lambda x:a[int(x)],ii)))
              if value==i:
                     continue
              possible_value=map(lambda x:int(''.join(x)),permutations(ii))
              for iii in possible_value:
                     if iii<10**(i-1):
                            continue
                     if iii==value:
                            su+=value
                            break

time2=time()
print(time2-time1,su)
40730

huomqh

def g(x):
    s=0
    for i in str(x):
        t=1
        for j in range(1,int(i)+1):
            t *= j
        s+=t
    return s
list1=[]
ss=0
for f in range(3,999999):
    if f==g(f):
        ss+=f
print(ss)

低调的人！

def Fac(num):
    for each in range(1,num):
        num=each*num
    return num
result=0
for num in range(3,2540160):
    for each in str(num):
        result=Fac(int(each))+result
    if num==result:
        print(num,end=' ')
    result=0

老忘

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

 -*- coding:Utf-8 -*-
import itertools
import time
start = time.clock()

def js(i): # 计算i的阶乘
    pd=1
    for a in range(1,i+1):
        pd*=a
    return pd
def js_sum(numbers): #计算numbers各位数阶乘和
    pd_sum=0
    for each in numbers:
        pd_sum+=dict_js[int(each)]
    return pd_sum

def check_num(str_num):
    if int(str_num)==js_sum(str_num):
        return 1
    return 0

dict_js={}
for j in range(1,10):
    dict_js[j]=js(j)
for i in range(2,8):
    for each in list(itertools.product(['1','2','3','4','5','6','7','8','9'],repeat = i)):
        s = ''
        for eachone in each:
            s = s + eachone
        if check_num(s):
            print(s)



end = time.clock()
print ("read: %f s" % (end - start))

最后结果如下：

145
read: 36.527411 s

效率很低啊！

无下限HENTAI

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

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

老忘

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

请问

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

这里的范围(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位数以下