问题
5位数\(16807=7^5\),也是一个5次幂数。同样地,9位数\(134217728=8^9\),也是一个9次幂数。
请问有多少个n位正整数,同时又是n次幂数?
* 传送门
分析
假设符合题目条件的数字n可以写成\(n = x^y\),而n的位数则可以用函数L表达\(L(n) = \lfloor log_{10}(n) \rfloor + 1\),那么满足条件的情况便会有\(y = L(x^y)\)。
题目要求的n是正整数,所以x不可能为0;因为0的任意次幂都是0、都不会是一个正整数。x应该从1开始搜索。同样,显然地,x=1的情况只有y=1能成立,因为y>1的时候,\(y > L(1^y) = 1\)。
先不考虑x,先来观察一下y。y到什么数字的时候应该停止搜索?
首先,y不可能等于0。因为\(L(x^0) = L(1) = 1 > 0 = y\)。
其次,以x=2为例,要找\(L(2^y)=y\),显然只有y=1能成立,当3>=y>1时,\(y > L(2^y) = 1\)。当y>3,显然y的增长速度是要比函数L的值的增长速度要快。
更严谨的说明,就是设\(z_1\)是y的导数,有\(z_1 = 1\)。设\(z_2\)是函数L对y的导数,有\(z_2 = \frac{∂}{∂_y} L(x^y) = \frac{∂}{∂_y} [\lfloor log_{10}(x^y) \rfloor + 1] = \frac{∂}{∂_y} \lfloor y \cdot log_{10}(x) \rfloor = \lfloor log_{10}(x) \rfloor\):
- 当0<x<10时,显然\(log_{10}(x) < 1, \lfloor log_{10}(x) \rfloor = 0\),即\(z_1 > z_2\);
- 当10<=x<100时,则有\(1 \leq log_{10}(x) < 2, \lfloor log_{10}(x) \rfloor = 1\),即\(z_1 = z_2\);
- 当x>=100时,则有\(log_{10}(x) \geq 2, \lfloor log_{10}(x) \rfloor \geq 2\),即\(z_1 < z_2\)。
x的这3个区间有什么意义?我们假设x>=10、y>=1,于是便有\(L(x^y) = \lfloor log_{10}(x^y) \rfloor + 1 = y \cdot \lfloor log_{10}(x) \rfloor + 1 \geq y \cdot 1 + 1 = y + 1 > y\)。也就是说,当x>=10时,y永远不可能有满足题目条件的值!
所以说,只要0<x<10,当发现\(y > L(x^y)\),便可以停止搜索幂数y。
暴力解题便显得很简单了!
答案
// brute force
const start = Date.now()
const L = (n) => Math.floor(Math.log10(n)) + 1
let result = 0
for (let x = 1; x < 10; ++x)
for (let n = x, y = 1; true; n *= x, ++y)
if (y > L(n)) // 用 n *= x 代替 n = Math.pow(x, y),速度更上一层楼
break
else
result++
alert(result + ', ' + (Date.now()-start) + 'ms')
打赏作者