Detailed mathematical approach

Problem Summary

We want to count all pairs \((b,n)\) for which \(b^n\) is an \(n\)-digit positive integer. In decimal language, the number of digits of the power must match the exponent itself.

The search is much smaller than it first appears. No base \(b \ge 10\) can work, and for each fixed base \(b \in \{1,\dots,9\}\) the valid exponents form a short initial interval. Summing those intervals gives the final total \(49\).

Mathematical Approach

Let \(d(x)\) denote the number of decimal digits of a positive integer \(x\). The problem asks for the number of pairs \((b,n)\) with \(d(b^n)=n\).

Only bases 1 through 9 can contribute

If \(b \ge 10\), then \(b^n \ge 10^n\). Any number at least \(10^n\) has at least \(n+1\) digits, so it cannot be an \(n\)-digit number. Therefore every valid pair must satisfy

$1 \le b \le 9.$

This is the first decisive simplification: instead of infinitely many bases, there are only nine candidates.

Converting digit length into inequalities

For every positive integer \(x\),

$d(x)=\lfloor \log_{10} x \rfloor + 1,$

which is equivalent to

$10^{d(x)-1} \le x \lt 10^{d(x)}.$

So \(b^n\) has exactly \(n\) digits if and only if

$10^{n-1} \le b^n \lt 10^n.$

Taking base-10 logarithms gives

$n-1 \le n\log_{10} b \lt n.$

Because \(b \le 9\), we already know \(\log_{10} b \lt 1\), so the right-hand inequality is automatic. The real condition is the left-hand side:

$n-1 \le n\log_{10} b.$

Counting valid exponents for a fixed base

Rearranging the inequality above yields

$n(1-\log_{10} b) \le 1,$

hence

$n \le \frac{1}{1-\log_{10} b}.$

Therefore, for a fixed base \(b\), the valid exponents are exactly

$1 \le n \le \left\lfloor \frac{1}{1-\log_{10} b} \right\rfloor.$

This shows that each base contributes a finite number of powers. It also explains the recurrence used by the implementation: if we define

$a_0=1,\qquad a_{n+1}=b\,a_n,$

then \(a_n=b^n\) for every \(n\), so repeated multiplication walks through all candidate powers of that base in order.

The counts by base are

$1,1,1,2,3,4,6,10,21 \quad \text{for } b=1,2,3,4,5,6,7,8,9,$

and their sum is

$1+1+1+2+3+4+6+10+21=49.$

The equivalent exponent-first viewpoint

We can also fix \(n\) first. From \(10^{n-1} \le b^n\) we obtain

$10^{(n-1)/n} \le b,$

so the valid bases are

$b \in \left\{\left\lceil 10^{(n-1)/n} \right\rceil,\left\lceil 10^{(n-1)/n} \right\rceil+1,\dots,9\right\}.$

Hence the number of valid bases for exponent \(n\) is

$10-\left\lceil 10^{(n-1)/n} \right\rceil,$

provided that the lower bound does not exceed \(9\). The largest possible exponent comes from the largest base \(9\):

$n \le \left\lfloor \frac{1}{1-\log_{10} 9} \right\rfloor = 21.$

So \(9^{21}\) is the last successful boundary case, while \(9^{22}\) already falls short: it has only 21 digits, not 22.

Worked examples

For \(n=5\), the lower bound is \(10^{4/5} \approx 6.31\). The admissible integer bases are \(7,8,9\), and indeed

$7^5=16807,\qquad 8^5=32768,\qquad 9^5=59049,$

all of which have five digits.

For base \(7\), the fixed-base formula gives

$\left\lfloor \frac{1}{1-\log_{10} 7} \right\rfloor = 6.$

That means \(7^1\) through \(7^6\) qualify, but \(7^7=823543\) has only six digits, so the run stops permanently there. The same boundary logic at the top end says that base \(9\) contributes exactly 21 valid powers.

How the Code Works

Enumerating candidate bases

The C++, Python, and Java implementations loop over bases \(1\) through \(9\). That range is complete because the mathematical argument above rules out every larger base before any computation starts.

Maintaining exact powers by recurrence

For one chosen base, the implementation starts from \(1\) and multiplies by the base once per iteration. After the \(n\)-th multiplication, the current value is exactly \(b^n\). Converting that integer to decimal text gives the exact digit count, so there is no floating-point rounding risk near the boundary cases.

This is why the C++ and Java versions use arbitrary-precision integers, while Python relies on its built-in unbounded integer arithmetic.

Counting and stopping at the right moment

Whenever the current digit count equals the current exponent, the total answer increases by one. As soon as the digit count becomes smaller than the exponent, the inner loop stops for that base. The proof above shows that this is safe: valid exponents for a fixed base form an initial segment \(1,2,\dots,k\), so after the first failure there can never be another success for the same base.

The implementations also include a checkpoint based on \(9^{21}\). That value has 21 digits, so it verifies the final successful boundary before the search necessarily dies out.

Complexity Analysis

There are only 9 outer iterations, one for each possible base. The inner loop for a base stops immediately after the first exponent that fails, and the global search ends by exponent 22. Therefore the total running time is \(O(1)\) for this problem.

Space usage is also \(O(1)\) aside from the current big integer being multiplied. Even that object stays tiny here: the relevant boundary value \(9^{21}\) has only 21 decimal digits.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=63
2. Common logarithm: Wikipedia - Common logarithm
3. Exponentiation: Wikipedia - Exponentiation
4. Positional notation: Wikipedia - Positional notation
5. Arbitrary-precision arithmetic: Wikipedia - Arbitrary-precision arithmetic