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

欧拉计划 · 发表于 2015-4-23 23:47:03

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

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 不是和的形式，所以它们不算在内。

迷雾少年 · 发表于 2016-8-29 17:13:27

用大数算了 100!很长的数

愤怒的大头菇 · 发表于 2016-9-2 17:13:44

#当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

芒果加黄桃 · 发表于 2017-1-13 23:12:27

# 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

渡风 · 发表于 2017-6-15 07:47:21

%% 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 · 发表于 2018-9-10 21:11:27

结果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)

王小召 · 发表于 2019-6-13 13:46:30

结果是:[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()))

复制代码

永恒的蓝色梦想 · 发表于 2020-4-18 19:01:21

本帖最后由永恒的蓝色梦想于 2020-5-8 09:01 编辑

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 · 发表于 2020-8-5 11:17:23

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 · 发表于 2021-3-15 10:00:00

#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 · 发表于 2022-1-3 15:29:48

本帖最后由 guosl 于 2022-1-3 15:36 编辑

当数字是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 · 发表于 2023-2-16 20:30:01

本帖最后由 TLM 于 2023-2-16 20:34 编辑

[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 · 发表于 2023-10-12 17:16:10

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);
}

复制代码

账号		自动登录	找回密码
密码			立即注册

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

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块