Problem 16 — Power Digit Sum

Problem Analysis

The task is to compute 2 raised to the 1000th power and sum the decimal digits of the result. The mathematical content is modest, but the implementation challenge is real: 2^1000 has roughly ceil(1000 * log10(2)) = 302 decimal digits. That figure comes from the observation that the number of base-10 digits of a positive integer n is floor(log10(n)) + 1, and log10(2^1000) = 1000 * log10(2). A 302-digit number dwarfs the capacity of any native integer type in C, where even a 64-bit unsigned long long tops out near 19 decimal digits. We therefore need arbitrary-precision arithmetic - the ability to represent and manipulate integers whose size is bounded only by available memory.

The key observation that makes the problem tractable is that we only ever need the decimal representation of the result, never its binary form. If we maintain the number as an array of base-10 digits throughout the computation, then extracting the digit sum at the end is a trivial linear pass. The natural algorithm is repeated multiplication: start at 1 and multiply by the base power times. Each multiplication is a schoolbook (long) multiplication that walks across all current digits once, propagating a carry. With P multiplications over a result of up to D digits (and D ~ 0.301 * P), the total cost is O(P * D) = O(P^2). For P = 1000 that is about 300,000 digit operations - instantaneous on modern hardware.

Solution Approach

Algorithm 0 - Repeated decimal multiplication (C and Python)

Both files implement the same logical algorithm - compute base^power as an arbitrary-precision integer, then sum its decimal digits - and differ only in how they realize that big integer.

Python version. Python integers carry arbitrary-precision arithmetic built into the language, so I delegate the entire big-number problem to the runtime with the single expression base**power. That one operator produces the full 302-digit value. I then convert it to a string with str(...), iterate over each character, convert each digit back to an integer with int(i), and feed the stream into sum(...). The whole solve body is one line: sum((int(i) for i in str(base**power))). This is correct, idiomatic, and concise; the cost is that I cede control of the internal representation to the interpreter, which here is entirely acceptable.

C version. C has no native arbitrary-precision arithmetic, so I built one by hand as an array of unsigned char, each element holding a single decimal digit (0-9), with the least-significant digit at index 0 - a little-endian layout. The steps:

• Allocate. I compute an upper bound on the digit count as (int)(power * 0.30103 + 10) + 10, where 0.30103 approximates log10(2), and call calloc to obtain a zero-initialized array. The size formula and the safety margin guarantee no reallocation is ever needed.
• Initialize. I set digits[0] = 1 and len = 1, representing the value 1.
• Multiply. I loop power times, each iteration a schoolbook (long) multiplication by the base: I walk positions j = 0..len-1, computing val = digits[j] * base + carry, storing val % 10 back, and carrying val / 10 forward. After the digits are exhausted, any remaining carry is appended as new high-order digits via digits[len++] = carry % 10 until the carry is consumed.
• Sum. A final linear pass accumulates all digits into a long long.

The crucial design decision is the little-endian digit order. Because carry propagates from the least-significant position upward - the same direction as the loop - the array grows naturally at its high end with a simple append. A big-endian layout would force either backward iteration or a final reversal, adding complexity for no benefit.