063. 幂的位数(Powerful digit counts)

五位数\(16807=7^5\)也是一个五次幂,同样的,九位数\(134217728=8^9\)也是一个九次幂。求有多少个\(n\)位正整数同时也是\(n\)次幂?

分析:设题目要求的幂的底为\(n\),指数为\(k\),则这个幂应为\(k\)位数,则有:

$$ 10^{k-1}<n^k<10^k \Rightarrow k-1<k\cdot log_{10}n<k $$

因为\(k\ge1\),则对于不等式\(k\cdot log_{10}n<k\),有\(log_{10}n<1\Rightarrow n<10\)。对于另一边有:

$$ k-1<k\cdot log_{10}n\Rightarrow k<\frac{1}{1-log_{10}n} $$

则我们有\(1\le n<10,1\le k < 1/(1-log_{10}n)\)。因此我产只需要遍历所有符合条件的\(n\),统计在特定的\(n\)时有多少个符合条件的\(k\)并加总,即为题目所求。

# time cost = 2.8 µs ± 29.8 ns

from math import log10

def main():
    c = 0
    for n in range(1,10):
        c += int(1/(1-log10(n)))
    return c