题目30：找出所有能够写成各位数字5次方之和的数之和

欧拉计划

Digit fifth powers

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:



is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

题目：

令人惊奇的，只有三个数能够写成它们各位数的四次方之和：



没有被算作在内因为它不是一个和。

这些数字的和是 1634 + 8208 + 9474 = 19316.

找出所有能被写成各位数字五次方之和的数之和。

Estein

结果为：443839
代码如下：

1. result = []
   
2. for i in range(1,10):
   
3.     if i**5*i < int(str(9)*i):
   
4.         up_boundary = i**5*i
   
5. for j in range(2,up_boundary):
   
6.     length = len(str(j))
   
7.     s = 0
   
8.     for k in range(length):
   
9.         s += (int(str(j)[k]))**5
   
10.     if s == j:
    
11.         result.append(j)
    
12. print(sum(result))
    
13.    
    

复制代码

迷雾少年

有6个 数字
分别是 4150 4151 54748 92727 93084 194979
和是443839
代码

1. int divcalc(int num)
   
2. {
   
3.         int k = 0;
   
4.         int sum = 0;
   
5.         while ( num )
   
6.         {
   
7. 
   
8.                 k = num%10;
   
9.                 sum = sum + pow(k,5);
   
10.                 num/=10;
    
11.         }
    
12.         return sum;
    
13. }
    
14. int main()
    
15. {
    
16.     for (int n=2;n<=10000000;n++)
    
17.     {
    
18.                 if(n==divcalc(n))
    
19.                 {
    
20.                         std::cout<<n<<endl;
    
21.                 }
    
22.     }
    
23.         return 0;
    
24.        
    
25. }

复制代码

愤怒的大头菇

1. i = 1
   
2. result = 0
   
3. while True:
   
4.       temp = i
   
5.       total = 0
   
6.       while temp:
   
7.             total += (temp%10)**5
   
8.             temp = temp//10
   
9. 
   
10.       if total == i and i != 1:
    
11.             result += i
    
12.             print(result)
    
13.       i += 1

复制代码

等半天没有继续出结果最后一个是443839

jerryxjr1220

1. 
   
2. {194979, 4151, 4150, 92727, 54748, 93084} 443839
   
3. [Finished in 7.1s]
   
4. 
   
5. lst = []
   
6. for i in range(2,1000000):
   
7.         length = len(str(i))
   
8.         if int(str(i)[0])**5 <= i:
   
9.                 summ = 0
   
10.                 for j  in range(length):
    
11.                         summ += int(str(i)[j])**5
    
12.                 if summ == i:
    
13.                         lst.append (i)
    
14. lst = list(set(lst))
    
15. print (lst, sum(lst))

复制代码

376103327

一个期间内所有符合该算法的数
import math
def SumSXH(arg):
    Num = arg
    Count = 0
    Sum = 0
    eNum = len(str(Num))
    listNum = []
    for i in str(Num):
        listNum.append(i)
    while Count < eNum:
        Sum += math.pow(int(listNum[Count]), eNum)
        Count += 1
    return int(Sum)

NumStart = int(raw_input("StartNum: "))
NumEnd = int(raw_input("EndNum: "))
Count = NumStart
if NumStart >= NumEnd:
    print "The num is error!"
else:
    while Count < NumEnd:
        if Count == SumSXH(Count):
            print Count
        Count += 1


153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051

芒果加黄桃

1. # encoding:utf-8
   
2. # 找出所有能写成各位数字五次方之和的数之和
   
3. # 比如 ABCD = A**5 + B**5 + C**5 + D**5
   
4. from time import time
   
5. import itertools
   
6. def euler030():
   
7.     l_nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
   
8.     l_result = []
   
9.     #粗略算一下，只能是3-6位数之间
   
10.     for i in range(3, 7):
    
11.         for each in itertools.combinations_with_replacement(l_nums, i):
    
12.             n_sum = sum([x ** 5 for x in each])
    
13.             t1 = list(each)
    
14.             t1.sort()
    
15.             t2 = [int(n) for n in list(str(n_sum))]
    
16.             t2.sort()
    
17.             if t1 == t2:
    
18.                 l_result.append(n_sum)
    
19.     print(sum(l_result))           
    
20. if __name__ == '__main__':
    
21.     start = time()
    
22.     euler030()
    
23.     print('cost %.6f sec' % (time() - start))
    

复制代码

443839
cost 0.075007 sec

芒果加黄桃

376103327 发表于 2016-10-26 17:39
一个期间内所有符合该算法的数
import math
def SumSXH(arg):

第一个数算一下就不满足条件

渡风

此代码使用matlab编程
Problem30所用时间为50.6545秒
Problem30的答案为443839

1. %% Problem30
   
2. % 题目30:找出所有能够写成各位数字5次方之和的数之和
   
3. function Output=Problem30(Input)
   
4. tic
   
5. if nargin==0
   
6. Input=5;
   
7. end
   
8. %已经确定最多为6位数
   
9. Limit=sum([9 9 9 9 9 9].^Input);%上限
   
10. Sum=0;
    
11. disp(Limit)
    
12. for ii=2:Limit
    
13.     Temp=str2num(num2str(ii)')';
    
14.     if sum(Temp.^5)==ii
    
15.         disp(ii)
    
16.         Sum=Sum+ii;
    
17.     end
    
18. end
    
19. Output=Sum;
    
20. toc
    
21. disp('此代码使用matlab编程')
    
22. disp(['Problem30所用时间为',num2str(toc),'秒'])
    
23. disp(['Problem30的答案为',num2str(Output)])

复制代码

余欲渔

1. jh=[]
   
2. for i in range(20,295245):
   
3.     x=list(str(i))
   
4.     he=0
   
5.     for j in x:
   
6.         he+=int(j)**5
   
7.     if he==i:
   
8.         jh.append(i)
   
9. print(sum(jh),jh)

复制代码

1. == RESTART: C:\Users\ASUS\AppData\Local\Programs\Python\Python35-32\test.py ==
   
2. 443839 [4150, 4151, 54748, 92727, 93084, 194979]
   
3. >>>

复制代码

99592938

1. list1=[]
   
2. for i in range(10,5*9**5+2**5+1):
   
3.     st=str(i)
   
4.     sum0=0
   
5.     for j in st:
   
6.         sum0+=int(j)**5
   
7.     if sum0==i:
   
8.         list1.append(i)
   
9. print(sum(list1),list1)

复制代码

443839 [4150, 4151, 54748, 92727, 93084, 194979]
>>>

由我们主宰

1. public class DigitFifthPowers{
   
2.         public static void main(String[] args){
   
3.                 int n = 2;
   
4.                 int sum = 0;
   
5.                 int t = n;
   
6.                 int[] result = new int[10];
   
7.                 int count = 0;
   
8.                 for(n = 2;n < 1000000;n ++){
   
9.                         t = n;
   
10.                         count = 0;
    
11.                         for(int i = 0;i < result.length;i ++){
    
12.                                 result[i] = 0;
    
13.                         }
    
14.                        
    
15.                         while(t != 0){
    
16.                                 result[count++] = t % 10;
    
17.                                 t /= 10;
    
18.                         }
    
19.                         if(powerSum(n,result,count)){
    
20.                                 System.out.print(n+"\t");
    
21.                                 sum += n;
    
22.                         }
    
23.                 }       
    
24.                 System.out.println("\n它们的和为"+sum);
    
25.         }
    
26.         public static boolean powerSum(int n,int[] result,int count){
    
27.                 int sum = 0;
    
28.                 for(int i = 0;i < count;i ++){
    
29.                         sum += Math.pow(result[i],5);
    
30.                 }
    
31.                 if(sum == n){
    
32.                         return true;
    
33.                 }
    
34.                 else{
    
35.                         return false;
    
36.                 }
    
37.         }
    
38. }

复制代码

4150    4151    54748   92727   93084   194979
它们的和为443839

王小召

计算和是：443839
用时：2.8860185秒

1. import time
   
2. 
   
3. 
   
4. def dig_sum(num):
   
5.     sum = 0
   
6.     tmp = num
   
7.     while tmp > 0:
   
8.         sum += (tmp % 10)**5
   
9.         tmp = tmp//10
   
10.     if sum == num:
    
11.         return True
    
12.     else:
    
13.         return False
    
14. 
    
15. print("计算和是：{}\n用时：{}秒".format(sum([i for i in range(2, 1000000) if dig_sum(i)]), time.process_time()))

复制代码

永恒的蓝色梦想

C++ 67ms

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. 
   
5. int main() {
   
6.     int sum = 0, i, j, k, p[] = { 0, 1, 32, 243, 1024, 3125, 7776, 16807, 32768, 59049 };
   
7. 
   
8.     for (i = 10; i < 1000000; ++i) {
   
9.         j = 0;
   
10.         k = i;
    
11. 
    
12.         while (k) {
    
13.             j += p[k % 10];
    
14.             k /= 10;
    
15.         }
    
16. 
    
17.         sum += i == j;
    
18.     }
    
19. 
    
20.     cout << sum << endl;
    
21.     return 0;
    
22. }

复制代码

有马_冬巳

1. 
   
2. start = time.time()
   
3. 
   
4. a = 100
   
5. addup = 0
   
6. while a < 1000000:
   
7.     a = str(a)
   
8.     sum = 0
   
9.     for i in range(len(a)):
   
10.         sum += int(a[i])**5
    
11. 
    
12.     a = int(a)
    
13.     if sum == a:
    
14.         print(a)
    
15.         addup += a
    
16.     a += 1
    
17. print(addup)
    
18. 
    
19. 
    
20. end = time.time()
    
21. print("共用时%f秒" %(end - start))

复制代码

4150
4151
54748
92727
93084
194979
443839
共用时3.221054秒

a1351468657

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int sum_num(int);
   
5. int sum_num(int num)
   
6. {
   
7.         int i, sum = 0;
   
8.         i = num;
   
9.         while (i)
   
10.         {
    
11.                 sum += pow((i % 10), 5);
    
12.                 i /= 10;
    
13.         }
    
14.         return sum;
    
15. }
    
16. 
    
17. main()
    
18. {
    
19.         int i, j, sum = 0;
    
20. 
    
21.         for (i = 2; i < 1000000; i++)
    
22.         {
    
23.                 j = sum_num(i);
    
24.                 if (j == i)
    
25.                 {
    
26.                         sum += j;
    
27.                         printf("%d ", j);
    
28.                 }
    
29.         }
    
30.         printf("\n%d\n", sum);
    
31. }

复制代码

不知道还能不能优化， 望指教

ft215378

#找出所有能够写成各位数字5次方之和的数之和
from time import*
start = time()
a = 4150
res = []
result = []
while a < 200000:
    for i in str(a):
        res.append(int(i) ** 5)
    if sum(res) == a:
        result.append(a)
        res = []
    else:
        res = []
    a += 1
end = time()
print(result)
print(sum(result))
print("用时：%.2fs" % (end-start))

guosl

由于这个题目中没有给出数据范围，而又要求求出所有满足条件的数，为此我们首先要求出这题的数据范围，这样才能保证所有的数都被求出。假设这个数n是一个x位的10进制数，那么：
10^(x-1)<=n<=x*9^5，我们来看看满足这个不等式的x最大是多少？作函数 f(x)=x*9^5-10^(x-1),对这个函数求导得：f'(x)=9^5-(x-1)*10^(x-2)，我们可以计算出当x>=7时这个函数小于0，也就是说f(x)当x>=7时是一个严格的递减函数，或者换句话将就是：n将无法表示为其各位数字的5次方之和。故这样数的上限是：10^7。

1. /*
   
2. 答案：443839
   
3. 耗时：0.107251秒（单核）
   
4.       0.0160824秒（六核）
   
5. */
   
6. #include <iostream>
   
7. #include <omp.h>
   
8. using namespace std;
   
9. 
   
10. const int N = 10000000;
    
11. 
    
12. int getDigitsSum(int n)
    
13. {
    
14.   int nSum = 0;
    
15.   while (n > 0)
    
16.   {
    
17.     int k = n % 10;
    
18.     n /= 10;
    
19.     nSum += k * k * k * k * k;
    
20.   }
    
21.   return nSum;
    
22. }
    
23. 
    
24. int main(void)
    
25. {
    
26.   int nSum = 0;
    
27. #pragma omp parallel for reduction(+:nSum)
    
28.   for (int i = 2; i <= N; ++i)
    
29.   {
    
30.     if (i == getDigitsSum(i))
    
31.       nSum += i;
    
32.   }
    
33.   cout << nSum << endl;
    
34.   return 0;
    
35. }

复制代码

mathtimes

1. table = []
   
2. for i in range(10):
   
3.     for j in range(10):
   
4.         for k in range(10):
   
5.             for m in range(10):
   
6.                 for n in range(10):
   
7.                     for a in range(10):
   
8.                         if(100000*a+10000*n+1000*m+100*k+10*i+j==i**5+j**5+k**5+m**5+n**5+a**5):
   
9.                             table.append(100000*a+10000*n+1000*m+100*k+10*i+j)
   
10. table.remove(0)
    
11. table.remove(1)
    
12. print(table,"\n",sum(table))

复制代码

[92727, 54748, 4150, 4151, 194979, 93084]
443839

[Done] exited with code=0 in 1.53 seconds

Asss-whom

1. use rayon::prelude::*;
   
2. use std::time::Instant;
   
3. 
   
4. fn main() {
   
5.     let now = Instant::now();
   
6.     let num: i32 = (2..354294) // (9 ^ 5) * 6 < 999999
   
7.         .into_par_iter()
   
8.         .filter(|x| check(*x))
   
9.         .sum();
   
10.     println!("cost {}ms.", now.elapsed().as_millis());
    
11.     println!("{:?}", num)
    
12. }
    
13. 
    
14. fn check(num: i32) -> bool {
    
15.     let mut value = 0;
    
16.     for i in num.to_string().bytes() {
    
17.         value += ((i - 48) as i32).pow(5)
    
18.     }
    
19.     value == num
    
20. }
    

复制代码

cost 10ms.
443839