The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power.
How many n-digit positive integers exist which are also an nth power?
Solution
We can use the lemma of Problem 25 here to calculate the length of a number. Since we are looking for all numbers that are \(L(n^k) = k\), we can formulate
\[ \begin{array}{rl} & k = L(n^k)\\ \Leftrightarrow & k = \lfloor 1 + \log_{10}(n^k)\rfloor\\ \Leftrightarrow & k-1 \leq k\log_{10}(n) < k\\ \Rightarrow & \log_{10}(n) < 1\\ \Leftrightarrow & n < 10 \end{array} \]
This is a pretty good finding, as it states that the only possible bases \(n\) are below 10. Now the question is, what is the biggest \(k\) for each of these \(n\)?
\[ \begin{array}{rl} & L(n^k) > k\\ \Leftrightarrow & \lfloor 1 + k\log_{10}(n^k)\rfloor > k\\ \Rightarrow & 1 + k\log_{10}(n) > k\\ \Leftrightarrow & \log_{10}(n) > \frac{k-1}{k} = 1 - \frac{1}{k}\\ \Leftrightarrow & \log_{10}(n)+ \frac{1}{k} > 1 \\ \Leftrightarrow & \frac{1}{k} > 1-\log_{10}(n) \\ \Leftrightarrow & k > \frac{1}{1-\log_{10}(n)} \\ \Rightarrow & k > \log_{\frac{10}{n}}(10) \\ \end{array} \]
It turns out that the function is monotonically nondecreasing on the given interval, so we can skip the 9 individual calculations and use only the biggest value for \(n=9\) which is \(k< 21.85\). With the constrained bounds we can formulate a pretty fast brute-force algorithm:
function solution() {
let c = 0;
for (let n = 1; n <= 9; n++)
for (let k = 1; k <= 21; k++)
if (Math.floor(1 + k * Math.log10(n)) === k)
c++;
return c;
} Another way of thinking of the problem is this. Again, from the definition of \(L\) we know that \(10^{k-1}\leq n^k<10^k\). Since \(n<10\), \(10^{k-1}\) grows faster than \(n^k\) and will eventually surpass \(n^k\). All we have to find is the point where they meet:
\[\begin{array}{rrl} &10^{k-1} &= n^k\\ \Leftrightarrow&\frac{1}{10} 10^k &= n^k\\ \Leftrightarrow&k\log(10) - \log(10) &= k\log(n)\\ \Leftrightarrow&k &= \frac{\log(10)}{\log(10) - \log(n)}\\ \Leftrightarrow&k &= \log_{\frac{10}{n}}(10) \end{array}\]
Surprisingly, we saw this expression earlier for the boundary check, but here it means the number of numbers that meet the requirement. All we still have to do is rounding down the result to get the largest integer for which the inequality holds true. A new much faster algorithm then is this:
function solution() {
let c = 0;
for (let n = 1; n <= 9; n++)
c+= Math.floor(Math.LN10 / Math.log(10 / n));
return c;
}