# 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? Commented 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? Commented 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
Commented Dec 19, 2016 at 3:58
• Can we take "numbers equal to or below 10", or take 9 as input instead of 10? Commented Dec 19, 2016 at 7:41
• "and a set of at least one positive integer A" how big can the set be? Commented Dec 19, 2016 at 7:41

# 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)

# 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


# Pip, 12 bytes

$+Y0N_%gFI,q  Try it online! ### Explanation Uses a somewhat unusual input method: takes N from stdin and the set of divisors as command-line args. $+Y0N_%gFI,q
g is list of command-line args (implicit)
q  Read a line of stdin
,   Range from 0 up to one less than that value
FI    Filter on this function:
_         Take each element
%g       mod the list of divisors g
0N          Check if zero is in the result list: some number in g divides the element exactly
Result: a list of the numbers that are a multiple of one of the set of divisors
Y           Yank (no-op to manipulate operator precedence)

# Scala, 45 41 bytes

s=>0 to _-1 filter(x=>s.exists(x%_<1))sum


Try it in Scastie

Takes as its input a List[Int] s and an Int, creates a range from 0 to that number, filters every number in that range that's divisible by an element in s, and sums it.

Requires language:postfixOps.

# Vyxals, 5 bytes

ɽ'⁰Ḋa


Try it online!

Explanation:

ɽ      # Range 1 to n-1
'     # Keep those that are
Ḋ   #   Divisible by
a  #   Any of
⁰    #   The second input
# Sum with the s flag


# Thunno 2S, 5 bytes

Læ¹ḊS


Try it online!

## Thunno 2S, 6 bytes

LsȷḊʂV


Try it online!

#### Explanations

Læ¹ḊS   # Implicit input           ->  [2,3,5], 50
L       # Lowered range            ->  [2,3,5], [0..49]
æ      # Filtered by:             ->     0       1    ...   48      49
¹Ḋ    #  Divisible by 2nd input  ->  [1,1,1] [0,0,0]     [1,1,0] [0,0,0]
S   #  Sum (any are true)      ->     3       0    ...    2       0
# (End filter)             ->  [0,2,3,4,5,...,42,44,45,46,48]
# (S flag) Sum the list    ->  857
# Implicit output

LsȷḊʂV  # Implicit input
#   [2,3,5], 50
L       # Take the lowered range of the first input
#   [2,3,5], [0..49]
s      # Swap the two values on the stack
#   [0..49], [2,3,5]
ȷḊ    # Outer product over divisibility check
#   [[0%2==0, 0%3==0, 0%5==0], ..., [49%2==0, 49%3==0, 49%5==0]]
#   [[1,1,1], [0,0,0], [1,0,0], ..., [0,0,0], [1,1,0], [0,0,0]]
ʂ   # Sum each inner list (check if any are true)
#   [3,0,1,1,1,...,2,1,0,2,0]
V  # Get the indices of truthy (non-zero) items
#   [0,2,3,4,5,...,42,44,45,46,48]
# (S flag) Sum the resulting list
#   857
# Implicit output


# Julia 1.0, 31 bytes

N^A=sum(x->any(@.x%A<1)x,1:N-1)


Try it online!

The function sum can accept a subfunction to be called on each element before summation. I use this to multiply each element x in the range $$\[1, N-1]\$$ by the boolean value any(@.x%A<1), essentially filtering the range. Julia supports logical indexing for arrays, but this generally requires defining the array first, which often isn't ideal for code golf.

The expression @. vectorizes the functions that follow, but in this case, it doesn't save any bytes over the alternative, x.%A.<1.

-1 byte thanks to MarcMush: use the result of any as a literal coefficient

• any(...)x should work for -1 byte Commented Aug 27, 2023 at 19:18

# Processing, 88 bytes

int q(int a,int[]b){int s=0,i=0;for(;++i<a;)for(int j:b)if(i%j<1){s+=i;break;}return s;}


Uses the simple for-loop approach, sums all the multiples up and returns it. Input is the format int, int[]array.

• Isn't it simpler to just name it java? Commented Aug 12, 2020 at 14:39

# J, 18 bytes

[:+/@I.0=*/@(|/i.)


Try it online!

## Explanation

[:+/@I.0=*/@(|/i.)  Input: A (LHS), N (RHS)
i.   Make the range [0, 1, ..., n-1]
|/     Form the modulus table between each value in A and the range N
*/@(    )  Reduce columns by multiplication
0=           Test if each value if equal to 0, 1 if true else 0
[:   I.             Find the indicies of 1s
+/@               Reduce by addition and return


# PHP, 80 bytes

for($c=1;++$i<$argv[1];$c++?:$t+=$i)for($j=1;$v=$argv[++$j];$i%$v?:$c=0);echo$t;


Run from command line with -r. First argument is the limit N, any subsequent arguments are our positive integers A.

Our outer loop goes through the range 1..N, while the inner loop goes through each value of A and checks to see if $i is a multiple of it. If it is, we set a flag that tells our outer loop to add $i to our total ($t). We use a flag so that we don't add $i more than once. We then output our total at the end.

Clojure, 44 bytes

#(apply +(set(mapcat(partial range 0 %)%2)))


Instead of generating the whole range form 0 to N it is generating values on that range with step length of A_0, A_1, etc. and uses set to get unique values.

Calling convention:

(def f #(apply +(set(mapcat(partial range 0 %)%2))))
(f 50 [2 3 5])


Steps are more clear when ->> macro is used:

(defn f [N A] (->> A (mapcat #(range 0 N %)) set (apply +)))


Python 3 & 2.7, 55 bytes

Based on the same set idea as my Clojure version.

lambda N,A:sum(set(i for a in A for i in range(0,N,a)))


## Batch, 110 bytes

@set t=-%1
@for /l %%i in (1,1,%1)do @set p=1&(for %%e in (%*)do @set/ap*=%%e%%%%i)&set/at+=%%i*!p
@echo %t%


Takes input as command-line arguments; the first argument is n, the rest are the set of numbers. Works by computing the product of the remainders of all numbers up to and including n with each of the arguments including n itself and summing those numbers with a zero product; this causes n to always be included in the total so we offset that by starting the total at -n.

# C#, 92 bytes

n=>{int i=0,j,s=0;for(;i<n[0];i++)for(j=1;j<n.Length;)if(i%n[j++]<1){s+=i;break;}return s;};


Anonymous function which receives an array containing the upper limit and all required divisors.

This method does not use a set (actually HashSet in C#) since it was way too verbose. Not that this code is too succinct...

Full program and test cases:

using System;

public class Program
{
public static void Main()
{
Func<int[], int> f =
n =>
{
int i = 0, j, s = 0;
for ( ; i < n[0] ; i++)
for (j = 1 ; j < n.Length ; )
if (i % n[j++] < 1)
{
s += i;
break;
}
return s;
};

// test cases:
Console.WriteLine(f(new int[]{50, 2})); // 600
Console.WriteLine(f(new int[]{10, 3, 5}));  // 23
Console.WriteLine(f(new int[]{28, 4, 2}));  // 182
Console.WriteLine(f(new int[]{19, 7, 5}));  // 51
Console.WriteLine(f(new int[]{50, 2, 3, 5}));   // 857
}
}


## awk, 64 bytes

{for(;i++<NF;j=0)while((c=$i*++j)&&c<$NF)a[c];for(i in a)$0+=i}1  Write the code to file program.awk and execute: $ echo run 2 3 5 50 | awk -f this.awk
857


run is a cludge to allow using record $0 for summing and shorter printing, emphasis on the latter. Try it online ## R, 39 bytes z=2:N-1;z%*%!!rowSums(!outer(z,X,"%%"))  N is the number, X is a vector of divisors ## Racket 94 bytes (apply +(remove-duplicates(for*/list((i(range 1(car l)))(j(cdr l))#:when(= 0(modulo i j)))i)))  Ungolfed: (define (f l) (apply + (remove-duplicates (for*/list ((i (range 1 (first l))) (j (rest l)) #:when (= 0 (modulo i j))) i))))  Testing: (f '(10 3 5)) (f '(50 2)) (f '(28 4 2)) (f '(19 7 5)) (f '(50 2 3 5))  Output: 23 600 182 51 857  # Perl 5-pa, 44 bytes map{$"="*$_%";$\+=!eval"$_%@F"&&$_}1..<>-1}{


Try it online!

Takes the list of A on the first line of input, space separated. Takes N on the second line.

# APL(NARS), 17 chars, 34 bytes

{+/∪⍺∼⍨∊⍵×⍳¨⌊⍺÷⍵}


test:

  f←{+/∪⍺∼⍨∊⍵×⍳¨⌊⍺÷⍵}
50 f 2
600
10 f 3 5
23
28 f 4 2
182
19 f 7 5
51
50 f 2 3 5
857


# Headass, 74 bytes

{N)OUO}:+E.UO^UO[{UON)}:](D)RP:N+E.U+O-[UOU{R)U-ORO^:R-OUO;UN)}:D)R:R];ONE


Try It Online! - Input is taken as a newline delimited list of numbers, with the first one being N, and the rest being the values of A

tattoo on my forehead that says I LOVE EASY CHALLENGES

## Explanation

PREAMBLE: this program counts up from 0 to N, with this increasing value being
referred to as the "counter". along the way it reads members of A, which
will be given "countdown timers", which start at 0 and are reset to the
associated A member value minus one, so that every A[i]th cycle, they reach
0 and trigger the adding of the counter to the accumulator.
The accumulator, of course, accumulatizes.

{N)OUO}:+E.  code block 0 (initialization)
{N)   }:     for each input
OUO         save 0, save input
this inits the counter, stores N,
creates a list of countdown timers starting at 0
and implicitly, an accumulator starting at 0
all on the queue. the queue now looks like this:
0 N 0 A1 0 A2 0 A3... 0
+E   go to code block 1
.  end code block

UO^UO[{UON)}:](D)RP:N+E.  code block 1 (checking if we're done)
UO^                       set r1 to the counter value
UO[                    set r2 to N
{UON)}:             put the rest of the values back on the queue,
noting that the accumulator is the last value
](D)         if r1 == r2 (the counter has reached N)
RP         print the last value added to the queue
(which is the accumulator)
(and halt)
:      else
N+E     go to code block 2
.  end code block

U+O-[UOU{R)U-ORO^:R-OUO;UN)}:D)R:R];ONE  code block 2
U+O                                      put the counter + 1 onto the queue
U+ -[                                    set r2 to the counter value
UO                                  put N back on the queue
{                N)}:            for each member of A
U R)             U                  if the countdown timer has reached 0
U-O                               reset the countdown timer
RO                             put the A member back on the queue
^                            raise a flag in r1
:                         else
R-O                        decrement the countdown timer
UO                      put the A member back on the queue
;                   endif
D)          if the flag in r1 is down
R:  ;O      put the accumulator back on the queue
:        else
R];O      increase the accumulator by the
value of the counter

Also, registers r0-r3 are reset between code blocks, so you can basically think about them as local variables in each code block. Register r0 is constantly in use but not mentioned due to the language structure, and register r3 is in use whenever ( or ) show up, but it's much easier to abstract these to simple comparisons, since that's all they're used for in this program.