Number theory approach to Project Euler’s “Large Sum” problem

decimal-expansionelementary-number-theorynumber theorysummation

I am refreshing some of my skills by solving problems on the Project Euler site. It is a repository of problems that usually require some mathematics knowledge and programming knowledge to solve efficiently. Here is problem 13:

https://projecteuler.net/problem=13

The idea of this problem is you are given a collection of large numbers and asked to find the first (i.e. from the left) 10 digits of the sum of these numbers. Because Python handles large integers nicely, all that is required for a simple programming solution is to define a list L containing these numbers and then call str(sum(L))[:10] to obtain a string of these digits. But that doesn't involve much mathematical knowledge at all and is uninteresting as a programming problem since modern computers can easily handle numbers of this size. The problem becomes more interesting to me if we include the constraint of not being allowed to compute the entire digit expansion, only what is necessary to compute those left-most 10 digits. Perhaps this cannot be done in general, but I am sure that it can sometimes be done (e.g. sum of powers of 10).

Is there a more elegant (and maybe computationally efficient) way to find the first 10 digits of a sum of large counting numbers?

Best Answer

The idea, as Greg Martin says in the comments, is that you can ignore most of the digits and compute using only the first $10 + k$ digits for some $k$. Since we consider a sum of $100$ numbers, the sum of the errors if we discard all of the digits after the first $10 + k$ is less than $100 \times 10^{40-k}$, so if we pick $k = 2$ the sum of the errors is less than $10^{40}$ and so does not affect the first $10$ digits. So, as Greg says, it suffices to keep the first $12$ digits of each number. This is true regardless of how long they are, the important thing is that we are only summing $100$ numbers. If we were summing $1000$ numbers we'd need to keep the first $13$ digits, etc.