Project Euler 1: Multiples in constant time

Question

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 \3ドルT_{333}\$ and \5ドルT_{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

$3ドルT_{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.

enter image description here

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] contains 10.
• 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!

• xnor: It's OK if the code is exponential-time in terms of the length of the list of divisors?
• N3buchadnezzar: @xnor Read the first bullet point in Restrictions and assumptions =)

Answer 1

Jelly, 20 bytes

+Ø.÷€AĊc2ḋIɓN;æl\ƒ-Ḋ

Try it online!

Port of my own APL answer. Trailing ɓ chain trick is indeed strong :P

How it works

+Ø.÷€AĊc2ḋIɓN;æl\ƒ-Ḋ Dyadic link; left=range, right=divisors
xxxxxxxxxxxɓyyyyyyyy x(left, y(right, left))
 N;æl\ƒ-Ḋ y: subset LCMs, negative for even-sized ones
 N Negate the divisors
 ƒ- Starting with -1, reduce by
 ;æl\ current list ++ LCM(current list, next num)
 Ḋ Remove the leading -1
+Ø.÷€AĊc2ḋI x: range(start, end), subset LCMs -> answer
+Ø. Add 1 to the end
 ÷€AĊ Divide each by subset LCMs, abs, ceil
 c2 nC2 of each
 ḋ Dot product of each row with subset LCMs
 I Increments (2nd - 1st)

• Jonathan Allan: Took me a while to work out how it works, but that is simply brilliant. EDIT: Also +1 for using one of my babies, ɓ :D

Answer 2

APL (Dyalog Extended), 31 bytes

-/+/(⎕+⍳2)(×ばつ2!⌈⍤|⍤÷)\∊(⊢,∧)\-⎕

Try it online!

Full program which takes the list of divisors, and then the (start,end) pair. Uses a modified trick to generate all nonempty subsequences. Also abuses the definition of LCM which is LCM(a,b) = a * b / GCD(a,b) and GCD is always positive, so LCM follows the sign of a * b.

How it works

-/+/(⎕+⍳2)(×ばつ2!⌈⍤|⍤÷)\∊(⊢,∧)\-⎕ Input 1: divisors; input 2: range (start,end)
 ∊(⊢,∧)\-⎕ LCMs of all nonempty subsets of divisors,
 negative if the subset has odd size
 (⎕+⍳2) Add 1 to the right end of the range
 ( )\ Outer product:
 ⌈⍤|⍤÷ ceil(abs(left ÷ right))
 ×ばつ2! nC2 to each of above, times right
 For each pair of (a,b), this evaluates the sum of
 numbers in [1..a] divisible by b, following sign of b
-/+/ Sum of 1st row - sum of 2nd row
 (each value was negated because odd subsets should be added, not subtracted;
 the difference order fixes the negation)

Answer 3

Python 3, 229 bytes

lambda d,s,e:sum(-(-1)**len(k)*(t(e//l(*k))-t(~-s//l(*k)))*l(*k)for k in p(d)[1:])
t=lambda x:x*-~x//2
p=lambda k:k and[j+a for j in[[],k[:1]]for a in p(k[1:])]or[[]]
l=lambda a,*b:b and a*l(*b)//math.gcd(a,l(*b))or a
import math

Try it online!

-5 bytes thanks to ovs

There's probably a less direct approach. I haven't properly golfed in Python in too long.

• ovs: A few (untested) golfs: ~(-s//l(*k))) -> ~-s//l(*k), x*(x+1) -> x*-~x and (len(k)%2*2-1) -> -(-1)**len(k)

Answer 4

Vyxal s, 32 bytes

$ṗḢƛ:λ=*ġḭ;R:1‹÷›"$ḭ:›*2ḭ ̄unLe**

Try it Online!

Answer 5

05AB1E, 25 bytes

æ¦ε.¿DIāÉ-s÷D>*2÷Æ®ygmP}O

Try it online!

æ¦ε } # map over each non-empty subset of the divisors
 .¿D # take the LCM of the subset
 IāÉ- # push the range with the lower bound decreased
 s÷ # integer divide modified range by LCM
 D>*2÷ # for both resulting integers, compute the nth triangular number
 Æ # reduce by subtraction (results in negative values)
 ®ygm* # multiply with LCM and (-1)**len(subset)
 O # sum the resulting list

• hyperneutrino: Did you mean LCM in your explanation? I'm trying to understand this because if GCD works, I can probably golf my Python solution down. It looks like LCM from testing but I don't know 05AB1E enough to know if I messed something up when trying to test parts of the code.
• ovs: @hyper-neutrino You're right, this is the LCM, my bad. I think this doing the exact same thing as your Python solution.

Answer 6

Vyxal, 37 bytes

$ṗḢƛ:λ=*ġḭ;R:1÷$‹$"$ḭ:2+1⁄2$*÷-$Lu$e*;∑

Try it Online!

This is extremely messy. In case it wasn't clear, I am terrible with stack-based languages.

Answer 7

J, ⁷² 69 bytes

1#.(_1*_1^1#.g)*(_1 0+[)(]*[:-~/(2!>:)@<.@%/)]*./@#~g=.1}.2#:@i.@^#@]

Try it online!

^{-3 thanks to nC2 trick from Bubbler's answer}

There's some more golf's I believe I can port from Bubbler's APL answer. Will try tomorrow.

Answer 8

Jelly, (削除) 30 (削除ここまで) 29 bytes

-1 thanks to caird coinheringaahing!

×ばつʋⱮⱮœcⱮJæl/€€Ɗ}§Ṛḅ-

Try it online!

How?

×ばつʋⱮⱮœcⱮJæl/€€Ɗ}§Ṛḅ- - Link: [start, stop]; divisors
 1¦ - apply to index 1 (of [start, stop]):
’ - decrement -> [start-1, stop]
 } - using right (divisors):
 Ɗ - last three links as a monad - f(divisors):
 J - range of length -> [1,2,...,#divisors]
 Ɱ - map with (for n in that):
 œc - all ways to choose n of the divisors
 € - for each (list of choices of length n):
 € - for each (way to choose):
 / - reduce by:
 æl - least common multiple
 Ɱ - map across (for each list of LCMs):
 Ɱ - map across (for each LCM):
 ʋ - last four links as a dyad - f([start-1, stop],LCM):
 : - integer divide -> [(start-1)//LCM, stop//LCM]
 call this "[A,B]"
 Ʋ - last four links as a monad - f([A,B]):
 ‘ - increment -> [A+1,B+1]
 ×ばつ - multiply -> [A(A+1),B(B+1)]
 H - halve -> [A(A+1)/2,B(B+1)/2]
 I - differences -> [B(B+1)/2-A(A+1)/2]
 Ḣ - head -> B(B+1)/2-A(A+1)/2
 ×ばつ - multiply -> LCM(B(B+1)/2-A(A+1)/2)
 § - sums -> [sum of single-choices, sum of two-choices, ...]
 Ṛ - reverse
 ḅ- - convert from base -1 -> ×ばつ(sum of single-choices)×ばつ(sum of two-choices)+...

---

With fewer loops using the same approach, also 30 bytes:

×ばつʋæl/}\ⱮⱮœcⱮJ$}§Ṛḅ-

---

With no constraint on computational complexity, 7 bytes (-1 thanks to caird again!):

r/ọẸ\ƇS

• caird coinheringaahing: You can golf the unconstrained one to 7 bytes by replacing ḍ@ with ọ. Also: 29 bytes for the main one

Answer 9

Python 3, 146 bytes

lambda d,s,e:(e*e+e-s*s+s+g(d,e)-g(d,s-1))//2
g=lambda d,n,m=1:g(d[1:],n,m)-g(d[1:],n,m*d[0]//math.gcd(m,d[0]))if d else~n//m*(n//m)*m
import math

Try it online!

Some tricks explained: ~n//m is a shorter way to write -(n//m+1), and e*e+e-s*s+s is twice the sum of integers in the interval.

---

Python 3.9, 138 bytes

lambda d,s,e:(e*e+e-s*s+s+g(d,e)-g(d,s-1))//2
g=lambda d,n,m=1:g(d[1:],n,m)-g(d[1:],n,math.lcm(m,d[0]))if d else~n//m*(n//m)*m
import math

Uses the new math.lcm in Python 3.9. No TIO link because Python 3.9 is not available there yet.

• ovs: 144 bytes by using bitshift instead of division.
• ovs: 140 bytes

Answer 10

Charcoal, 41 bytes

×ばつ↨ι±1+Σιε⊗ε

Try it online! Link is to verbose version of code. Explanation:

≔Πθε

Calculate the product of the divisors, as it gets used enough times that it saves a byte.

×ばつ÷−⟦⊖ηζ⟧ιεει

Map over the product, generating an adjusted half-open range of (first multiple below, last multiple not above] for each possible remainder.

×ばつ↨ι±1+Σιε⊗ε

Calculating the sum of the integers within the range with that remainder as (last - first) * (last + first + product) / (2 * product).

IΣE...∧⊙θ¬%κλ...

Map over the list of ranges, calculating the sums for those which are divisible by one of the divisors, and output the overall sum.