Following links: Project Euler

I was just trying to update the wiki on Google's code hosting site, where I put the java GDS-2062 utility. I wanted to add an image, to make it look nice, they're worth a thousand words, you know. And this was only 5k in size, so that's a thousand 4-letter words! Anyway, I ended up looking at a page that had no relevance to my search, it just happened to have the search terms scattered about on it. And there was a blog entry for the Project Euler website. The author of the page (Doug Daniels) had posted some Java code, and before I could stop myself, I was trapped. "That looks like it should be easier than that" I was thinking, and then an hour or so of my afternoon disappeared.

Project Euler lists maths problems. The one the author had posted on his blog was to find the sum of the natural numbers below 1000 that are multiples of 3 or 5. Doug Daniels was on the right track - he posted an equation for the sum of a series, and I used it. The answer to the problem is the sum of all 3-multiple numbers plus the sum of all 5-multiple numbers minus the sum of all 15-multiple numbers. Project Euler told me my answer was wrong. Doug had posted the equation shown here, which appears to have at least one error in it. That minus sign should be a plus, and perhaps the n to the right of the sigma should be a k.

I was pleased to see this equation, I remember its derivation in school as a moment of insight. Anyway, I wrote a reply to Doug's blog, explaining the derivation of the formula and a way of writing down the answer as a one-liner in Java. When I submitted my reply, the blog page came back with no indication I'd ever written anything. I would have been happier to have got a page saying "I've /dev/nulled your smug reply, you big-headed tosser". But there was nothing at all...

So you're going to get it, now. That sum of series. You need it to add up all the multiples of 3 and of 5, and of 15 under 1000. There are 333 multiples of 3 under 1000, from 3 to 999, so you can use the sum equation to calculate 3 times the sum of 1-333. To answer the problem, you could sum the multiples of 3, add the multiples of 5, and then subtract one sum of the multiples of 15, because they were in both series.

You need an equation that works though, so how to sum up numbers from 1 to whatever (n as a mathematician would say)? Write the numbers down in a row, 1 on the left, n on the right. Write a zero to the left of the 1. Under the zero, write the same series down, but starting with n on the left, under the top row's zero, and counting down until you write down 0 under the top row's n. If you add up each column (2 numbers in each column), starting from (0 + n) on the left, and ending with (n + 0) on the right, you'll see that every column sums to n. And there are n + 1 columns (because we added a zero column). Adding the zero doesn't affect the sum, obviously, it just helps the maths work out nicely. Look at what you've written down. There are two of the original series, one counting up, one counting down, and the sums of the columns (all the same). If you add all those sums together, you'll get (n + 1) times n. That's the sum of 2 of the original series. Since the two series you wrote down are the same, they must each contribute half towards that big sum. So the sum of the original series must be (n + 1) times n divided by 2. Or if you don't like words in your equations, it's (n + 1)(n / 2).

I've typed this in once before today, so I'm going to give up early this time. Doug's Java code used for loops to sum test each number under 1000 and add it to a total if it qualified as a multiple of 3 or 5. The one liner (split over 3 lines!) is:

public static int pe35sum(int n)
{
return (((n - 1) / 3) * (((n - 1) / 3) + 1) * 3
+ ((n - 1) / 5) * (((n - 1) / 5) + 1) * 5
- ((n - 1) / 15) * (((n - 1) / 15) + 1) * 15)
/ 2;
}

The divide by 2 has been moved to the end. In some places, integer truncation helps this method work. In the case of the / 2, the 0.5 is necessary, as often as it isn't.

I hope this helps!