Euler Problem 13

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
(and so on…)

To a ruby programmer, this problem looks trivial; just calculate the sum as requested:

s = <em>&lt;big string of numbers&gt;</em>
a = s.split(' ').map{ |line| line.to_i }
sum = a.reduce(:+)
digits = sum.to_s.slice(0..9)
puts digits

This hides the meat of the problem of course, by relying on ruby’s built-in handling of large numbers. In a language like C, the largest base type is the long long: 64bits. The largest number we can represent in 64 bits is only 20 digits, so adding a list of 50 digit numbers requires some trickery behind the scenes.

Addition can be broken up into smaller chunks though: we could add the lowest 10 digits of each number together to get the lowest 10 digits of the number plus a carry, then add the next group of 10 digits to the carry to get the next 10 digits in the result plus a carry and so on until we compute the entire sum.

But since the question only asks for the leading 10 digits, we can cheat a little. In a sum of 100 numbers the largest carry we can have from any one digit is 9*100/10 ie. a 9 two columns away. And the total result must grow by at least 2 digits (think of adding 100 ones together). So at worst we expect one digit of carry from the lower digits of the sum. So if we just sum the first 11 digits, we’ll likely get the same leading 10 digits in the result! (The carry *could* propagate all the way up the leading digits, so this is only an estimate of the final result, but it will cover most cases just fine!)

In ruby this estimate saves about half the computation time too:

a = s.split(' ').map{ |line| line.slice(0..10).to_i }
sum = a.reduce(:+)
puts sum
digits = sum.to_s.slice(0..9)
puts digits
end

About this entry