问题
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')
