# Find the sum of all numbers below n that are a multiple of some set of numbers

Almost equivalent to Project Euler's first question:

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.

## Challenge:

Given a positive integer N and a set of at least one positive integer A, output the sum of all positive integers less than N that are multiples of at least one member of A.

For example, for the Project Euler case, the input would be:

1000
3
5


## Test cases:

Input : 50, [2]
Output: 600

Input : 10, [3, 5]
Output: 23

Input : 28, [4, 2]
Output: 182

Input : 19, [7, 5]
Output: 51

Input : 50, [2, 3, 5]
Output: 857

• 1) Do we count numbers that are multiples of both twice? 2) Can we only get two other numbers? or any amount say one or 3? Dec 19, 2016 at 3:48
• Can you give some test cases? Obviously don't post the answer to the PE one, but what about other examples? Dec 19, 2016 at 3:55
• @WheatWizard: The word "or" implies that each number is counted only once, at most. I agree that the question needs to make it clear how many "numbers to check for multiples of" arguments must be supported, though. Exactly two? One or more? Zero or more?
– smls
Dec 19, 2016 at 3:58
• Can we take "numbers equal to or below 10", or take 9 as input instead of 10? Dec 19, 2016 at 7:41
• "and a set of at least one positive integer A" how big can the set be? Dec 19, 2016 at 7:41

# Jelly, 6 bytes

ḍþṖḅTS


Try it online!

### How it works

ḍþṖḅTS  Main link. Left argument: D (array). Right argument: n (integer)

ḍþ       Divisible table; test each k in [1, ..., n] for divisibility by all
integers d in D.
Ṗ     Pop; discard the last Boolean array, which corresponds to n.
ḅ    Unbase; convert the Boolean arrays of base n to integer. This yields a
non-zero value (truthy) and and only if the corresponding integer k is
divisible by at least one d in D.
T   Truth; yield the array of all indices of truthy elements.
S  Compute their sum.

• Of course @Dennis has to come with something that will make you wonder what you're doing on ppcg Dec 19, 2016 at 19:35

# Octave, 3836 33 bytes

@(x,y)(1:--x)*~all(mod(1:x,y),1)'


Take input as: f(10, [3;5]). This would be 2 bytes shorter if the input could be f(9,[3;5]) for the same test case.

Verify all test cases here.

Explanation:

@(x,y)        % Anonymous function that takes two inputs, x and y
% x is a scalar and y is a vertical vector with the set of numbers
(1:--x)*      % Pre-decrement x and create a vector 1 2 ... x-1


Octave can pre-decrement, so using 1:--x instead of 1:x-1 (two times) saves two bytes.

mod(a,b) gives 1 2 0 1 2 0 1 2 0 for mod(1:9,3). If the second argument is a vertical vector, it will replicate the first input vertically and take the modulus for each of the values in the second input argument. So, for input mod(1:9, [3;5]) this gives:

1 2 0 1 2 0 1 2 0
1 2 3 4 0 1 2 3 4


Taking ~all(_,1) on this gives true for the columns where at least one value is zero, and false where all values are non-zero:

~all(mod(1:x,y),1)
0 0 1 0 1 1 0 0 1


The ,1 is needed in case there is only one number in y. Otherwise it would act on the entire vector instead of number-by-number.

Transposing this to a vertical matrix and use matrix multiplication, will give us the correct answer, without the need for explicit summing:

• Oh that's cruel: I had to add 2 bytes because of the difference between x and x–1, but you had to add 4 bytes, and I'm now ahead by 1 byte >:) Dec 19, 2016 at 9:02

# Python, 59 55 bytes

lambda n,l:sum(v*any(v%m<1for m in l)for v in range(n))


repl.it

Unnamed function taking an integer, n and a list of integers l. Traverses a range of the Natural numbers (plus zero) up to but not including n and sums (sum(...)) those that have a remainder after division of zero (v%m<1) for any of the integers m in the list l. Uses multiplication rather than a conditional to save 3 bytes.

## JavaScript (ES6), 4039 36 bytes

Input: integer n and array of integer(s) a with currying syntax (n)(a)

n=>F=a=>n--&&!a.every(v=>n%v)*n+F(a)


### Test cases

let f =

n=>F=a=>n--&&!a.every(v=>n%v)*n+F(a)

console.log(f(50)([2]));        // 600
console.log(f(10)([3, 5]));     // 23
console.log(f(28)([4, 2]));     // 182
console.log(f(19)([7, 5]));     // 51
console.log(f(50)([2, 3, 5]));  // 857

• I had a slightly different formulation for the same length: f=(n,a)=>n--&&a.some(v=>n%v<1)*n+f(n,a). Best I could do nonrecursively was 61 bytes.
– Neil
Dec 19, 2016 at 9:56
• @Neil Your comment encouraged me to look for yet another formulation. Interestingly, the currying syntax saves 3 bytes. Dec 19, 2016 at 10:16

# MATL, 9 bytes

q:ti\~*us


Try it online!

• Just checking if I read this right (without checking the docs). You're decrementing, creating a vector 1 2 .... You duplicate it and take modulus the other input. You negate it and multiply with the vector 1 2 .., use unique to get rid of duplicates and finally summing it... Dec 19, 2016 at 10:36
• Exactly! I'm on the mobile so I didn't include an explanation. Now it's not necessary :-) Dec 19, 2016 at 10:38

## Retina, 34 bytes

Byte count assumes ISO 8859-1 encoding.

\d+
$* M&!(.+)\1*(?=1¶.*\b\1\b) 1  Input format is 50 2,3,5  Try it online! # R, 67 bytes a=scan();x=c();for(i in a[-1])x=c(x,seq(i,a[1]-1,i));sum(unique(x))  Takes a vector to STDIN in the following format: [N, a_1, a_2, ...]. Supports any number of a. For each a, creates the sequence a to N-1 with stepsize a. Then takes the sum of all the unique entries in that vector. • 50 bytes Aug 12, 2020 at 20:38 # Python, 67 bytes a,b,c=input() x=y=0 exec("if x%c<1or 1>x%b:y+=x\nx+=1\n"*a) print y  After writing this I noticed my code was similar to the existing python answer, however I came up with it independently and am posting it anyway. • You don't need the semicolon in the exec, since you have a line break after it anyway. I knew my answer could be outgolfed! – Theo Dec 19, 2016 at 5:44 • The spec says "a set of at least one positive integer"; this seems to only handle the case where the set is two integers. Also having x=y=0 on a separate line would save four bytes. Dec 19, 2016 at 7:52 • @JonathanAllan cool, thanks a lot! Dec 19, 2016 at 16:57 # Mathematica, 37 27 bytes Thanks to Martin Ender for a shrewd observation that led to big byte savings! Tr[Union@@Range[#,#2-1,#]]&  Unnamed function taking two arguments, a list # of integers (the desired divisors A) and an integer #2 (the upper bound N) , and returning an integer. Range[#,#2-1,#] gives, for each element d of the list #, all the multiples of d less than or equal to #-1 (hence less than #); the union of these lists is then computed and summed with Tr. Previous version: Tr[x=#;Union@@(Range[#,x-1,#]&/@#2)]&  • Range is listable: Tr[Union@@Range[#2,#-1,#2]]& (and then save another byte by swapping the order of the inputs) Dec 19, 2016 at 10:21 # Perl 6, 25 bytes {sum grep *%%@_.any,^$^a}


A lambda that takes the input numbers as arguments. (One argument for N, and an arbitrary number of arguments for A).

### Explanation:

• { ... }: A lambda.
• $^a: First argument of the lambda. • @_: Remaining arguments of the lambda ("variadic parameter"). • ^$^a: Range from 0 to $^a - 1. • * %% @_.any: Another lambda, which tests its argument * using the divisible-by operator %% against an any-Junction of the list @_. • grep PREDICATE, RANGE: iterates the range of numbers and returns the ones for which the predicate is true. • I think adding ^ to declare a placeholder parameter is fairly explicit. Especially since you could use it later in the block as just $a. I think only $_ @_ %_ self can ever be considered to be implicitly declared. I think I would have that line read "declare first parameter as a placeholder" Dec 20, 2016 at 2:43 • @BradGilbertb2gills: I meant that it implicitly becomes part of the lambda's signature, even though the code didn't introduce a signature before the lambda's body. @_, and %_ in case of functions, are no different in that regard: They too only become part of the signature if they appear in the body. Only $_ (and self and %_ in methods) can become part of a signature by default.
– smls
Dec 20, 2016 at 15:36
• PS: I removed the phrase "implicitly declared" now, though, as it's not necessary for understanding the code.
– smls
Dec 20, 2016 at 15:43

# Haskell, 42 39 bytes

a!b=sum[x|x<-[1..a-1],any((<1).mod x)b]


Usage:

Main> 50![2,3,5]
857


Thanks to @Zgarb for 3 bytes

• (xmod) is the same as mod x. Dec 19, 2016 at 8:53
• @Zgarb whoops :)
– Angs
Dec 19, 2016 at 10:39

# 05AB1E, 9 bytes

FND²%P_*O


Try it online!

F         For N in [0, ..., input[0]-1]
ND²%     Evaluate N%input[1]; yields an array of results
P    Take the total product of the array. Yields 0 only if at least one of the value is 0, in other words if N is multiple of at least one of the specified values
_   Boolean negation, yields 1 if the last value is 0 and yields 0 otherwise
*  Multiply by N: yields N if the last value is 0 and yields 0 otherwise
O Display the total sum

• 8 bytes or 8 bytes alternative using a filter. (The first 8-byter wasn't possible when you posted your answer, though. Since à (maximum) pops the list now, but didn't before.) Jun 28, 2019 at 12:29

# Octave, 49 37 bytes

@(A,N)sum(unique((z=(1:N)'.*A)(z<N)))


the function will be called as f([2 3 4],50)

Assume that A=[2 3 4]; we require to have sum of numbers as

sum(
2,4,6...,50-1 ,
3,6,9...,50-1,
4,8,12,...50-1)


we can multiply [2 3 4] by 1:50 to get matrix (1:N)'.*A

[2 4 6 ... 2*50
3 6 9 ... 3*50
4 8 12 ...4*50]


then extract from the matrix those that are smaller than 50 : z(z<N)

Since there are repeated elements in the matrix we extract unique values and sum them.

previous answer: (this solution will fail if N==1)

@(A,N)sum((k=uint64(1:N-1))(any(k==(k./A').*A')))


function should be called as f(unit64([2 3 4]),uint64(50))

• Very nice! Almost as sort as the other octave answer, but a completely different approach. This didn't cross my mind at all! Could benefit from having some explanation though and maybe a link to ideone, but you have my vote already :-) Dec 19, 2016 at 22:21
• I changed the order of the input, but here's a link ideone.com/8Bljrl Dec 19, 2016 at 22:25

# Japt -x, 97 6 bytes

Ç*VøZâ


Try it

           :Implicit input of integer U and array V
Ç          :Map each Z in the range [0,U)
*         :  Multiply by
Vø       :  Does V contain
Zâ     :   Any of the divisors of Z
:Implicit output of sum of resulting array


# Pip, 43 41 39 35 bytes

b^:sFc,a{f:0Fdb{f?0c%d?0(f:i+:c)}}i


Try it online!

Explanation:

Takes inputs like so:

arg1 1000
arg2 3 5

b^:s                      ;read rest of inputs as array
;(s is " " and ^ is split into array on char)
F c ,a{                   ;for(c in range(0,a))
f:0                     ;flag to prevent double counting 15,30,etc.
F d b {                 ;forEach(d in b)
f? 0 c%d? 0 (f:i+:c)  ;if flag {continue}elif c%d {f=i+=c}
;      (i will always be truthy so why not)
}
}
i                         ;print sum

• whoops! I read too fast Jun 27, 2019 at 18:03
• Much better. Great answer! Jun 27, 2019 at 18:14

# Pyth, 10 bytes

s{sm:0hQdt


### Explanation

s{sm:0hQdtQ   Implicit input
:0hQd     Get multiples of d below the bound
m     tQ   ... for each d given
s           Concatenate results
{            Remove repeats
s             Take the sum


# T-SQL, 87 bytes

This will work as long as @i has a value of 2048 or lower

USE master--needed for databases not using master as default
DECLARE @i INT=50
DECLARE @ table(a int)
INSERT @ values(2),(3),(5)

SELECT sum(distinct number)FROM spt_values,@ WHERE number%a=0and abs(number)<@i


Try it out

# APL (Dyalog Unicode), 12 bytes

+/⊢∘⍳∩∘∊×∘⍳¨


Try it online!

Anonymous tacit function. Thanks to @Adám for helping me shave 3 bytes off of this. Uses ⎕IO←0.

### How:

+/⊢∘⍳∩∘∊×∘⍳¨ ⍝ Tacit function. Left and right arguments will be called ⍺ and ⍵ respectively.

×∘⍳¨ ⍝ Multiply ⍺ with each element of [0..⍵-1]
∊     ⍝ Enlist (flattens the vector)
∩∘      ⍝ Then, get the intersection of that vector with
⊢∘⍳        ⍝ The vector [0..⍵-1].
+/           ⍝ Then sum


# Google Sheets, 141 140 134 132 90

Closing parens already discounted.

Phew! That was more work than I bargained for. The hard part was getting something that worked for all ranges.

### Inputs:

• A1 - N
• Row 2 - A1, A2, ...

### Formulae:

• A3 - =A1-1 (N - 1)
• A4 - =SUM(ArrayFormula(SEQUENCE(A3)*LT(,COUNTIF(MMULT(SEQUENCE(A1),FILTER(2:2,2:2)),SEQUENCE(A3)))))

Where A4 is the final output.

### How It Works

Hint: Start from the middle.

# Sum everything together
=SUM(
ArrayFormula(
# The "number under N"
SEQUENCE(A3)*
# Use the LT Operator function to pile parens at the end
LT(
# Implicit 0
,
COUNTIF(
# Generate every multiple of each element in A via matrix multiplication up to the Nth multiple.
# This is overkill, but saves characters.
MMULT(
# Column Matrix (1, ... , N) and Row Matrix (A1, A2, ...).
SEQUENCE(A1),
# Have to remove blanks from the end
FILTER(2:2,2:2)
),
# If element appears in the resulting matrix, multiply by 1, or else 0
SEQUENCE(A3)
)
)
)
)


# x86-16 machine code, 27 25 bytes

Binary:

00000000: 33db 4a51 56ac a20c 018a c2d4 0ae0 f675  3.JQV..........u
00000010: 0203 da5e 594a 75eb c3                   ...^YJu..


Listing:

33 DB       XOR  BX, BX                 ; clear BX running sum
4A          DEC  DX                     ; N = N - 1 (only multiples below N)
N_LOOP:
51          PUSH CX                     ; save array length
56          PUSH SI                     ; save array start pointer
F_LOOP:
AC          LODSB                       ; AL = next factor
A2 0C01     MOV  BYTE PTR[AAM1+1], AL   ; AAM divisor = AL
8A C2       MOV  AL, DL                 ; AL = dividend
AAM1:
D4 0A       AAM                         ; ZF = ( current N % factor == 0 )
E0 F6       LOOPNZ F_LOOP               ; if not a multiple, continue to next factor
75 02       JNZ  F_BREAK                ; if last is not a multiple, don't add
03 DA       ADD  BX, DX                 ; otherwise add factor to sum
F_BREAK:
5E          POP  SI                     ; restore array pointer
59          POP  CX                     ; restore array length
4A          DEC  DX                     ; decrement N / loop counter
75 EB       JNZ  N_LOOP                 ; loop until N = 0


As a function: input N in DL, SI array of factors, CX array size.

Once again, using DOS DEBUG to test. Note: literal values are in hex in DEBUG.

N = 10 (0xA), [ 3, 5 ] = 23 (0x17)

N = 50 (0x32), [ 2, 3, 5 ] = 857 (0x359)

## Python 2, 80 Bytes

This is very long. Can definitely be shortened. Taking the 3 numbers as separate inputs is definitely hurting the score.

i=input
x=i();y=i();z=i();s=c=0
exec("if c%z<1 or c%y<1:s+=c\nc+=1\n"*x)
print s

• You could do x,y,z=input() and give input in the form of (1000,3,5). Dec 20, 2016 at 17:35

## Common Lisp, 77

(lambda(n x)(loop for i below n when(some(lambda(u)(zerop(mod i u)))x)sum i))


### Ungolfed

(lambda (limit seeds)
(loop for i below limit
when (some (lambda (u) (zerop (mod i u))) seeds)
sum i))


# PowerShell, 57 bytes

param($a,$b)(1..--$a|?{$i=$_;$b|?{!($i%$_)}})-join'+'|iex


Try it online!

Iterative solution. Takes input as a number $a and as a literal array $b. Loops from 1 up to one below $a (via --$a), using a Where-Object operator |?{...} with a clause to select certain numbers.

The clause sets $i to be the current number before sending input array $b into another |?{...}, here picking out those items where the current number is evenly divided by at least one of the numbers in $b. Those elements of $b that do divide evenly are left on the pipeline.

Thus, if there is at least one element from $b, the pipeline contains an element, so the outer Where is $true and the current number is left on the pipeline. Otherwise, with no elements from $b on the pipeline, the outer Where is $false, so the current number is not placed on the pipeline.

Those numbers are all gathered up in parens, -joined together with + signs, and piped to |iex (short for Invoke-Expression and similar to eval). The summation result is left on the pipeline, and output is implicit.

# PHP, 7876 74 bytes

for(;++$i<$argv[$f=$k=1];$s+=$i*!$f)for(;$v=$argv[++$k];)$f*=$i%$v;echo$s;


The outer loop runs $i from 1 to below first argument and adds $i to $s if $f is not set.
The inner loop multiplies $f with ($i modulo argument) for all subsequent arguments, setting $f to 0 if $i is the multiple of any of them.

Run with -r.

# Scala, 47 bytes

n=>1.to(n(0)-1).filter(i=>n.exists(i%_==0)).sum


n is a List which contains of a first argument N, the rest are elements of A

Works by filtering out numbers where there doesn't exist at least one A of which i is a multiple, then summing. Strictly speaking we should use n.tail.exists inside the closure, but as i is always less than N and therefore never a multiple of N the solution is still complete without this.

# Java 8, 75 bytes

(N,A)->IntStream.range(1,N).filter(x->A.stream().anyMatch(y->x%y==0)).sum()


The method signature for this is int f(int N, List<Integer> A)

## Ruby, 52 48 46 bytes

->b{b[s=0].times{|x|b.find{|y|x%y<1&&s+=x}};s}


# C11, 177 bytes

#include"object.h"
#define S size_t
S g(S m,array_t*d){S s,i,l,j;for(s=i=0;i<m;i++){for(l=1,j=0;j<d->idx+1;l*=i%(S)(*array_get_ref(d,j++,NULL))->fwi->value);s+=l?0:i;}return s;}


Requires this set of headers in the same folder, and the fnv-hash library found there as well. Compile like gcc 1.c ../fnv-hash/libfnv.a -o 1 -DNODEBUG

Test Program:

#include "../calc/object/object.h"
#include <stdio.h>

size_t f (const size_t max, const size_t a, const size_t b);
size_t f2 (const size_t max, const array_t* const divs);
size_t g (size_t max, array_t* divs);

define_array_new_fromctype(size_t);

int main(void) {
printf("%zu\n", f(10, 3, 5));
static const size_t a[] = {
3, 5
};
array_t* b = array_new_from_size_t_lit(a, 2, t_realuint);
printf("%zu\n", f2(10, b));
printf("%zu\n", g(10, b));
array_destruct(b);
return 0;
}

size_t f (const size_t max, const size_t a, const size_t b) {
size_t sum = 0;
for (size_t i = 0; i < max; i++) {
sum += (i % a * i % b) ? 0 : i;
}
return sum;
}

size_t f2 (const size_t max, const array_t* const divs) {
size_t sum = 0;
const size_t len = array_length(divs);

for (size_t i = 0; i < max; i++) {
size_t mul = 1;
for (size_t j = 0; j < len; j++) {
object_t** this = array_get_ref(divs, j, NULL);

fixwid_t*   num = (*this)->fwi;

mul *= i % (size_t) num->value;
}
sum += mul ? 0 : i;
}
return sum;
}

#define S size_t
S g(S m,array_t*d){S s,i,l,j;for(s=i=0;i<m;i++){for(l=1,j=0;j<d->idx+1;l*=i%(S)(*array_get_ref(d,j++,NULL))->fwi->value);s+=l?0:i;}return s;}


outputs

23
23
23


# Whispers v2, 178 bytes

> Input
> Input
> ℕ
>> (1)
>> ∤L
>> {L}
>> L∩2
>> #L
>> L∈3
>> L⋅R
>> Each 5 4
>> Each 6 11
>> Each 7 12
>> Each 8 13
>> Each 9 14
>> Each 10 15 4
>> ∑16
>> Output 17


Try it online!

Structure tree:

## How it works

Very simply, we put each number (the lines with Each on them) through a series of functions (the lines with L on them), then, based off the results of those functions, we discard some numbers and keep the rest, before finally summing them. In fact, we can define those functions, where $$\\alpha\$$ denotes the set of numbers given as input:

\begin{align} f(x) & = \{i \: | \: (i|x), i \in \mathbb{N}\} & \text{i.e. the set of divisors of} \: x \\ g(x) & = f(x) \cup \alpha & \text{i.e. the union of the divisors of} \: x \: \text{with} \: \alpha \\ h(x) & = |g(x)| > 0 & \text{i.e.} \: g(x) \: \text{is not empty} \end{align}

This is what lines 5 through to 10 represent. Lines 11 through 16 are simply the application of those three functions. Once we've defined all the functions, we then mutate $$\\alpha\$$ to $$\\beta\$$ according to the following rule:

$$\beta_i = \begin{cases} \alpha_i & h(\alpha_i) \: \top \\ 0 & h(\alpha_i) \: \bot \end{cases}$$

where $$\\alpha_i\$$ denotes the $$\i\$$th element of $$\\alpha\$$, and the same for $$\\beta\$$. Finally, we can simply take the sum of $$\\beta\$$, as the $$\0\$$ elements do not affect the sum.

# K (oK), 15 14 bytes

Solution:

{+/&|/~y!\:!x}


Try it online!

Examples:

{+/&|/~y!\:!x}[50;,2]
600
{+/&|/~y!\:!x}[10;3 5]
23


Explanation:

{+/&|/~y!\:!x} / the solution
{            } / lambda taking implicit x and y
!x  / range 0..x-1
y!\:    / modulo (!) x with each-left (\:) item in y
~        / not
|/         / min-over to flatten into single list
&           / indices where true
+/            / sum up
`