43
\$\begingroup\$

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
\$\endgroup\$
5
  • 6
    \$\begingroup\$ 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? \$\endgroup\$
    – Wheat Wizard
    Dec 19, 2016 at 3:48
  • 3
    \$\begingroup\$ Can you give some test cases? Obviously don't post the answer to the PE one, but what about other examples? \$\endgroup\$
    – Riker
    Dec 19, 2016 at 3:55
  • 1
    \$\begingroup\$ @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? \$\endgroup\$
    – smls
    Dec 19, 2016 at 3:58
  • 1
    \$\begingroup\$ Can we take "numbers equal to or below 10", or take 9 as input instead of 10? \$\endgroup\$ Dec 19, 2016 at 7:41
  • \$\begingroup\$ "and a set of at least one positive integer A" how big can the set be? \$\endgroup\$
    – betseg
    Dec 19, 2016 at 7:41

56 Answers 56

1
2
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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:

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

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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)
$+            Fold on addition
\$\endgroup\$
1
\$\begingroup\$

Io, 63 bytes

Port of NikoNyrh's answer.

method(N,A,A map(i,Range 0toBy(N-1,i)asList)flatten unique sum)

Try it online!

Explanation

method(N,A,                                                   ) // Take two inputs, the number and the array
           A map(i,                        )                    // For each item in the array A:
                   Range 0toBy(N-1,i)                           //     Generate a range from 0 to N-1, with the step of i
                                     asList                     //     Convert it to a list
                                            flatten             // Flatten the lists
                                                    unique      // Uniquify them
                                                           sum  // Sum the resulting list
\$\endgroup\$
1
\$\begingroup\$

Arn, 15 bytes

pIÔX╗▀‹·¬○¯vËa?

Explained

Unpacked: +\$v{$:{!v%}?1}1->

  \ Fold with...
+ ...addition
    $ Filter with...
      v{ ...block with key of v
        $: Any operation
          { Block with key of _
            ! Boolean not
              v% v modulo _ (implied)
          }
          ?1 Each element on second line of _ (implied)
        }
        1-> Range, [1, _)

When passing an array in string or integer context, Arn will automatically take the 0th element. When passing a string/integer in array context, Arn will split on spaces if there are any or every character otherwise.

STDIN is initialized to the _ variable, split on newlines if there are any or just a string if one line.

Originally I had +\$v{$:{0=v%}?1}1->, which was 1 byte longer.

\$\endgroup\$
0
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Vyxal s, 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
\$\endgroup\$
1
\$\begingroup\$

Thunno 2 S, 5 bytes

Læ¹ḊS

Try it online!

Thunno 2 S, 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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ any(...)x should work for -1 byte \$\endgroup\$
    – MarcMush
    Aug 27, 2023 at 19:18
0
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Isn't it simpler to just name it java? \$\endgroup\$
    – Razetime
    Aug 12, 2020 at 14:39
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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 +)))
\$\endgroup\$
0
\$\begingroup\$

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)))
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
    }
}
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

R, 39 bytes

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

N is the number, X is a vector of divisors

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
                                     NE  return to code block 1

There's a bunch of implicit re-adding of values to the queue that I don't mention, basically any time I say that I've modified some value, that means I'm saving the modified version to the queue.

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.

I'm still always learning the best way to explain this language, trying to balance between overexplaining and overabstracting, if anyone has any questions of course feel free to ask, you may have a golf on your hands :P

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.