题目56：对于形如a的b次方的数字，找出最大的各位和

欧拉计划

Powerful digit sum

A googol is a massive number: one followed by one-hundred zeros; is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, , where a, b < 100, what is the maximum digital sum?

题目：

一个 googol 是一个巨大的数字：1 后面跟着 100 个 0； 几乎是不可想象的大：1 后面跟着 200 个 0。它们虽然很大，但是它们的各位数之和却只有 1。

考虑形如 的数, 其中 a, b < 100，最大的各位和是多少？

迷雾少年

最大的是  99的95次方   各位数的和是972

1. int getResult(string &str)
   
2. {
   
3.         //将str各位加起来
   
4.         int re=0;
   
5.         for (int n =0;n<str.size();n++)
   
6.                 re+=str[n]-'0';
   
7.         return re;
   
8. }
   
9. int main()
   
10. {
    
11.        
    
12.         int max=0;
    
13. 
    
14.         //记录下指数和底数
    
15.         int zhi,di;
    
16.         for (int z=2;z<=100;z++)
    
17.         {
    
18.                 for (int k=2;k<=100;k++)
    
19.                 {
    
20.                         //底数是z  指数是k
    
21.                         char buf[20];
    
22.                         itoa(z,buf,10);
    
23.                         strcat(buf,".0");
    
24.                         string result;
    
25.                         result = BigNum_factorial(buf,k); //大数幂
    
26.                         int n=getResult(result);
    
27.                         if(n>max)
    
28.                    {
    
29.                            zhi=k;
    
30.                             di=z;
    
31.                            max=n;
    
32.                         }
    
33.                 }
    
34.         }
    
35.         std::cout<<max<<endl<<di<<endl<<zhi<<endl;
    
36.         return 0;
    
37. }

复制代码

jerryxjr1220

1. 最大各位和是99的95次方得到的972
   
2. 
   
3. '''求a**b 的各位和最大值'''
   
4. maxi,maxa,maxb = 0,0,0
   
5. for a in range(99,1,-1):
   
6.         for b in range(99,1,-1):
   
7.                 summ = 0
   
8.                 test = str(a**b)
   
9.                 for each in test:
   
10.                         summ += int(each)
    
11.                 if maxi < summ:
    
12.                         maxi,maxa,maxb = summ,a,b
    
13. print ('最大各位和是%d的%d次方得到的%d' % (maxa,maxb,maxi))

复制代码

愤怒的大头菇

1. def Figure(a,b):
   
2.     temp = a**b
   
3.     count = 0
   
4.     for each in str(temp):
   
5.         count +=int(each)
   
6.     return count
   
7. temp = 0
   
8. for i in range(1,100):
   
9.     for j in range(1,100):
   
10.         sum1 = Figure(i,j)
    
11.         if sum1 > temp:
    
12.             temp = sum1
    
13. print(temp)

复制代码

结果：972

芒果加黄桃

1. # encoding:utf-8
   
2. # a,b<100,计算a**b各位数之和最大的
   
3. from time import time
   
4. def euler056(N=1000000):
   
5.     maxsum = 0
   
6.     a, b = 0, 0
   
7.     for i in range(1, 100):
   
8.         for j in range(1, 100):
   
9.             t = sum(int(x) for x in str(i ** j))
   
10.             if t > maxsum:
    
11.                 maxsum = t
    
12.                 a, b = i, j
    
13.     print(maxsum, a, b)
    
14. if __name__ == '__main__':
    
15.     start = time()
    
16.     euler056()
    
17.     print('cost %.6f sec' % (time() - start))
    

复制代码

飘飞的白杨

1. y = 0
   
2. for i in range(1,101):
   
3.     for j in range(1,101):
   
4.         x = sum([int(n) for n in str(i**j)])
   
5.         y = max(x, y)
   
6. print(y)

复制代码

渡风

在此吐槽MATLAB vpa的大数计算精度。算法没错。结果错了
此代码使用matlab和Python编程
Problem56所用时间为： 1.1116秒
Problem56的答案为： 972

1. % 最后编辑时间：17-06-18 12：15
   
2. % 0 <a,b<100 a^b 所有位数相加起来最大的那个数是？
   
3. % 解决要点，使用Python 和 MATLAB 联合编程
   
4. % Problem56所用时间为： 2.2817秒
   
5. % Problem56的答案为： 972
   
6. 
   
7. function Output = Problem56()
   
8. tic
   
9. Output = 0;
   
10. bottom = 0;
    
11. power = 0;
    
12. for a = 99:-1:1
    
13.     for b = 99:-1:1
    
14.          Score = py.Fun56.PowTotal(int32(a),int32(b));  %调用Python函数
    
15.         if Score > Output         
    
16.             Output = Score ;
    
17.             disp(Output)
    
18.             bottom = a;
    
19.             power = b;
    
20.         end
    
21.     end
    
22. end
    
23. disp(bottom)
    
24. disp(power)                                    
    
25. toc
    
26. disp('此代码使用matlab和Python编程')
    
27. disp(['Problem56所用时间为： ',num2str(toc),'秒'])
    
28. disp(['Problem56的答案为： ',char(Output)])
    
29. end
    

复制代码

Python 文件

1. #输入a , b 判断 a** b的所有位数的和
   
2. def PowTotal(a,b):
   
3.     Num = str(a**b)
   
4.     Vec = [int(x) for x in Num ]
   
5.     Sum = sum(Vec)
   
6.     return Sum
   
7. #end

复制代码

   

najin

用的matlab计算
结果是
   972

时间已过 4.927415 秒。
>>

k往事如烟k

972

1. def digital_sum(num):
   
2.     sum = 0
   
3.     for each in str(num):
   
4.         sum += int(each)
   
5.     return sum
   
6. 
   
7. sum = 1
   
8. for i in range(1, 100):
   
9.     for j in range(1,100):
   
10.         if digital_sum(pow(i, j)) > sum:
    
11.             sum = digital_sum(pow(i, j))
    
12. 
    
13. print(sum)

复制代码

王小召

最大a的b次方的数字各位和是：972
用时：0.4212027 秒

1. import time
   
2. 
   
3. result = []
   
4. for a in range(2, 100):
   
5.     for b in range(1, 100):
   
6.         result.append(sum([int(letter) for letter in str(a**b)]))
   
7. print("最大a的b次方的数字各位和是：{}\n用时：{} 秒".format(max(result), time.process_time()))

复制代码

永恒的蓝色梦想

1. print(max(sum(map(int, str(a ** b))) for a in range(100) for b in range(100)))

复制代码

debuggerzh

972

Process returned 0 (0x0)   execution time : 0.942 s
Press any key to continue.
高精度乘法

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<cstdio>
   
4. #include<cstring>
   
5. using namespace std;
   
6. 
   
7. const int M = 100;
   
8. int pw[250];
   
9. 
   
10. void ini_pw(){
    
11.   memset(pw,0,sizeof(pw));
    
12.   pw[0] = 1;
    
13. }
    
14. 
    
15. int mult(int x){
    
16.   for (int i = 0;i < 200;i++){
    
17.     pw[i] *= x;
    
18.   }
    
19.   for (int i = 0;i < 200;i++){
    
20.     pw[i+1] += pw[i] / 10;
    
21.     pw[i] %= 10;
    
22.   }
    
23.   int res = 0;
    
24.   for (int i = 0;i < 200;i++){
    
25.     res += pw[i];
    
26.   }
    
27.   return res;
    
28. }
    
29. 
    
30. int main(){
    
31.   int ans = 0;
    
32. 
    
33.   for (int a = 2;a < M;a++){
    
34.     for (int b = 2;b < M;b++){
    
35.       ini_pw();
    
36. 
    
37.       for (int i = 0;i < b;i++){
    
38.         ans = max(mult(a),ans);
    
39.       }
    
40.     }
    
41.   }
    
42.   cout << ans << endl;
    
43.   return 0;
    
44. }
    

复制代码

4444567

99的95次方最大，各位和为972

1. def he(n):
   
2.     return sum(int(i) for i in str(n))
   
3. 
   
4. max1 = 0
   
5. for a in range(1,100):
   
6.     for b in range(1,100):
   
7.         if he(a**b) > max1:
   
8.             a1 = a
   
9.             b1 = b
   
10.             max1 = he(a**b)
    
11. 
    
12. print('%d的%d次方最大，各位和为%d' % (a1,b1,max1))
    

复制代码

guosl

直接调用大数库mpir.

1. /*
   
2. 欧拉问题56
   
3. 答案：972
   
4. 耗时：0.005703秒（单核）
   
5.       0.001556秒（6核）
   
6. */
   
7. #include <cstdio>
   
8. #include <mpir.h>
   
9. #include <omp.h>
   
10. #include <cstring>
    
11. 
    
12. int main(void)
    
13. {
    
14.   int k = omp_get_max_threads();
    
15.   mpz_t* mb = new mpz_t[k];
    
16.   int nMSum = 0;
    
17. #pragma omp parallel reduction(max:nMSum) shared(mb)
    
18.   {
    
19.     int k = omp_get_thread_num();
    
20.     mpz_init(mb[k]);
    
21. #pragma omp for collapse(2)
    
22.     for (int b = 2; b < 100; ++b)
    
23.     {
    
24.       for (int a = 2; a < 100; ++a)
    
25.       {
    
26.         int p = omp_get_thread_num();
    
27.         mpz_ui_pow_ui(mb[p], b, a);
    
28.         char str[256];
    
29.         memset(str, 0, sizeof(str));
    
30.         mpz_get_str(str, 10, mb[p]);
    
31.         int lSum = 0;
    
32.         for (int i = 0; i < (int)strlen(str); ++i)
    
33.           lSum += int(str[i] - 48);
    
34.         nMSum = (nMSum > lSum) ? nMSum : lSum;
    
35.       }
    
36.     }
    
37.     mpz_clear(mb[k]);
    
38.   }
    
39.   delete[] mb;
    
40.   printf_s("%d\n", nMSum);
    
41.   return 0;
    
42. }
    

复制代码

Asss-whom

1. use rayon::prelude::*;
   
2. use num::bigint::ToBigUint;
   
3. use num::bigint::BigUint;
   
4. use std::time::Instant;
   
5. 
   
6. fn main() {
   
7.     let now = Instant::now();
   
8.     let num: u32 = (1..101u32)
   
9.         .into_par_iter()
   
10.         .map(|x| {
    
11.             let a = x.to_biguint().unwrap();
    
12.             (1..101u32)
    
13.                 .into_par_iter()
    
14.                 .map(|b| s(a.pow(b)))
    
15.                 .max()
    
16.                 .unwrap()
    
17.         })
    
18.         .max()
    
19.         .unwrap();
    
20.     println!("cost {}ms.", now.elapsed().as_millis());
    
21.     println!("{:?}", num)
    
22. }
    
23. 
    
24. fn s(num: BigUint) -> u32 {
    
25.     num
    
26.         .to_string()
    
27.         .bytes()
    
28.         .map(|x| (x - 48) as u32)
    
29.         .sum()
    
30. }
    

复制代码

cost 4ms.
972