Detailed mathematical approach

Problem Summary

Problem 13 gives one hundred 50-digit integers and asks for the first 10 digits of their total sum.

With \(S=\sum_{i=1}^{100} N_i\), the goal is to determine \(\operatorname{pref}_{10}(S)\).

Mathematical Approach

The arithmetic is elementary, but the scale matters: the input is far beyond ordinary 64-bit integers. The real structure of the problem comes from decimal place value, carry propagation, and the fact that only a short leading prefix of the full sum is needed.

The sum is forced into 52 digits

Every addend has 50 decimal digits, so

$10^{49} \le N_i \lt 10^{50}.$

Summing 100 such numbers gives

$10^{51} \le S \lt 10^{52}.$

Therefore the total has exactly 52 digits. The requested answer is the leading 10-digit prefix of a 52-digit integer.

Column addition gives an exact recurrence

Write each number in base 10 as

$N_i = \sum_{j=0}^{49} d_{i,j}10^j,\qquad 0\le d_{i,j}\le 9,$

where \(j=0\) is the units column. Exact schoolbook addition processes columns from right to left. If \(c_j\) is the carry entering column \(j\), then

$u_j = c_j + \sum_{i=1}^{100} d_{i,j},\qquad r_j = u_j \bmod 10,\qquad c_{j+1} = \left\lfloor \frac{u_j}{10} \right\rfloor,$

with \(c_0=0\).

The key invariant after finishing columns \(0,1,\dots,p-1\) is

$\sum_{i=1}^{100}\sum_{j=0}^{p-1} d_{i,j}10^j = \sum_{j=0}^{p-1} r_j10^j + c_p10^p.$

So the digits already written are exactly the low \(p\) digits of the processed part of the sum, and the carry stores everything that still has to move into higher positions. This is precisely the correctness argument behind the manual digit-by-digit algorithm.

The carry stays small even though the sum is huge

The same recurrence shows why the carry itself fits comfortably into an ordinary small integer. If \(0\le c_j\le 99\), then

$u_j \le 99 + 100\cdot 9 = 999,$

so

$0 \le c_{j+1} = \left\lfloor \frac{u_j}{10}\right\rfloor \le 99.$

Since \(c_0=0\), induction gives \(0\le c_j\le 99\) for every column. The full total needs 52 digits, but the per-column state remains tiny.

Worked example: why 13 leading digits already determine the answer

The implementations compute the exact sum, but Problem 13 also admits a clean guard-digit proof. We need 10 leading digits, and there are 100 summands, so any carry coming from discarded tails has at most two decimal digits. One extra safety digit is enough, giving

$10 + \lceil \log_{10} 100 \rceil + 1 = 13.$

Split each addend into a 13-digit prefix and a 37-digit tail,

$N_i = 10^{37}A_i + B_i,$

where \(A_i\) is the first 13 digits and \(0\le B_i \lt 10^{37}\). Then

$S = 10^{37}\sum_{i=1}^{100} A_i + \sum_{i=1}^{100} B_i.$

The tail block satisfies

$0 \le \sum_{i=1}^{100} B_i \lt 100\cdot 10^{37} = 10^{39},$

so the carry from the tail into the prefix block is at most 99. Therefore only the last two digits of \(\sum A_i\) can change, and the first 10 digits are already fixed by those 13-digit prefixes. This explains, rigorously and specifically for this dataset, why a prefix-only method also works.

How the Code Works

The C++, Python, and Java implementations all compute the same exact quantity. They differ only in how the growing sum is represented.

The C++ implementation keeps the input as decimal strings, scans from the least significant column to the most significant one, adds the 100 digits in the current column together with the incoming carry, emits the new result digit, and updates the carry. Those produced digits are collected in reverse order and reversed once at the end, which yields the full decimal expansion of \(S\); the first 10 characters are then returned.

The Python and Java implementations rely on arbitrary-precision integers provided by the language runtime. Each 50-digit line is parsed as an exact integer, all 100 values are summed, the final total is converted back to decimal text, and the first 10 digits are sliced off. Mathematically this is the same sum as in C++, just performed by a built-in big-integer type instead of manual column logic.

Complexity Analysis

If there are \(m\) numbers of \(d\) digits each, exact column addition takes \(O(md)\) time. For Problem 13, \(m=100\) and \(d=50\), so the total work is only a few thousand digit operations. The big-integer implementations have the same effective scale because they still process every input digit and every digit of the final sum.

Keeping the input in memory costs \(O(md)\) space. Beyond the input itself, the manual exact addition needs \(O(d)\) extra space for the output digits and the carry, while the arbitrary-precision versions need \(O(d)\) space for the running total. A prefix-truncation strategy would reduce the working digit count to \(O(k+\log m)\), but the provided implementations do not need that optimization.

Footnotes and References

1. Problem page: Project Euler Problem 13
2. Arbitrary-precision arithmetic: Wikipedia - Arbitrary-precision arithmetic
3. Addition and carrying: Wikipedia - Addition
4. Decimal positional notation: Wikipedia - Positional notation