In the 1970 MAA High School Mathematics Contest (Problem #33), students encountered this sweeping number theory challenge:

Find the sum of the digits of all the numbers in the sequence $1, 2, 3, 4, \dots, 10000$.

If you tried adding them up by hand, it would take weeks! But with programming and a brilliant combinatorial symmetry insight, we can solve it in milliseconds.

Here is the mathematical symmetry trick:

• Consider all the numbers from $0$ to $9999$. Write each as a 4-digit number: $0000, 0001, 0002, \dots, 9999$.
• There are $10,000$ numbers, and each number has $4$ digits, giving a total of $10,000 \times 4 = 40,000$ digit positions.
• Since every decimal digit ($0, 1, 2, 3, 4, 5, 6, 7, 8, 9$) is equally likely across all positions, each digit appears exactly: $$\frac{40,000}{10} = 4,000 \text{ times}$$
• The sum of the single digits from $0$ to $9$ is: $$0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45$$
• Therefore, the sum of all digits from $0000$ to $9999$ is: $$4,000 \times 45 = 180,000$$
• Finally, we add the single extra number $10,000$, whose digits sum to $1 + 0 + 0 + 0 + 0 = 1$: $$180,000 + 1 = 180,001$$

In this lesson, we write an efficient loop using the modulo operator % 10 and integer division to extract and sum digits, verifying the formula!

Move the mouse over a dotted box for more information.

The loop runs through all 10,000 numbers in a fraction of a second, producing the exact answer $180,001$.