[Math] 10 most significant digits of the sum of a 100 50-digit numbers

arithmeticproject euler

This is about Project Euler #13. You are given a 100 50-digit numbers and are asked to calculate the 10 most significant digits of the sum of the numbers.

The solution threads stated that we are only required to sum, the 11 most significant digits of each number to obtain the answer. Why is this?

Heres a counterexample to that with fewer digits.

Consider a small example, 2 numbers, and we have to find the 4 most significant digits of the sum.

123446

234556

If we consider only the 5 most significant digits, we get 12344+23455 = 35799 => first 4 = 3579

But if we take all 6, we get 123446+234556 = 358002 => first 4 = 3580

So why would summing only the 11 most significant digits of each number yield the correct answer?

(I have tagged this with modular arithmetic as I suspect its related to that, feel free to correct the tags if not)

Best Answer

It is not guaranteed that summing the 11 most significant digits will work, but it is very likely. When you sum the sets 11 digits you get a 13 digit number and throw away the lower two digits. If you round, each of the 100 numbers has an error of at most 0.5 and they should be equally distributed up and down. The standard deviation is about 5, which would have to impact the hundreds digit of your sum to make a problem. This will only happen $5\%$ of the time. If you keep the top 12 digits the error chance goes down to $0.5\%$. In the Project Euler setting, you can just do the addition this way, and if you are wrong try going up or down one, and be very likely to be right.