题目34：找出所有等于各位数阶乘之和的数字之和
Digit factorials145 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 =
print(l_facs)
for f in range(2, 7):
l_temp =
for each in permutations(l_temp, f):
n_t = ''
nums = 0
for t in each:
n_t += str(t)
nums += l_facs
if nums == int(n_t):
print(nums)
def euler034_1():
l_facs =
print(l_facs)
for i in range(11, l_facs * 7):
tmp = list(str(i))
sums = sum( 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))
一种用排列，不含重复数字的；一种暴力求解，可以喊重复数字。结果如下：
145
cost 0.481362 sec
145
40585
cost 8.705163 sec
%% Problem34.m
% 最后编辑时间：17-06-05 0:18
% 问题：找到所有满足一下条件的数，这个数的值等于各个位数阶乘的和，再求和
% 分析：这些书一定在100w之内
% Problem34所用时间为7.2159秒
% Problem34的答案为40730function Output = Problem34()
tic
n = 1000000;
Value = ones(1,n)*(-1);
Value(1:9) = factorial();
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
结果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))
# 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) 结果是:
用时：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, )
if res == num:
result.append(num)
value += 1
return result
print("结果是:{}\n用时：{:.2f}秒".format(get_result(2), time.process_time())) 本帖最后由 永恒的蓝色梦想 于 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;
}
if (temp == i) {
sum += i;
}
}
cout << sum << endl;
return 0;
} 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;
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;
}
#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: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;
}
if (nS == n)
nSum += nS;
}
printf_s("%d\n", nSum);
return 0;
}
本帖最后由 TLM 于 2023-2-16 20:34 编辑
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=jiecheng+4
err2num=dict()
err2num]=
for i in range(1,10):
num=num*i
jiecheng.append(num)
num2err=jiecheng-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=num2err+jiecheng-j*ii-1
if num2err in err2num:
err2num].append(j*ii+k)
else:
err2num]=
if num2err+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-5+i+k+jiecheng-(j*ii+k)*jj)
if err in err2num:
for data in err2num:
if data>=jj:
break
a.append((j*ii+k)*jj+data)
ans=ans+((j*ii+k)*jj+data)
# data0=-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+num2err)
# uu=(w)*jj+u
# v=0
# while uu>0:
# v=v+jiecheng
# uu=uu//10
# print(v-((w)*jj+u)) 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);
}
页:
[1]