Project Euler – Problem 1

So, as I mentioned earlier, I will be posting solutions to Project Euler problems.

Problem 1 is indicated as follows:

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 first thing we can try is a brute force solution.

$sum = 0
foreach ($number in 1..999)
    if ($($number % 3 -eq 0) -or $($number % 5 -eq 0))
        $sum += $number

The solution goes in a loop through all the numbers from 1 to 999 (because the problem states we need to find multiples below 1000). With the if statement we check if the current number is a multiple of 3 or 5. If it is, we add the value to our accumulator $sum. After the loop ends, $sum holds the required answer.

The brute force solution is an acceptable choice as the numbers involved are not very large. However, this is not a very elegant solution.

For a more elegant solution we will employ arithmetic progressions. At first, we need to notice that the multiples of the 3 and 5 are two arithmetic progressions – 3, 6, 9, 12, … and 5, 10, 15, 20, … Next, lets remember the formula to find the sum of a certain number of terms of an arithmetic progression:

 S_n = \frac{n}{2} (a_1 + a_n),

where S_n is the sum of n terms (n^{\mathrm{th}} partial sum), a_1 is the first term, a_n is the n^{\mathrm{th}} term.

To effectively use the formula, we need to find the last terms in the progressions which are less than 1000. For multiples of 3 it is 999. It is the 333rd term in the progression (999/3 = 333). For multiples of 5 it is 995. It is the 199th term in the progression (995/5 = 199).

Now, we could use the formula to calculate the sums… but we would get the wrong answer! This is because some of the terms in the progressions are both multiples of 3 and 5 (e.g., 15, 30, 45, etc). Because of this, these items were included twice (once in the sum of multiples of 3 and once in the sum of multiples of 5). To counter this, we need to subtract all these terms from the sum. To do this, we can use the same summation formula, because the unneeded terms also form an arithmetic progression. The last term would be 990, and it is the 66th term in the progression (990/15 = 66).

So, now our formula would be

 sum = \frac{n_3}{2} ({a_3}_1 + {a_3}_n) + \frac{n_5}{2} ({a_5}_1 + {a_5}_n) - \frac{n_{15}}{2} ({a_{15}}_1 + {a_{15}}_n).

So, we could calculate it in PowerShell by running this command:

$sum = ((333 * (3 + 999)) / 2) + ((199 * (5 + 995)) / 2) - ((66 * (15 + 990)) / 2)

And that’s it! I hope that you enjoyed reading this post and that it helped you in some way.

Leave a Reply

Your email address will not be published. Required fields are marked *