notes.html

problem 63 · 21 lines

<article>
<h3>Problem Analysis</h3>
<p>
I want to count every positive integer x that has exactly n digits and is simultaneously the n-th power of some integer base b. The first thing to pin down precisely is what "exactly n digits" means: an integer x has n digits when it lies in the half-open interval from 10^(n-1) up to 10^n - 1. So the entire problem reduces to counting the pairs (b, n) for which b^n falls inside that interval. The unlocking observation is that the base b is mathematically forced to be a single digit, that is, 1 through 9. The reasoning is short and decisive: if b is 10 or larger then b^n is at least 10^n, which already has n+1 digits, so it can never be an n-digit number. This single fact collapses the base axis of the search from infinite to exactly nine candidates per value of n.
</p>
<p>
The second observation bounds the exponent n. The number of decimal digits of a positive integer x is floor(<a class="reference-source" href="https://en.wikipedia.org/wiki/Common_logarithm" rel="noopener noreferrer" target="_blank">log10</a>(x)) + 1. Applied to b^n this gives floor(n * log10(b)) + 1 digits. For every base b below 10 we have log10(b) &lt; 1, so the digit count grows strictly more slowly than n itself - it is sublinear in n. That means for each fixed base there is a largest n beyond which b^n has fewer than n digits and can never qualify again. The last base to drop out is b = 9, which stops producing n-digit n-th powers near n = 21. Because the whole search is bounded by roughly 9 * 21 candidate pairs - a fixed constant independent of any input - the algorithm runs in <a class="reference-source" href="https://en.wikipedia.org/wiki/Big_O_notation" rel="noopener noreferrer" target="_blank">O(1)</a> time. All the intellectual work is in establishing the bounds; once they are in hand, the implementation is almost mechanical, and the answer is 49.
</p>
<h3>Solution Approach</h3>
<h4>Upward range scan with digit-count verification (Python and C)</h4>
<p>
Both of my solutions share the same skeleton. An outer loop walks n upward starting from 1, and for each n it counts how many single-digit bases produce an n-digit n-th power. The loop stops the instant a value of n yields zero qualifying bases, because the sublinear digit-growth argument guarantees that no larger n can ever succeed again. The two implementations differ only in how each candidate is tested, which is dictated by the arithmetic each language offers.
</p>
<p>
The Python version narrows the bases analytically instead of testing all nine blindly. I invert the digit formula to get a lower bound, <code>start_range = ceil((10^(n-1))^(1/n))</code>, and an upper bound, <code>stop_range = ceil((10^n - 1)^(1/n)) + 1</code>. For each integer base in that interval I compute <code>i**n</code> exactly using Python's <a class="reference-source" href="https://docs.python.org/3/library/stdtypes.html#numeric-types-int-float-complex" rel="noopener noreferrer" target="_blank">arbitrary-precision integers</a>, then confirm the digit count with <code>len(str(r)) == n</code>. The crucial discipline here is that the floating-point bounds are used only to shrink the candidate set, never to make the final ruling. Because Python integers never overflow, the exact string-length check is always reliable even when floating-point inversion is slightly off at the edges.
</p>
<p>
The C version cannot lean on unbounded integers, so I built a two-stage filter. First a cheap primary screen via log10: I compute <code>floor(n * log10(b)) + 1</code> and check whether it equals n, treating b = 1 specially since 1^n always has exactly one digit. If the screen passes, I confirm with exact integer arithmetic through <code>ipow</code>, which returns -1 if the product would overflow a <code>long long</code>. When the exact value is available, <code>ll_digit_count</code> verifies the digit total; when overflow is signalled, I trust the log10 estimate. That fallback is safe here because an overflowing power of a single-digit base would have far more than 21 digits and could never match a plausible n. Both routes converge on the same correct count of 49.
</p>
</article>