5
\$\begingroup\$

Project Euler Problem #1 Multiples of 3 or 5 states:

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.

I solved it using the following Python code:

#!/usr/bin/env python3

def sum_mult_3_5(max_num: int=1000) -> int:
    """
    Euler Project
    Problem 1
    Multiples of 3 or 5
    Find the sum of all the multiples of 3 or 5 below max_num.
    Return the sum.
    """

    total = 0

    # First find the sum of all the multiples of 3.
    # Also, store all the multiples of 3 in a dictionary.
    multiples = {}
    for mult in range(3, max_num, 3):
        total += mult
        multiples[mult] = 1

    # Now add the sum of all the multiples of 5,
    # using the dictionary to exclude common multiples.
    for mult in range(5, max_num, 5):
        if mult not in multiples:
            total += mult

    return total

if __name__ == "__main__":
    print(f'Total = {sum_mult_3_5()}')
    print(f'Total = {sum_mult_3_5(10)}')

Is this algorithm efficient?

  • Is range a good choice?
  • Was it a good choice to first loop through the multiples of 3, then the multiples of 5?
  • Was it a good choice to store the multiples of 3 in a dictionary?

I haven't looked at any other solutions or discussions for this problem yet, so as to not be biased.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Once you have entered the correct solution for PE #1 you have access to the document projecteuler.net/overview=0001, where a very efficient algorithm is described. \$\endgroup\$ Commented Jun 26 at 19:14
  • \$\begingroup\$ The link is at the bottom of projecteuler.net/problem=1 : “Download overview for problem 1.” \$\endgroup\$ Commented Jun 26 at 19:27

3 Answers 3

Reset to default
8
\$\begingroup\$

Not an expert in Python, I would say iteration was not the best approach in this case, but the remaining two choices (using range for iteration and a dictionary to avoid duplicates) are both very good.

Of course, duplicates could be skipped with a simple test of divisibility, but using a dictionary allows for further extension. If, for example, the problem gets extended to multiples of 3, 5 and 7, the if-composed condition for inclusion-exclusion rule would get very complex. Skipping multi-level duplicates with a dictionary in such a case is straight forward.

Added later:
But, as Robert shows in the answer, a set would be even better than dictionary in this case.

What concerns the first decision, you may sum up all the multiples of a given number in a given range without iterations at all. Just notice the multiples of \$a\$ are \$a, 2a, 3a, \dots\$ which is an arithmetic sequence with an initial term of \$a\$ and the increment \$a\$, too. The sum of \$n\$ terms of such sequence is \$\frac{(n+1)n}2a\$.

There are \$\left\lfloor\frac Na\right\rfloor\$ multiples of \$a\$ up to (and including) some positive \$N\$, so if we need multiples below \$N\$ we take \$\left\lfloor\frac {N-1}a\right\rfloor\$. The brackets are the floor operator, rounding down to the nearest integer.

As a result, the sum of multiples of three \$(a=3)\$ below \$N=1000\$ is \$S_3=\frac{(n_3+1)n_3}2\cdot3\$ for \$n_3=\left\lfloor\frac {1000-1}3\right\rfloor\$.
Similarly, the sum of multiples of five is \$S_5=\frac{(n_5+1)n_5}2\cdot5\$ for \$n_5=\left\lfloor\frac {1000-1}5\right\rfloor\$.

But! Before you add them up, please notice there are also multiples of \$15\$, which get accounted for in both the sums above. So to make the answer right, we need to calculate \$S_{15}=\frac{(n_{15}+1)n_{15}}2\cdot15\$ for \$n_{15}=\left\lfloor\frac {1000-1}{15}\right\rfloor\$ and subtract it from the sum of those two.

Then the final answer is \$\boxed{S_3 + S_5 - S_{15}}\$.

\$\endgroup\$
0
5
+50
\$\begingroup\$

Yes, range is good. No, dictionary without actually using the values is bad, use a set instead. And you don't need your own loops and adding, you can just unpack and use sum:

def sum_mult_3_5(max_num: int=1000) -> int:
    return sum({
        *range(3, max_num, 3),
        *range(5, max_num, 5)
    })

Though inclusion-exclusion as CiaPan said is faster (but really not necessary for this small range). Here's a version with ranges:

def rangesum(r: range) -> int:
    """Compute sum(r), but fast."""
    return (r[0] + r[-1]) * len(r) // 2 if r else 0
    
def sum_mult_3_5(max_num: int=1000) -> int:
    S3, S5, S15 = (
        rangesum(range(i, max_num, i))
        for i in [3, 5, 15]
    )
    return S3 + S5 - S15

That keeps it simple, I don't have to think about how to get the number of multiples exactly right, the range does that for me.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ +1 Very nice simplification by the set construction. And it easily generalises to more than two input fators. \$\endgroup\$ Commented Jun 27 at 11:06
  • \$\begingroup\$ @toolic Oh, the { and } surreptitiously built a set, excluding duplicates \$\endgroup\$ Commented Jun 27 at 13:30
  • \$\begingroup\$ Whoops, what a typo! Of course, I meant 'factors'... \$\endgroup\$ Commented Jun 27 at 16:07
  • \$\begingroup\$ Indeed, inclusion-exclusion is faster, but it can get awkwardly complicated for bigger number of input terms. \$\endgroup\$ Commented Jun 28 at 13:44
  • 1
    \$\begingroup\$ @CiaPan Yes, and even more so if they're not just primes. For example multiples of 6, 10 or 15. \$\endgroup\$ Commented Jun 29 at 6:18
3
\$\begingroup\$ 
    for mult in range(5, max_num, 5):
        if mult not in multiples:
            total += mult

From an algorithmic standpoint, this is a troublesome and unnecessary linear lookup.

It need only be a bit of math to avoid this complexity:

    for mult in range(5, max_num, 5):
        if mult % 3 != 0:
            total += mult

Further, as suggested in comments, your initial loop can be replaced by an O(1) arithmetic sequence equation.

Removing comments for brevity.

def sum_mult_3_5(max_num: int=1000) -> int:
    n = round(max_num / 3 + 0.5)

    total = (n + 1) * n / 2 

    for mult in range(5, max_num, 5):
        if mult % 3 != 0:
            total += mult

    return total
\$\endgroup\$
7
  • \$\begingroup\$ Why do you call a dictionary lookup "troublesome" and "linear"? Highly misleading. And better avoid floats. \$\endgroup\$ Commented Jun 27 at 10:07
  • \$\begingroup\$ multiples is a python dict, not a list, so the lookup is pretty much constant time (although still slower than % 3). \$\endgroup\$ Commented Jun 27 at 12:37
  • 1
    \$\begingroup\$ @Stef But is the lookup slower than Chris's % 3 != 0? In my benchmarking, the lookup is slightly faster than that. Making Chris's code slower than the original. (But the overall solution is probably still faster, if you of course delete the creation of the now unused dict.) \$\endgroup\$ Commented Jun 27 at 13:23
  • \$\begingroup\$ @KellyBundy Hrmpf. I'm always surprised and annoyed at how slow the modulo operator is. 2 = -1 mod 3, so taking the mod 3 of a number expressed in binary could be as easy as removing the sum of even-indexed bits from the sum of odd-indexed bits, but I guess that's not how it's implemented :( \$\endgroup\$ Commented Jun 27 at 13:33
  • \$\begingroup\$ @KellyBundy Although I guess python is the wrong language for this complaint: bitwise operators are slower than modulo \$\endgroup\$ Commented Jun 27 at 13:45

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.