PE 0001: Multiples of 3 or 5

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

1

0

1

2

3

4

5

6

7

8

9

=

23

Find the sum of all the multiples of $3$ or $5$ below $1000$.

---

• Sequential Approach
• Selection Approach
• Constant-time Approach
• Generalized Approach
• See Also
  • Arithmetic Series
  • Euclid's Algorithm (GCD and LCM)
  • Solution overview on projecteuler.net
  • FizzBuzz (programming challenge)
• Exercises

Sequential Approach

One very simple approach would be to look at every number, one by one until reaching 1000, adding up each number that is either a multiple of 3 or multiple of 5:

▶️

1

Because only 1000 values have to be inspected, this is actually not an unreasonable approach. And it's a simple property – integer divisibility – something that we can easily check with the modulus operator (%).

python

sum(i for i in range(N) if (i%3 == 0 or i%5 == 0))

golang

sum := 0
for i := range n {
	if i%3 == 0 || i%5 == 0 {
		sum += i
	}
}

prolog

% Copyright (c) 2024 Kevin Damm
%
% Permission is hereby granted, free of charge, to any person obtaining a copy
% of this software and associated documentation files (the "Software"), to deal
% in the Software without restriction, including without limitation the rights
% to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
% copies of the Software, and to permit persons to whom the Software is
% furnished to do so, subject to the following conditions:
%
% The above copyright notice and this permission notice shall be included in all
% copies or substantial portions of the Software.
%
% THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
% IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
% FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
% AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
% LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
% OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
% SOFTWARE.


% Sum is the sum of multiples of {3, 5} below N.
sum_multiples(N, Sum) :-
  sum_multiples_naive(N-1, 0, Sum).

% Base case, Sum is total accumulated when N is 0.
sum_multiples_naive(0, Acc, Acc).

% Sum is accumulated for all values > 0 divisible by 3 or 5.
sum_multiples_naive(N, Acc, Sum) :-
  N > 0, (N mod 3 =:= 0 ; N mod 5 =:= 0),
  !,
  NewAcc is Acc + N,
  Nminus is N - 1,
  sum_multiples_naive(Nminus, NewAcc, Sum).

% Rule for carrying accumulated value on non-divisible values.
sum_multiples_naive(N, Acc, Sum) :-
  N > 0,
  Nminus is N - 1,
  sum_multiples_naive(Nminus, Acc, Sum).


main :-
  sum_multiples(1000, Sum),
  write(Sum).

A direct and brute-force approach like this will still complete in less than a second, even on a small device.

Under a minute, really, even if you include the time for typing the code out.

Selection Approach

+?

That naïve solution inspects all natural values below $n$, even though we know that about half of them are not divisible by $3$ nor by $5$.

To save having to div/mod each of these excluded values, we can count upwards in increments of these numbers, making sure to only count the multiples of three or five.

python

def gen_multiples(n: int) -> Iterator[int]:
  """Generate all integers between 1..n that are divisible by either 3 or 5."""
  for i3 in range(3,n,3):
    yield i3

  for i5 in range(5,n,15):
    # skip each third multiple of 5,
    yield i5
    i5 += 5
    if i5 < n:
      # ...careful not to exceed n.
      yield i5

sum(gen_multiples(100))

golang

sum := 0
for i := 3; i < n; i += 3 {
	sum += i
}
for j := 5; j < n; j += 15 {
	sum += j
	if j+5 < n {
		sum += j + 5
	}
}

prolog

% Copyright (c) 2024 Kevin Damm
%
% Permission is hereby granted, free of charge, to any person obtaining a copy
% of this software and associated documentation files (the "Software"), to deal
% in the Software without restriction, including without limitation the rights
% to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
% copies of the Software, and to permit persons to whom the Software is
% furnished to do so, subject to the following conditions:
%
% The above copyright notice and this permission notice shall be included in all
% copies or substantial portions of the Software.
%
% THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
% IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
% FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
% AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
% LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
% OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
% SOFTWARE.


% Sum is the sum of multiples of {3, 5} below N.
sum_multiples(N, Sum) :-
  sum_by(3, N, Sum3),
  sum_by(5, N, Sum5),
  sum_by(15, N, Sum15),
  Sum is Sum3 + Sum5 - Sum15.

sum_by(Increment, N, Sum) :-
  sum_by(Increment, 0, N, 0, Sum).

% Accumulate each multilpe of Inc less than N.
sum_by(Increment, I, N, Accumulator, Sum) :-
  I < N,
  !,
  SubSum is Accumulator + I,
  NextI is I + Increment,
  sum_by(Increment, NextI, N, SubSum, Sum).

% Resolve total sum when incremented past the limit.
sum_by(Inc, I, N, Acc, Acc) :- I >= N.


main :-
  sum_multiples(1000, Sum),
  write(Sum).

This skips a lot of unnecessary computation by only looking at the numbers that we know will be included in the sum. You could simplify the second loop to look at every five-multiple and skip when the number also divides $3$, but we know in advance that will always be the third one (the one divisible by $15$).

The order that these numbers are added together is not strictly increasing. Since that doesn't affect the final result, and it's a little easier to read this way anyway, I've left it as two separate for-loops. An example of interleaving the series so that the numbers are in sorted order can be found in the github repo for this site.

Constant-time Approach

As $n$ gets bigger, the time spent iterating through the multiples of three and five increases as well. Do we have to look at every multiple, even if we're only examining known multiples?

Realigning the previous solution will reveal a pattern that emerges:

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

The components of the above are the arithmetic sum, in steps of $3$ and in steps of $5$, with the combined steps of $3\times 5=15$ being counted twice, so it should be subtracted from the total. For the above example of n=99,

$$\sum _{i=1}^{\lfloor n/3\rfloor }3i+\sum _{i=1}^{\lfloor n/5\rfloor }5i-\sum _{i=1}^{\lfloor n/15\rfloor }15i=\frac{3\ast 1122}{2}+\frac{5\ast 380}{2}-\frac{15\ast 42}{2}$$

Another way to look at this is to separate out the common parts of each column and row in the above grid, resulting in one part that increases vertically and another part that is the same for every row.

$15\times \sum _0^{k}1$ for

0

0

0

0

0

0

0

15

15

15

15

15

15

15

30

30

30

30

30

30

30

45

45

45

45

45

45

45

60

60

60

60

60

60

60

75

75

75

75

75

75

75

$k\times \sum _0^{k}x$ for

0

3

5

6

9

10

12

0

3

5

6

9

10

12

0

3

5

6

9

10

12

0

3

5

6

9

10

12

0

3

5

6

9

10

12

0

3

5

6

9

10

12

This is in terms of $k$, the number of rows (or, $n÷15$ rounded down, where $n$ is the final counted value).

n := limit - 1
k := n / 15 // number of rows (except partial final row)
rowcount := 5 /*3s*/ + 3 /*5s*/ - 1 /*common*/
rowsum := 0 + 3 + 5 + 6 + 9 + 10 + 12

sum := rowcount * 15 * k * (k - 1) / 2
sum += k * rowsum

The last row may be partial, a few values remaining between $15\times k$ and $n$. We can sum those up in a couple of small for loops, adding them to the main result. Or, since we know the row size consists of non-shared multiples of $3$ and $5$, we can use some number theory to arrive at the result without even having to loop through the numbers in the last row.

90

90

90

90

90

0

3

5

6

9

// Add remaining multiples of 3 and 5 (excluding n).
delta := n - k*15
div3, div5 := delta/3, delta/5
sum += k*15*(div3+div5+1) +
  div3*(div3+1)*3/2 +
  div5*(div5+1)*5/2

To understand the last three lines, it helps to think of the last (partial) row as its own arithmetic series for the threes and fives separately, offset by the $k$th row as with all of the previous rows. The div3 and div5 are the limits on these smaller series, arrived at by counting the numbers between $n$ and the last $k\times 15$ value. You can see the sequence this creates for the full row by looking at the definition of rowsum, and this can be generalized as well.

Generalized Approach

Limit:ab

We could further generalize this to any pair of numbers $a$ and $b$, finding the sum of their multiples that are less than $n$. Rather than knowing in advance to loop every 15, we need to find the Least Common Multiple of the pair and use that as our row size. We can compute it with Euclid's algorithm (which actually determines the greatest common divisor, which we then easily derive the LCM from).

function SumOfPairsLessThan(a: number, b: number, n: number): number {
  const width = lcm(a, b);
  const k = Math.floor(n / width);
  const diva = width / a;
  const divb = width / b;

  const rowcount = diva + divb - 1;
  const rowsum = (diva * (diva + 1) * a + divb * (divb + 1) * b) / 2;

  var sum = rowcount * width * k * (k - 1) / 2;
  sum += k * rowsum;

  const delta = n - 1 - k*width;
  const rema = delta / a;
  const remb = delta / b;
  sum += k * width * (rema + remb + 1);
  sum += rema * (rema + 1) * a / 2;
  sum += remb * (remb + 1) * b / 2;

  return sum
}

function lcm(a: number, b: number): number {
  // Javascript and floating-point error, let's round to be sure, though it's
  // only needed when a*b is many orders of magnitude larger than gcd(a, b).
  return Math.round((a * b) / gcd(a, b));
}

function gcd(a: number, b: number): number {
  if (b === 0) {
    return a;
  }
  return gcd(b, a % b);
}

See Also

Arithmetic Series

Central to this problem is the idea of summing over a series of integers, and the extension to this – summing over all multiples of an integer.

$$\sum _i^{n}ai=a\sum _i^{n}i=a\times \frac{n(n+1)}{2}$$

In some places we had to convert instead to $n(n-1)/2$ because we were counting up to but not including the limit value $n$. If you need help seeing why the above equation works out, try drawing out the series as a stack of boxes like a staircase, 1 then 2 then 3 ... until n. Now, take the second half of it (the taller part of the staircase) and pivot it around so that it is stacked on top of the smaller half of the staircase. This will result in a rectangle with area $n(n+1)/2$, whether $n$ is odd or even it will be a full rectangular shape.

If $n$ is an even number then they can be stacked directly, column-for-column, with a height of $n+1$ and a width of $n/2$. If $n$ is an odd number, then we put the extra column on the slightly larger side and the largest stack ($n$ units tall) stands alone on the left when we pivot it around. The rectangle from joining the two pieces has height $n$ and width $(n+1)/2$.

Try it yourself with some pencil and paper if you're not seeing it yet!

Euclid's Algorithm (GCD and LCM)

After understanding the series part of the problem, further investigation shows that the Least Common Multiple decides what the period of interference between the two divisors is. This is the series that needs to be subtracted out if it gets double counted between the 3s and the 5s.

Since we already knew the pair of constants is $3$ and $5$, finding $15$ from that is straightforward. However, if it may be any pair of numbers then we'll need to determine what this other series is. The GCD is a kind of recursive remainder search. The LCM can then be derived from $(a\times b)/$GCD$(a,b)$.

There are actually some interesting identities bewtween the LCM and GCD, and entire algebras can be derived from their operations. The computation needed to find the GCD is also interesting, and the pairs of values which require the most computation are found along the Fibonacci Sequence. That is, values which follow the line $y=\varphi x$ require the most computation to find GCD$(x,y)$, where $\varphi$ is the golden ratio. Keep reading the wiki page to see beautiful symmetries revealed by applying Euclid's Algorithm to complex conjugates!

Solution overview on projecteuler.net

This doc will only be available if you've already submitted the correct answer. I'm not going to give you the answer directly, but you can execute the code examples here, with only minor edits, to find the answer.

The official overview stops at calculating the $(\sum 3i)+(\sum 5i)-(\sum 15i)$ answer. I preferred my approach for a couple of reasons – it provides an avenue to showing the generalized solution, and it doesn't have the same risk of numeric overflow on large inputs (for languages that don't default to a BigInt).

It is also valuable to read through the forums for any problems you solve, you may see an elegant solution in a language you are less familiar with.

FizzBuzz (programming challenge)

This puzzle is reminiscent of FizzBuzz, but the ProjectEuler.net problem appeard a few years before it became popular as a test of basic programming ability.

Originally it was a children's game, then suggested by Imran Ghory in "Using FizzBuzz to Find Developers who Grok Coding". A month later it was also featured in a codinghorror blog commentary by Jeff Atwood. It isn't meant to be hard, it's meant to be a minimum evaluation function, after conventional wisdom that 99% of interview candidates cannot actually code even the simplest of functions, while knowing enough terminology to give the impression that they can.

The question usually implies a serial printing of "fizz" (at 3s), "buzz" (at 5s) and "fizzbuzz" (at 15s) with the numbers themselves printed otherwies. This means the constant-time algorithms (and even the selection-based one) wouldn't qualify, but I think I would ask if we could just print how many fizzes, buzzes and fizzbuzzes there are (pointing to this blog post if necessary) and maybe get a pass on the interview question. What I'm saying is, I'm not above doing fizzbuzz but give me something challenging.

If you want to take this problem to the next level, especially if you're using it as a starter question in your own interviews, I suggest asking next "what is the probability that an integer chosen at random in range 1..1000 is divisible by 3 or 5?", especially if you are looking for someone with a (slightly) deeper mathematical comprehension. There are numerous topics branching out from there.

Exercises

1. Where is the break-even point, i.e. when the constant-time approach goes from being worse than the linear-time solution to being better? This may vary by platform based on the cost of a div/mod and chosen values for $a,b$ and $n$.

   Benchmark both solutions on your chosen platform and measure for yourself. You can find three example benchmarks in the tests of my golang solution.

2. In the constant-time solution there is an expression rowcount * 15 * k * (k - 1) / 2. How do we know that this division by $2$ will not give us a $0.5$ remainder that gets truncated off?

3. Further generalize the solution to any three divisors. In doing so, you should be able to see a straightforward approach for any $k$ divisors.

4. What is the computational complexity of finding this sum (with respect to $n$) for any $k$ divisors? If $k$ is not fixed? If $k$ is larger than $n$?