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

Question

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

Answer 1

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.

Answer 2

Octave, 38 36 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:

Answer 3

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.

Answer 4

JavaScript (ES6), 40 39 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

Answer 5

MATL, 9 bytes

q:ti\~*us

Try it online!

Answer 6

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!

Answer 7

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

(Try it online.)

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.

Answer 8

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.

Answer 9

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)]&

Answer 10

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

Answer 11

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.

Answer 12

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

Answer 13

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

Answer 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

Answer 15

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

Answer 16

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

Answer 17

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

Answer 18

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

Answer 19

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

Answer 20

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.

Answer 21

PHP, 78 76 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.

Answer 22

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.

Answer 23

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)

Answer 24

Ruby, 52 48 46 bytes

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

Answer 25

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

Answer 26

Japt -x, 9 7 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

Answer 27

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.

Answer 28

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

Answer 29

Actually, 13 bytes

DR∙`i;)%Y*`MΣ

Try it online!

Explanation:

DR∙`i;)%Y*`MΣ
DR             range(1, N)
  ∙            Cartesian product with A
   `i;)%Y*`M   for each pair:
    i;)          flatten, make a copy of the value from the range
       %Y        test if value from range divides value from A
         *       value from range if above is true else 0
            Σ  sum

Answer 30

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.

Answer 31

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

Answer 32

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.

Answer 33

R, 39 bytes

z=2:N-1;z%*%!!rowSums(!outer(z,X,"%%"))

N is the number, X is a vector of divisors

Answer 34

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

Answer 35

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

Answer 36

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.

Answer 37

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
    }
}

Answer 38

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

Answer 39

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

Answer 40

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

Answer 41

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.