Duncan's blog

October 19, 2008

Project Euler: problem 1

Filed under: Coldfusion,Project Euler — duncan @ 11:07 am
Tags: , , , ,

Initially I wasn’t going to blog about the first two Project Euler problems, because I thought they were too simple. However I read something elsewhere encouraging people to blog about even simple coding things, because there’ll be someone else who’s not at that level that could benefit from reading it.

Problem 1:

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.

So, this seemed pretty simple. I liked the fact they gave a test case, so you could run against that before trying to get the answer for 1000.

Here’s the code I used:

```<cfset sum = 0>
<cfoutput>
<cfloop index="i" from="1" to="999">
<cfif (NOT i MOD 3) OR (NOT i MOD 5)>
<cfset sum = sum + i>
#i#<br>
</cfif>
</cfloop>

<strong>#sum#</strong>
</cfoutput>```

If I modify the loop to run to 9, it outputs
3
5
6
9
23
as expected.

Some things to note:
We’re only running up to 999, not 1000, as it states “below 1000“. Make sure and read your specification carefully!

I guess some people might not be familiar with the MOD statement in Coldfusion, or Modulus in general. Ben Nadel wrote a great article explaining it. Basically x MOD y says, divide x by y, but only give me the remainder. e.g. 10 MOD 3 = 1, because 3 goes into 10 three times, remainder 1. So if we say NOT i MOD 3, we mean this is a multiple of 3, i.e. there is no remainder.

There’s a version called ProperMod in the CFLib which does it better, because it allows division of real numbers as well as integers. It also handles cases where your integer value is larger than Coldfusion will allow (which came in useful for Project Euler problem 3 – more on that later).

I could have written my if statement as:

`<cfif NOT (i MOD 3 AND i MOD 5)>`

because (NOT A) OR (NOT B) = NOT (A AND B). This can be illustrated with some Venn diagrams (coincidentally very similar to Euler diagrams). In each diagram, it’s the cross-hatched part we’re interested in. [Does anyone know some decent free software for creating Venn diagrams like this?]

I preferred to keep it as two separate clauses just for readability.

This solution worked, but the PDF that you get after submitting the correct answer discusses another way to do it. That would be to have one function that sums the values of x MOD y. So you’d do SumOfValues(3) + SumOfValues(5) – SumOfValues(15).