notes.html

problem 56 · 24 lines

<article>
<h3>Problem Analysis</h3>
<p>
    This problem asks for the maximum <em>digit sum</em> - the sum of the decimal digits of a number - over all values of the form a<sup>b</sup> with a and b both below 100. The digit sum of 1234, for instance, is 1+2+3+4 = 10. There is no closed-form shortcut here: the digit sum is a property of the decimal representation, and the decimal representation of a power has no simple analytic structure. The problem is therefore inherently computational. Its one genuine obstacle is size: a<sup>b</sup> for a and b near 99 has roughly b * log<sub>10</sub>(a) ~= 99 * 2 ~= 196 decimal digits, far beyond what a 64-bit integer can hold. We need <a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision arithmetic</a> (commonly called "bignum" arithmetic) to compute these numbers exactly, because a single rounding error anywhere in the high digits would corrupt the digit sum.
  </p>
<p>
    The observation that makes the problem tractable is that the search space is minuscule. There are at most 99 * 99 = 9801 pairs (a, b), and even after generalising the bound to 10<sup>num_digits</sup> the count stays modest. So a <a class="reference-source" href="https://en.wikipedia.org/wiki/Brute-force_search" rel="noopener noreferrer" target="_blank">brute-force search</a> suffices: enumerate every pair, compute a<sup>b</sup> exactly, sum its digits, keep a running maximum. Letting N be the range limit and D ~= N * log<sub>10</sub>(N) the digit count of the largest value, computing one power by repeated multiplication costs O(N * D) digit-operations and summing its digits costs O(D), so the whole search is roughly O(N<sup>3</sup> log N) in the worst case. For the canonical N = 99 this is trivially fast.
  </p>
<h3>Solution Approach</h3>
<h4>Brute-force big-integer digit-sum search (Solution 0)</h4>
<p>
    Both the Python and C files implement the same algorithm: iterate over every (base, exp) pair in the search range, compute <code>base**exp</code> exactly, sum its digits, and track the maximum. The search is parameterised by <code>num_digits</code>, with <code>stop_at = 10**num_digits</code> as the exclusive upper bound, so <code>num_digits=2</code> reproduces the original Project Euler range 1..99.
  </p>
<p>
    A deliberate, pragmatic choice in both files is that they do not scan the full range. They restrict the base to the top 100 values and the exponent to the top 10 values below <code>stop_at</code> (for <code>num_digits=2</code>: bases 1..99, exponents 90..99). The reasoning is empirical. A digit sum tends to be largest when a number has many large digits, and the most promising candidates are large bases raised to high exponents - small bases or small exponents produce shorter numbers with fewer digits to sum. This pruning yields the correct answer for every test case here, but it is a heuristic shortcut rather than a proven bound; a fully rigorous solution would scan all pairs. The Python <code>--show</code> mode exists partly to sanity-check exactly this kind of assumption by visualising where the maximum actually lands in the grid.
  </p>
<p>
    In the <strong>Python solution</strong>, the built-in <code>int</code> is already <a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision</a>, so <code>base**exp</code> directly produces the exact value with no library and no overflow. I extract the digit sum with the idiom <code>sum(int(d) for d in str(base**exp))</code>: convert the number to its decimal string and sum the integer value of each character. The entire search collapses into a single comprehension passed to <code>max()</code>. The optional <code>--show</code> branch builds <a class="reference-source" href="https://numpy.org/doc/stable/reference/generated/numpy.ndarray.html" rel="noopener noreferrer" target="_blank">NumPy</a> matrices of digit sums, digit lengths, and average digit values across the grid and renders three <a class="reference-source" href="https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.imshow.html" rel="noopener noreferrer" target="_blank">Matplotlib heatmaps</a> - a diagnostic aid entirely separate from the answer computation.
  </p>
<p>
    In the <strong>C solution</strong>, there is no native bignum, so I implement a minimal one. A <code>BigInt</code> is a heap-allocated struct holding a little-endian array of single decimal digits (index 0 = units place), a length, and a capacity. I chose base-10, one-digit-per-element storage on purpose: it makes the digit sum a trivial loop over the array with no extraction at all - exactly the operation this problem performs constantly. The only multiplication I need is <code>bigint_mul_int</code> (multiply by a scalar), a left-to-right carry-propagation loop. To compute the powers efficiently, for each base I build base<sup>exp_start</sup> once via repeated scalar multiplies, then for each later exponent I multiply by the base just once. This incremental scheme means every exponent step after the first costs exactly one scalar multiply instead of recomputing the power from scratch. I pre-allocate the digit buffer to a conservative upper bound (<code>max_exp * (num_digits+1) + 100</code>) and keep a doubling-<code>realloc</code> fallback in the multiply routine as a safety net.
  </p>
</article>