The purpose of this challenge is to solve the original first Project Euler problem, but as the title suggests in constant time (with respect to the size of the interval).
Find the sum of all the multiples from a list of numbers in some defined range, in such a way that the running time of your program runs in constant time [\$\mathcal{O}(1)\$] with respect to the size of the range
Let us step through the problem statement with an handful of small examples.
Example 1: Let [3,5] be our list of numbers, and let our range be [1, 999] meaning every natural number starting with 1 up to and including 999. To do this in linear time we can do as follows. The multiples of 3 and 5 are
$$ \begin{align*} 3 + 6 + 9 + 12 + \color{red}{15}+18+\cdots+999=3(1+2+3+\cdots+333)=3\,T_{333}\\ 5 + 10 + \color{red}{15} + 20 + \cdots+995=5(1+2+3+\cdots+199)=5\,T_{199} \end{align*} $$
Where \$T_{333}\$ is the 333rd triangular number. \$T_n=n(n+1)/2\$. However, simply adding \$3T_{333}\$ and \$5T_{199}\$, makes us over count. We will then count every number that is both a multiple of 3 and 5 (15, 30, 45...) twice. Thus, our final answer, in constant time with respect to the input range is
$$3T_{333} + 5T_{199}-15 T_{66}$$
Where \$66\$ was chosen because it is the largest value such that \$66\cdot15<999\$.
Example 2: Let [6,9] be our list of numbers, we might suspect that our answer will be
$$\text{Multiples of } 6 + \text{Multiples of } 9 - \text{Multiples of } 6 \cdot 9=54 $$
However this is leads to an error, as the first number counted in the multiples of \$6\$ and \$9\$ is \$18\$ not \$54\$. So
$$\text{Multiples of } 6 + \text{Multiples of } 9 - \text{Multiples of } 18 $$
gives the correct answer. Where, for instance, we could have done \$\text{lcm}(6,9)=6\cdot9/\text{gcd}(6,9)=18\$.
Example 3: Let [3,5,7] be our list of multiples, were we again is dropping the range for the sake of brevity. The easiest is now to use the inclusion-exclusion principle.
So our answer will be
$$ \begin{align} &\text{Multiples of } 3 + \text{Multiples of } 5 + \text{Multiples of } 7 \\ - &\text{Multiples of lcm} (3,5) - \text{Multiples of lcm} (3, 7) - \text{Multiples of lcm} (5, 7) \\ + & \text{Multiples of lcm} (3, 5, 7) \end{align} $$
Input
A list of multiples (or divisors if you will), and a range. You may take input in any convenient method
Output
A single number/string/float ( representing the sum of every number divisible by at least one of the numbers in multiples=[3,5,...] in range [start, stop])
Restrictions and assumptions
- You only have to make sure your program runs in constant time with respect to the size of the range we are working over How, you choose the handle the multiples/divisors is up to you
- The range is always assumed to be non-empty, with inclusive endpoints. Meaning
[10, 10]contains10. - We are working over the integers meaning every multiple and range will be whole non-negative numbers.
Test cases
Our test cases will be on the form list of multiples, range, sum.
[7] [1000, 1000] 0
[3, 5] [1000, 1000] 1000
[3, 5] [ 1, 999] 233168
[3, 5, 7] [ 300, 600] 73558
[9,10] [ 1, 999] 99504
[6, 9] [ 1, 999] 111390
[6, 9, 10, 5, 5, 9] [ 1234, 4321] 3240486
[3, 5] [10**7, 10**8] 2310000085000000
You may use the following code below to test your implementation, note that the implementation below does not run in constant time with respect to the input
def naive(multiples, start, stop):
total = 0
for num in range(start, stop + 1):
for m in multiples:
if num % m == 0:
total += num
break
return total
This is code-golf so shortest code wins!
