Python Implementation of Problem 1

View source code here on GitHub!

Problem Solution

Project Euler Question 1

I decided I wanted to take a funcitonal approach on this one. It also uses only lazy functions, so it should take minimal memory usage.

Revision 1:

I found a closed form solution that works in the general case, so it's about an order of magnitude faster now.

Problem:

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.

python.src.p0001.summation(up_to: int, factor: int) → int
python.src.p0001.main() → int
 1"""
 2Project Euler Question 1
 3
 4I decided I wanted to take a funcitonal approach on this one. It also uses only
 5lazy functions, so it should take minimal memory usage.
 6
 7Revision 1:
 8
 9I found a closed form solution that works in the general case, so it's about an
10order of magnitude faster now.
11
12Problem:
13
14If we list all the natural numbers below 10 that are multiples of 3 or 5, we
15get 3, 5, 6 and 9. The sum of these multiples is 23.
16
17Find the sum of all the multiples of 3 or 5 below 1000.
18"""
19
20
21def summation(up_to: int, factor: int) -> int:
22    n = up_to // factor
23    return (n + 1) * factor * n // 2
24
25
26def main() -> int:
27    return summation(999, 3) + summation(999, 5) - summation(999, 15)

Tags: divisibility