欧拉计划 发表于 2015-8-7 22:03:07

题目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 次方？

迷雾少年 发表于 2016-8-31 15:59:13

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

迷雾少年 发表于 2016-8-31 15:59:34

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

QingXin 发表于 2016-9-16 00:38:29

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

num=0
for k in range(1,10):
    temp = 1/(1-math.log10(k))
    num+=int(temp)
print(num)

jerryxjr1220 发表于 2016-10-14 16:15:53

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

楼上分析得很到位！{:5_106:}
根据n<1/(1-log10(9)), 得到n需小于21.8
=> 49
count = 0
for n in range(1,22):
        for k in range(1,10):
                if len(str(k**n)) == n:
                        count += 1
print (count)

愤怒的大头菇 发表于 2016-11-24 10:26:36

count = 0
for i in range(1,100):
    for j in range(1,100):
      if len(str(i**j))==j:
            count +=1
print(count)
结果：49

芒果加黄桃 发表于 2017-1-20 16:38:07

# encoding:utf-8
# 一个n位数同时是一个数的n次方
from time import time
def euler063():
    count = 0
    for t in range(1,10):
      for n in range(1,100):
            tmp = t**n
            if len(str(tmp)) == n:
                #print(t,n,tmp)
                count += 1
            else:
                break
    print(count)
if __name__ == '__main__':
    start = time()
    euler063()
    print('cost %.6f sec' % (time() - start))

49
cost 0.000000 sec

渡风 发表于 2017-6-18 10:20:10

此代码使用matlab编程
Problem63所用时间为： 0.27143秒
Problem63的答案为： 49
%% Problem63.m
% 最后编辑时间：17-06-17 23:35
% 问题：有多少n位的正整数，也是某位数的n次方
% 分析：底数小于10，指数小于22
% Problem63所用时间为： 0.27143秒
% Problem63的答案为： 49

function Output = Problem63()
tic
Total = 0;
for bb = 1:22
    for aa = 1:9
      if length(char(vpa(aa^bb))) - 2 == bb %去掉***.0的.0
            Total = Total + 1;
      end
    end
end

Output = Total;
                                    
toc
disp('此代码使用matlab编程')
disp(['Problem63所用时间为： ',num2str(toc),'秒'])
disp(['Problem63的答案为： ',num2str(Output)])
end

王小召 发表于 2019-6-28 12:57:14

本帖最后由 王小召 于 2019-6-28 12:58 编辑

共有：49 个
用时：0.2184014 秒
## 因为10**n 次方是n+1位，所以当底数大于10的时候无需继续进行下去（所以y 上限设为9即可）
import time


def cal():
    result = []
    for x in range(1, 1000):
      for y in range(1, 10):
            if len(str(y**x)) == x:
                result.append("{}(长度：{}) = {}^{}次方".format(y**x, len(str(y**x)), y, x))
    return result
result = cal()
print("共有：{} 个\n用时：{} 秒".format(len(result), time.process_time()))
# print(result)

debuggerzh 发表于 2020-8-21 08:57:40

49

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

int main(){
int cnt = 0;

for (int x = 1;x <= 9;x++){
    for (int n = 1;n <= 21;n++){
      if (n == (int)(n*log10(x) + 1)) cnt++;
    }
}
cout << cnt << endl;
return 0;
}

永恒的蓝色梦想 发表于 2021-2-6 12:00:37

直接把4#代码改编成C++#include<iostream>
#include<cmath>



int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    unsigned short n, count = 0;


    for (n = 1; n < 10; n++) {
      count += 1 / (1 - log10(n));
    }


    cout << count << endl;
    return 0;
}

B1tetheDust 发表于 2022-10-29 18:08:23

import time as t
import numpy as np

start = t.perf_counter()
upper_limit = int(1 / (1 - np.log10(9))) + 1
count = 0
for n in range(1, upper_limit):
    for num in range(1, 10):
      if len(str(num ** n)) == n:
            count += 1

print(count)
print("It costs %f s" % (t.perf_counter() - start))



49
It costs 0.000116 s
页: [1]
查看完整版本: 题目63：有多少n位正整数同时也是一个数的n次方？