Project Euler Problem 1

Statement

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

Solution

Suppose the base numbers were $2$ and $3$ below $10$ so $9$, they would create duplicates, ie $6$ is counted twice. Therefore take the sum of each multiple to the limit, and one time remove the numbers counted twice:

This revealed a general solution, for base numbers $𝑛,𝑚$ below $𝐿$:

Testing this as code:

>>> def f(n,m,L):
...     a = floor((L-1)/n)
...     b = floor((L-1)/m)
...     c = floor((L-1)/(n*m))
...     return ((n*a*(a+1)) + (m*b*(b+1)) - (n*m*c*(c+1)))/2
...     
>>> f(2,3,10)
44.0
>>> f(3,5,10)
23.0

This general solution passes the two tests above.

>>> f(3,5,1000)
233168.0

Testing against the question, this result is successful. But what about for more than 2 numbers? How can this be approached?

Given a set $𝐴$ of base numbers, a multiple would be counted once for each of its divisors present in $𝐴$.

An easy solution is that in code, a hashmap could track the number of times each number is counted, and iteratively remove duplicates.

The goal is to not add the number if it was already added.

Mathamatically this can be done piecewise. If a previous element of $𝐴$ divides ${𝐴}_{𝑖}𝑘$, skip that number.