Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
2  
The solution threads are wrong? –  mixedmath Aug 19 '12 at 21:00
1  
I think you should specify the 10 "most significant digits" rather than the "first digits", which begs the question "which end do you start from?" –  Mark Bennet Aug 19 '12 at 21:07
    
@MarkBennet Fixed, thanks. –  Ankit Soni Aug 19 '12 at 21:25

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer

What is the sum when looking at the 11 most significant digits? How many digits does it have? What is the maximum error from cutting off the less significant digits?

Excel suggests to me that this sum has 13 digits (implicitly $\times 10^{39}$), that the least significant three of these are $342$ and the rounding error is less than $100$ ($\times 10^{39}$). So the method works here, though as you say it might not always work.

share|improve this answer
    
I don't understand what you mean by rounding error here. Does Excel do rounding? Isn't it using floating-point, which could be inappropriate for this sort of sum? –  Ben Millwood Aug 19 '12 at 21:39
    
@Ben: If you take the first 11 digits than the maximum rounding error for each term is $10^{39}$ so the maximum total rounding error is $100\times 10^{39}=10^{41}$ in a total which is about $5 \times 10^{51}$. Excel does about 15 significant figures of floating point which should be enough for this. –  Henry Aug 19 '12 at 23:05

I think you have proven that that specific comment in the solution thread is inaccurate.

In general, we can take something like $10^n - 1$ and add either $10^n$ or $10^n + 1$ to show that without looking at the digits themselves, we can't tell how many will be necessary to determine even the first digit of the result. However, the problem here is just that $10^n - 1$ contains lots of $9$s – lots of potential carries. What is true is that if your numbers have a corresponding pair of digits adding up to less than $9$, no carry is possible and hence you can potentially ignore beyond that point. In binary arithmetic, particularly, it is often easy to tell where carries might or might not happen, and this information can be used to parallelise addition, or solve problems like yours.

I would think that in this case the sort of analysis you'd need is significantly more complicated than just doing it the obvious way, and in the worst case the analysis would provide no insights anyway.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.