题目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!很长的数

愤怒的大头菇

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

print(sum(list1))

结果是:40730

芒果加黄桃

# encoding:utf-8
# 1! + 4! + 5! = 145 找类似组合
from time import time 
from math import factorial
from itertools import permutations
def euler034():
    l_facs = [factorial(x) for x in range(0, 10)]
    print(l_facs)
    for f in range(2, 7):
        l_temp = [k for (k, v) in enumerate(l_facs) if v < 10 ** f]
        for each in permutations(l_temp, f):
            n_t = ''
            nums = 0
            for t in each:
                n_t += str(t)
                nums += l_facs[t]
            if nums == int(n_t):
                print(nums)
def euler034_1():
    l_facs = [factorial(x) for x in range(0, 10)]
    print(l_facs)
    for i in range(11, l_facs[9] * 7):
        tmp = list(str(i))
        sums = sum([l_facs[int(k)] for k in tmp])
        if i == sums:
            print(i)
if __name__ == '__main__':
    start = time() 
    euler034()
    print('cost %.6f sec' % (time() - start))
    start = time() 
    euler034_1()
    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

function Output = Problem34()
tic
n = 1000000;
Value = ones(1,n)*(-1);
Value(1:9) = factorial([1 2 3 4 5 6 7 8 9]);
for ii = 1:n
    if Value(ii) == -1
        %disp(ii)
        Perms = str2num(perms(num2str(ii)));  %用于矢量
        value = sum( factorial(num2str(ii) - '0'));
        L = length(Perms);
        for jj = 1:L
            if Value(Perms(jj)) == -1
                Value(Perms(jj)) = value;
            end
        end
    end
end

%Set = find(Value == Value);
 All = Value == 1:n;
 for ii = 1:n
     if All(ii) == 1
         disp(ii)
     end
 end
 Output = sum(Value(All)) - 3; %去掉 1！ = 1 和 2！ = 2
toc 
disp('此代码使用matlab编程')
disp(['Problem34所用时间为',num2str(toc),'秒'])
disp(['Problem34的答案为',num2str(Output)])
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秒

import functools
import math
import time


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

永恒的蓝色梦想

C++ 854ms

#include<iostream>
using namespace std;


int main() {
    const static unsigned int map[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
    unsigned int sum = 0, temp, i, j;

    for (i = 10; i < 10000000; i++) {
        temp = 0;
        j = i;

        while (j) {
            temp += map[j % 10];
            j /= 10;
        }

        if (temp == i) {
            sum += i;
        }
    }

    cout << sum << endl;
    return 0;
}

debuggerzh

40730

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

#include<iostream>
using namespace std;

const int M = 1e7;
const int factorial[] = {1,1,2,6,24,120,720,5040,40320,362880};

int judge(int x){
  int x0 = x;
  int sum = 0;
  while(x){
    int current_digit = x % 10;
    sum += factorial[current_digit];
    x /= 10;
  }
  return x0 == sum ? x0 : 0;
}

int main(){
  int ans = 0;

  for (int i = 3;i < M;i++){
    ans += judge(i);
  }

  cout << ans << endl;
  return 0;
}

a1351468657

#include <stdio.h>

int fact(int);
int fact(int n)
{
        if (n == 0)
        {
                return 1;
        }
        else
        {
                return n * fact(n - 1);
        }
}

main()
{
        int i, j, a, sum = 0, count;
        
        

        for (i = 10; i < 1000000; i++)
        {
                count = 0;
                j = i;
                while (j)
                {
                        a = j % 10;
                        count += fact(a);
                        j /= 10;
                }
                if (i == count)
                {
                        sum += count;
                        printf("%d ", count);
                }
        }
        printf("\n%d\n", sum);
}

用了递归的方式求阶乘

guosl

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

/*
答案：40730
耗时：0.055327秒（单核）
      0.009392秒（六核）
*/
#include <cstdio>
#include <cstring>
#include <omp.h>
using namespace std;

const int b[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };

int main(void)
{
  int nSum = 0;
#pragma omp parallel for reduction(+:nSum)
  for (int n = 10; n < 10000000; ++n)
  {
    int nS = 0;
    int k = n;
    while (k > 0)
    {
      nS += b[k % 10];
      k /= 10;
    }
    if (nS == n)
      nSum += nS;
  }
  printf_s("%d\n", nSum);
  return 0;
}

TLM

[145, 40585]
40730
Time:0.17680621147155762s

"""
k<=8
将数字分成前4位后5位的结构，计算后五位结果并记录误差（输出误差为零的数据）
计算前四位误差，在前面五位结果中【查询】误差的相反数（误差和为零，即为相等）
此方法复杂度为O(sqrt(n)),n=10**9
实际上应该是n取10**8，后面想明白了，但是屎山已成
"""
# import random
import time
st=time.time()
a=[]
ans=0
jiecheng=[]
num=1
jiecheng.append(num)
# 获取前100000项的数据与误差数
num2err=dict()
num2err[0]=jiecheng[0]+4
err2num=dict()
err2num[num2err[0]]=[0]
for i in range(1,10):
    num=num*i
    jiecheng.append(num)
    num2err[i]=jiecheng[i]-i+4
ii=1
for i in range(1,5):
    ii=ii*10
    for j in range(1,10):
        for k in range(ii):
            num2err[j*ii+k]=num2err[k]+jiecheng[j]-j*ii-1
            if num2err[j*ii+k] in err2num:
                err2num[num2err[j*ii+k]].append(j*ii+k)
            else:
                err2num[num2err[j*ii+k]]=[j*ii+k]
            if num2err[j*ii+k]+i==4:
                a.append(j*ii+k)
                ans=ans+(j*ii+k)
# data0=dict()
ii=1
jj=10**4
for i in range(4):
    ii=ii*10
    for j in range(1,10):
        for k in range(ii):
            err=-(num2err[k]-5+i+k+jiecheng[j]-(j*ii+k)*jj)
            if err in err2num:
                for data in err2num[err]:
                    if data>=jj:
                        break
                    a.append((j*ii+k)*jj+data)
                    ans=ans+((j*ii+k)*jj+data)
            # data0[j*ii+k]=-err
print(a)
print(ans)
print('Time:{}s'.format(time.time()-st))
# u=random.randint(1,10000-1)
# w=random.randint(1,1000-1)
# print((u,w))
# print(data0[w]+num2err[u])
# uu=(w)*jj+u
# v=0
# while uu>0:
#     v=v+jiecheng[uu%10]
#     uu=uu//10
# print(v-((w)*jj+u))

mathtimes

fn bits_factorial(x: u128) -> u128 {
    let mut x = x;
    let mut sum = 0;
    while x != 0 {
        sum += (1..=(x%10)).product::<u128>();
        x /= 10;
    }
    sum
}

fn main () {
    let mut sum = 0;
    for i in 1..99999999 {
        if i == bits_factorial(i) {
            sum += i;
        }
    }
    println!("{}", sum - 3);
}