Project Euler Problem 1: Multiples of 3 and 5

Project Euler Problem 1 instructs:

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.

This ends up being a basic math problem, so no code is needed yet.

I think the easiest way to think of this is as a variation on triangular numbers. Triangular numbers are the sums of the first n natural numbers. Which is a very similar description to our problem statement. The initial formula for triangular numbers is:

T_n=\displaystyle\sum_{k=1}^nk

Expanded, this looks like:

T_n=1+2+3+...+(n-2)+(n-1)+n

If we do a little trick here, then we can simplify this expression considerably. Take the above expansion, reverse it, and add it to the original expansion term by term.

\begin{aligned}&T_n&=&1&+&2&+&3&+&...&+&(n-2)&+&(n-1)&+&n\\+&T_n&=&n&+&(n-1)&+&(n-2)&+&...&+&3&+&2&+&1\\=&2T_n&=&(n+1)&+&(n+1)&+&(n+1)&+&...&+&(n+1)&+&(n+1)&+&(n+1)\end{aligned}

If we simplify the repeated terms we get:

2T_n=n(n+1)

And then solve for T_n:

T_n=\dfrac{n(n+1)}2

Great! Now we really have something that we can use in our solution. Since the problem asked for the sum of natural numbers below 1000 let us subtract 1 to get 999. Then divide that by i (which will represent the increment being summed, either 3 or 5 in this problem). Last, scale by i so that we are adding up multiples of the increment instead of just sequential natural numbers. So if L represents the upper limit provided (1000), then we get this equation:

S(L,i)=iT_{{\lfloor}\frac{L-1}i{\rfloor}}

Now substitute the final equation for T_n:

S(L,i)=\dfrac{i}2{\lfloor}\dfrac{L-1}i{\rfloor}({\lfloor}\dfrac{L-1}i{\rfloor}+1)

However, we need the sum of numbers that are either multiples of 3 or 5. So we have to add both of those results and then subtract the intersection that would otherwise be counted twice.

S(1000,3) + S(1000,5) - S(1000,15)

166833 + 99500 - 33165 = 233168

It would have arguably been simpler to just write a quick program that loops through all natural numbers less than 1000 and total any value that is a multiple of 3 or 5. However, thinking about this problem mathematically is good practice for what is up ahead. In future problems you will not have the luxury of using an algorithm that takes linear time instead of constant time.

However, if you’d really like to see this in code, then here is my C# example:

using System;

namespace Problem1
{
	public class Program
	{
		static void Main(string[] args)
		{
			int result = Solve(1000);
			Console.WriteLine(result);
		}

		public static int Solve(int limit)
		{
			return Sum(limit, 3) + Sum(limit, 5) - Sum(limit, 15);
		}

		static int Sum(int limit, int increment)
		{
			int n = (limit - 1) / increment;
			return increment * n * (n + 1) / 2;
		}
	}
}

You can find the code on GitHub (complete with a unit test) at https://github.com/josiahwood/ProjectEuler/tree/master/Problem1.

1 thought on “Project Euler Problem 1: Multiples of 3 and 5

  1. Pingback: Project Euler Problem 2: Even Fibonacci numbers | Josiah Wood

Leave a Reply

Your email address will not be published.