Euler One

I first heard of the Project Euler web site a couple of months ago, and it remains obscure among a public that isn't receptive to math problems outside of the classroom. The site has no practical reason to exist, mind you, apart from providing some curious fodder among intellectuals: Simply put, it posts math problems on a regular basis, then challenges people to solve them.

My biggest issue with the site is that most of its problems require the use of some programming know-how. While I do have the appropriate background needed for this, it doesn't feel right for me, somehow. There are any number of things that I can do with a monitor, a keyboard, a hard drive and six feet of LAN cable... it's just that solving math problems is something that I normally associate with paper and pen.

Setting that aside, one of the things I noted was that the first problem on the site could at least be solved without having to go into Java or C++:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

The problem brings up a cute story that I heard many years ago. You see, one day in the late 18th century, there was a math class being held at a primary school somewhere in Germany. There, the teacher gave his students an exercise: He asked them to write down all the numbers from 1 to 100, then add them up and give him the result.

Within seconds, one of the children stood up and gave him the correct answer — 5,050 — without having written anything on his paper. When the astonished teacher asked him how he was able to come up with the result so fast, the boy explained his method:

The problem involved adding up the numbers such that: 1 + 2 + 3 + 4 + ... + 97 + 98 + 99 + 100. However, the boy had realized that this series was basically the same as: (1+ 100) + (2 + 99) + (3 + 98) + (4 + 97) + ... and so forth — it was all just a matter of pairing them up. The result was, of course, (101) + (101) + (101) + (101) + ... and there were fifty such numbers. From there, the boy just needed to find the product of 50 and 101, which was 5,050.

The boy would grow up to become Carl Friedrich Gauss, one of the most prominent contributors to modern mathematics, and the subject of a rather nice story. But for the purpose of this blog post, I think that his method can be applied to this problem from Project Euler.

For starters, we're obviously looking for a value, X, where:

X = A + B - C

And:

A = Sum of the multiples of 3 below 1000;

B = Sum of the multiples of 5 below 1000; and

C = Sum of the multiples of 15 below 1000.

We need to subtract C from the sum of A and B because any multiples of 15 (which would be divisible by both 3 and 5) would otherwise be counted twice in our total. Equation-wise:

A = 3 + 6 + 9 + 12 + ... + 999

B = 5 + 10 + 15 + 20 + ... + 995

C = 15 + 30 + 45 + 60 + ... + 990

Due to the nature of divisibles, each of the above three equations can be rephrased as follows:

A = 3 * (1 + 2 + 3 + 4 + ... + 333)

B = 5 * (1 + 2 + 3 + 4 + ... + 199)

C = 15 * (1 + 2 + 3 + 4 + ... + 66)

Then, using the young Gauss's method on each one:

A = 3 * (1 + 2 + 3 + 4 + ... + 333)
A = 3 * [(1 + 333) + (2 + 332) + (3 + 331) + ... + (166 + 168) + (167)]
A = 3 * [(334) + (334) + (334) + ... + (334) + (167)]
A = 3 * [(166 * 334) + (167)]
A = 3 * [(55444) + (167)]
A = 3 * (55611)
A = 166833

B = 5 * (1 + 2 + 3 + 4 + ... + 199)
B = 5 * [(1 + 199) + (2 + 198) + (3 + 197) + ... + (99 + 101) + (100)]
B = 5 * [(200) + (200) + (200) + ... + (200) + (100)]
B = 5 * [(99 * 200) + (100)]
B = 5 * [(19800) + (100)]
B = 5 * (19900)
B = 99500

C = 15 * (1 + 2 + 3 + 4 + ... + 66)
C = 15 * [(1 + 66) + (2 + 65) + (3 + 64) + ... + (33 + 34)]
C = 15 * [(67) + (67) + (67) + ... + (67)]
C = 15 * [(67 * 33)]
C = 15 * (2211)
C = 33165

Therefore, the sum of all multiples of 3 or 5 below 1000 is:

X = A + B - C

X = 166833 + 99500 - 33165

X = 233,168

I thank Carl Friedrich Gauss for his wonderful logic, of course.

Unfortunately, quite a few of the other problems posted on the Project Euler site involve prime numbers, or otherwise need a lot of trial-and-error attempts when done on paper. These are squarely within the bounds of programmers, although I'm still perusing the list for anything that catches my fancy. If I find anything that I feel is worth solving here, I'll solve it here.

But then again, most of the people reading this have probably gotten bored by the time. Maybe I should just get back to the sex, violence and politika.

:)