题目63：有多少n位正整数同时也是一个数的n次方？

欧拉计划

Powerful digit counts

The 5-digit number, , is also a fifth power. Similarly, the 9-digit number, , is a ninth power.

How many n-digit positive integers exist which are also an nth power?

题目：

五位数 同时也是一个数的五次方。类似的，九位数 ,同时也是一个数的九次方。

有多少 n 位正整数同时也是某个数的 n 次方？

迷雾少年

4 的2-2次方相等
5 的2-3次方相等
6 的2-4次方相等
7 的2-6次方相等
8 的2-10次方相等
9 的2-21次方相等

迷雾少年

用大数算的 比较简单 不过不知道答案对没

QingXin

这里，可以先数学分析一下：
如果使得某个数k的n次方是一个n位数，k显然必须小于10，且k^n>10^(n-1)
后面的不等式在取对数后，最终可化为
n<1/(1-log10(k)),当然，这里n是允许等于1的（即5的1次方是1位数，这是计数在内的）。
顺着这个思路，后面就很好写代码了。
将所有1次方计数在内，共49个。

1. import math
   
2. 
   
3. num=0
   
4. for k in range(1,10):
   
5.     temp = 1/(1-math.log10(k))
   
6.     num+=int(temp)
   
7. print(num)

复制代码

jerryxjr1220

QingXin 发表于 2016-9-16 00:38
这里，可以先数学分析一下：
如果使得某个数k的n次方是一个n位数，k显然必须小于10，且k^n>10^(n-1)
后面 ...

楼上分析得很到位！
根据n<1/(1-log10(9)), 得到n需小于21.8
=> 49

1. count = 0
   
2. for n in range(1,22):
   
3.         for k in range(1,10):
   
4.                 if len(str(k**n)) == n:
   
5.                         count += 1
   
6. print (count)

复制代码

愤怒的大头菇

1. count = 0
   
2. for i in range(1,100):
   
3.     for j in range(1,100):
   
4.         if len(str(i**j))==j:
   
5.             count +=1
   
6. print(count)

复制代码

结果：49

芒果加黄桃

1. # encoding:utf-8
   
2. # 一个n位数同时是一个数的n次方
   
3. from time import time
   
4. def euler063():
   
5.     count = 0
   
6.     for t in range(1,10):
   
7.         for n in range(1,100):
   
8.             tmp = t**n
   
9.             if len(str(tmp)) == n:
   
10.                 #print(t,n,tmp)
    
11.                 count += 1
    
12.             else:
    
13.                 break
    
14.     print(count)
    
15. if __name__ == '__main__':
    
16.     start = time()
    
17.     euler063()
    
18.     print('cost %.6f sec' % (time() - start))
    

复制代码

49
cost 0.000000 sec

渡风

此代码使用matlab编程
Problem63所用时间为： 0.27143秒
Problem63的答案为： 49

1. %% Problem63.m
   
2. % 最后编辑时间：17-06-17 23:35
   
3. % 问题：有多少n位的正整数，也是某位数的n次方
   
4. % 分析：底数小于10，指数小于22
   
5. % Problem63所用时间为： 0.27143秒
   
6. % Problem63的答案为： 49
   
7. 
   
8. function Output = Problem63()
   
9. tic
   
10. Total = 0;
    
11. for bb = 1:22
    
12.     for aa = 1:9
    
13.         if length(char(vpa(aa^bb))) - 2 == bb %去掉***.0的.0
    
14.             Total = Total + 1;
    
15.         end
    
16.     end
    
17. end
    
18. 
    
19. Output = Total;
    
20.                                     
    
21. toc
    
22. disp('此代码使用matlab编程')
    
23. disp(['Problem63所用时间为： ',num2str(toc),'秒'])
    
24. disp(['Problem63的答案为： ',num2str(Output)])
    
25. end

复制代码

王小召

共有：49 个
用时：0.2184014 秒

1. ## 因为10**n 次方是n+1位，所以当底数大于10的时候无需继续进行下去（所以y 上限设为9即可）
   
2. import time
   
3. 
   
4. 
   
5. def cal():
   
6.     result = []
   
7.     for x in range(1, 1000):
   
8.         for y in range(1, 10):
   
9.             if len(str(y**x)) == x:
   
10.                 result.append("{}(长度：{}) = {}^{}次方".format(y**x, len(str(y**x)), y, x))
    
11.     return result
    
12. result = cal()
    
13. print("共有：{} 个\n用时：{} 秒".format(len(result), time.process_time()))
    
14. # print(result)

复制代码

debuggerzh

49

Process returned 0 (0x0)   execution time : 0.025 s
Press any key to continue.
本楼其他大大说的已经很清楚，这里提供c++实现供参考
同时若数据范围较大，可预先计算上限从而进一步优化

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. 
   
5. int main(){
   
6.   int cnt = 0;
   
7. 
   
8.   for (int x = 1;x <= 9;x++){
   
9.     for (int n = 1;n <= 21;n++){
   
10.       if (n == (int)(n*log10(x) + 1)) cnt++;
    
11.     }
    
12.   }
    
13.   cout << cnt << endl;
    
14.   return 0;
    
15. }
    

复制代码

永恒的蓝色梦想

直接把4#代码改编成C++

1. #include<iostream>
   
2. #include<cmath>
   
3. 
   
4. 
   
5. 
   
6. int main() {
   
7.     using namespace std;
   
8.     ios::sync_with_stdio(false);
   
9. 
   
10.     unsigned short n, count = 0;
    
11. 
    
12. 
    
13.     for (n = 1; n < 10; n++) {
    
14.         count += 1 / (1 - log10(n));
    
15.     }
    
16. 
    
17. 
    
18.     cout << count << endl;
    
19.     return 0;
    
20. }

复制代码

B1tetheDust

1. import time as t
   
2. import numpy as np
   
3. 
   
4. start = t.perf_counter()
   
5. upper_limit = int(1 / (1 - np.log10(9))) + 1
   
6. count = 0
   
7. for n in range(1, upper_limit):
   
8.     for num in range(1, 10):
   
9.         if len(str(num ** n)) == n:
   
10.             count += 1
    
11. 
    
12. print(count)
    
13. print("It costs %f s" % (t.perf_counter() - start))
    

复制代码

49
It costs 0.000116 s