# 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.

# Twelve Men on an Island Logic Puzzle

One of my favorite shows right now is Brooklyn Nine-Nine. During season 2 episode 18, titled “Captain Peralta”, Captain Holt presents this riddle to the team:

There are twelve men on an island. Eleven weigh exactly the same amount, but one of them is slightly lighter or heavier. You must figure out which. The island has no scales, but there is a seesaw. You can only use it three times.

This isn’t exactly a programming post, but it does demonstrate the same kind of problem solving that is often found in devising efficient algorithms.

I decided to represent each islander with a letter from A to L. This makes it easy to unambiguously and concisely represent combinations of islanders. I show each trial with the seesaw as a column. The “Test” column shows what islanders are put on the seesaw as left vs. right. The “Result” column shows “=” if both sides were equal, “<” if the left side weighed less than the right, or “>” if the left side weighed more than the right. Then the “Possibilities” column shows what possible solutions remain given the result of the trial. As we move from the 1st trial towards the 3rd we can see the remaining possibilities reduce as more results eliminate solutions.

When solving this puzzle we know right away that we cannot rely on the seesaw always tilting to the left or right. This seems to be people’s initial attempt at solving this problem. Just put six on one side and six on the other and work your way down. However, 3 trials and only 2 possible results would only give us up to 8 solutions because 2 x 2 x 2 = 8. So we know that we have to rely some trials being balanced to find all the solutions. Therefore, it is probably not a good idea to put six vs. six because there is no way that seesaw could be balanced since the different islander would always be on the seesaw giving only two possible results which doesn’t tell us which side the different islander is on.

The first trial that gives the most information is to do four vs. four (ABCD vs. EFGH). No matter what the result we have reduced the possible solutions from 24 to 8.

Possibilities Test Result Possibilities
A lighter
A heavier
B lighter
B heavier
C lighter
C heavier
D lighter
D heavier
E lighter
E heavier
F lighter
F heavier
G lighter
G heavier
H lighter
H heavier
I lighter
I heavier
J lighter
J heavier
K lighter
K heavier
L lighter
L heavier
ABCD vs. EFGH = I lighter
I heavier
J lighter
J heavier
K lighter
K heavier
L lighter
L heavier
< A lighter
B lighter
C lighter
D lighter
E heavier
F heavier
G heavier
H heavier
> A heavier
B heavier
C heavier
D heavier
E lighter
F lighter
G lighter
H lighter
• If the seesaw is equal then we know those eight islanders (ABCDEFGH) can be eliminated from being either lighter or heavier. The remaining four islanders (IJKL) could then be either lighter or heavier.
• If the seesaw is unbalanced then we know the four untested islanders (IJKL) can be eliminated. We also know that all the islanders on the heavier side cannot be lighter. And all the islanders on the lighter side cannot be heavier.

What we do for the second trial depends on the type of result for the first trial because the pattern of remaining possibilities is different.

• If the first trial was balanced then we have four remaining islanders (IJKL) that could be either lighter or heavier. We can work out the remaining possibilities by comparing three remaining islanders (IJK) with three normal islanders (ABC).

Possibilities Test Result Possibilities
I lighter
I heavier
J lighter
J heavier
K lighter
K heavier
L lighter
L heavier
IJK vs. ABC = L lighter
L heavier
< I lighter
J lighter
K lighter
> I heavier
J heavier
K heavier
• If the second trial was balanced, then you know that that last remaining islander (L) is the different islander. Compare him with any other islander. That will tell you if he is lighter or heavier than the other islanders. This third trial cannot be balanced since we know that this last islander (L) is different from all the other islanders.
• If the second trial was unbalanced, then you now know if the different islander is either lighter or heavier. You also know that the last untested islander (L) is normal. You can weigh two of the remaining islanders against each other to determine which of the remaining three islanders is different. I will show the case where the three islanders (IJK) are lighter.

Possibilities Test Result Possibilities
I lighter
J lighter
K lighter
I vs. J = K lighter
< I lighter
> J lighter
• If the first trial was unbalanced, then this gets much less intuitive. For simplicity, we will only consider the result where the left side is lighter than the right side (ABCD < EFGH). The last case where the left side is heavier than the right side is just the inverse. The key to this trial is to find a test that will make the best use of the three possible seesaw results. Specifically, we don't want to use a test that only has two possible outcomes (like ABC vs. EFG). So I chose to take two potentially lighter islanders with one potentially heavier islander for each side (ABE vs. CDF). This has all three possible outcomes and leaves us with either two or three remaining possibilities.
Possibilities Test Result Possibilities
A lighter
B lighter
C lighter
D lighter
E heavier
F heavier
G heavier
H heavier
ABE vs. CDF = G heavier
H heavier
< A lighter
B lighter
F heavier
> C lighter
D lighter
E heavier
• If the second trial is balanced, then you only have two potentially heavier islanders left. Just weigh them against each other and whoever is heavier is the different islander. It is not possible for this last trial to be balanced since you know one of them is the heavier islander.
• If the second trail is unbalanced, then weigh the remaining potentially lighter islanders against each other. If the third trial is balanced then the last potentially heavier islander is the different islander. If the third trial is unbalanced, then the islander on the lighter side is the different islander.

Here is the full solution:

1st Trial 2nd Trial 3rd Trial
Test Result Possibilities Test Result Possibilities Test Result Possibilities
ABCD vs. EFGH = I lighter
I heavier
J lighter
J heavier
K lighter
K heavier
L lighter
L heavier
IJK vs. ABC = L lighter
L heavier
L vs. A = Impossible
< L lighter
> L heavier
< I lighter
J lighter
K lighter
I vs. J = K lighter
< I lighter
> J lighter
> I heavier
J heavier
K heavier
I vs. J = K heavier
< J heavier
> I heavier
< A lighter
B lighter
C lighter
D lighter
E heavier
F heavier
G heavier
H heavier
ABE vs. CDF = G heavier
H heavier
G vs. H = Impossible
< H heavier
> G heavier
< A lighter
B lighter
F heavier
A vs. B = F heavier
< A lighter
> B lighter
> C lighter
D lighter
E heavier
C vs. D = E heavier
< C lighter
> D lighter
> A heavier
B heavier
C heavier
D heavier
E lighter
F lighter
G lighter
H lighter
ABE vs. CDF = G lighter
H lighter
G vs. H = Impossible
< G lighter
> H lighter
< C heavier
D heavier
E lighter
C vs. D = E lighter
< D heavier
> C heavier
> A heavier
B heavier
F lighter
A vs. B = F lighter
< B heavier
> A heavier