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

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

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 11

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 12

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 13

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 14

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 15

Japt -fx, 9 7 6 4 bytes

VøUâ

Try it

Answer 16

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 17

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 18

Ruby, 52 48 46 bytes

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

Answer 19

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 20

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 - A₁, A₂, ...

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

Answer 21

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 
C3          RET                         ; return to caller

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)

Answer 22

Fig, \$11\log_{256}(96)\approx\$ 9.054 bytes

VxSFrx'!A%v

-8.232 bytes thanks to @Sʨɠɠan

Try it online!

Explanation:

Vx           # Set the register to the first input (the list)
    rx       # Range [0, n)
   F  '      # Filter:
         %   #   Modulo
          v  #   The register
        A    #   All truthy
       !     #   Logical not
  S          # Sum

Answer 23

Pyt, 9 bytes

⁻řĐ←ΠǤ1>·

Try it online!

⁻ř            implicit input (N); decrement and push [1,2,...,N-1]
  Đ           duplicate top of stack
   ←Π         get the product of the members of A
     Ǥ        GCD (elementwise)
      1>      is each GCD greater than 1?
        ·     dot product; implicit print

Answer 24

Nekomata, 7 bytes

ᵒ%ᵐ∏¬x∙

Attempt This Online!

ᵒ%ᵐ∏¬x∙
ᵒ%          Generate a modulo table
  ᵐ∏        Take product of each row
    ¬       Logical not
     x∙     Dot product with range from 0 to length - 1

Answer 25

Rust, 52 bytes

|n,v|(1..n).filter(|e|v.iter().any(|x|e%x==0)).sum()

Rust Playground

Answer 26

Itr, 13 bytes

#º#Xáà%¬*«ÍÌS

online interpreter

Explanation

#              ; read the number
 º             ; convert it to a zero-based range
  #            ; read the list of numbers
   ×     «     ; execute for each pair of numbers in the input
    áà         ; duplicate the lower number in the pair 
      %¬       ; check for divisibility
        *      ; keep the number if it is divisible
         ÍÌ    ; uniquify the list
           S   ; sum up the elements

---

Itr, 11 bytes

using implicit IO

ºXâà%¬*«ÍÌS

Answer 27

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 28

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 29

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 30

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.