Suchen Sie die Summe aller Zahlen unter n, die ein Vielfaches einiger Zahlen sind

31

Fast gleichbedeutend mit der ersten Frage von Project Euler:

Wenn wir alle natürlichen Zahlen unter 10 auflisten, die Vielfache von 3 oder 5 sind, erhalten wir 3, 5, 6 und 9. Die Summe dieser Vielfachen ist 23.

Ermitteln Sie die Summe aller Vielfachen von 3 oder 5 unter 1000.

Herausforderung:

Bei einer positiven Ganzzahl Nund einer Menge von mindestens einer positiven Ganzzahl Awird die Summe aller positiven Ganzzahlen ausgegeben, die kleiner als Ndas Vielfache von mindestens einem Element von sind A.

Für den Projekt-Euler-Fall wäre die Eingabe beispielsweise:

1000
3
5

Testfälle:

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
Cisplatin
quelle
4
1) Zählen wir Zahlen, die ein Vielfaches von beiden sind, zweimal? 2) Können wir nur zwei andere Zahlen bekommen? oder irgendein Betrag sagt eins oder 3?
Weizen-Assistent
3
Können Sie einige Testfälle geben? Posten Sie die Antwort natürlich nicht auf die PE, aber was ist mit anderen Beispielen?
Freitag,
1
@WheatWizard: Das Wort "oder" bedeutet, dass jede Zahl höchstens einmal gezählt wird. Ich stimme zu, dass die Frage deutlich machen muss, wie viele "Zahlen auf Vielfache von" Argumenten überprüft werden müssen. Genau zwei? Ein oder mehr? Null oder mehr?
smls
1
Können wir " Zahlen gleich oder unter 10 " nehmen oder 9 anstelle von 10 als Eingabe verwenden?
Stewie Griffin
"und eine Menge von mindestens einer positiven ganzen Zahl A" Wie groß kann die Menge sein?
Betseg

Antworten:

13

Gelee , 6 Bytes

ḍþṖḅTS

Probieren Sie es online!

Wie es funktioniert

ḍþṖḅ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.
Dennis
quelle
3
Natürlich muss @Dennis etwas mitbringen, das dich fragen lässt, was du auf ppcg machst
Grajdeanu Alex.
8

Python, 59-55 Bytes

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

repl.it

Unbenannte Funktion mit einer Ganzzahl nund einer Liste von Ganzzahlen l. Durchläuft einen Bereich der Natural-Zahlen (plus Null) bis einschließlich nund summiert ( sum(...)) diejenigen, die nach Division von Null ( v%m<1) für anydie Ganzzahlen min der Liste einen Rest haben l. Verwendet Multiplikation anstelle einer Bedingung, um 3 Bytes zu sparen.

Jonathan Allan
quelle
8

Oktave, 38 36 33 Bytes

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

Nehmen Eingang als: f(10, [3;5]). Dies wäre 2 Byte kürzer, wenn die Eingabe f(9,[3;5])für denselben Testfall erfolgen könnte.

Überprüfen Sie hier alle Testfälle.


Erläuterung:

@(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 kann vorab dekrementiert werden, also mit 1:--x statt 1:x-1(zweimal) verwenden, werden zwei Bytes gespeichert.

mod(a,b)gibt 1 2 0 1 2 0 1 2 0für mod(1:9,3). Wenn das zweite Argument ein vertikaler Vektor ist, wird die erste Eingabe vertikal repliziert und der Modul für jeden der Werte im zweiten Eingabeargument verwendet. Also zur Eingabemod(1:9, [3;5]) ergibt sich also:

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

Wenn Sie ~all(_,1)dies annehmen, erhalten Sie truefür die Spalten, in denen mindestens ein Wert Null ist, undfalse denen alle Werte ungleich Null sind:

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

Das ,1 wird benötigt, falls nur eine Nummer eingegeben wurde y. Andernfalls würde es auf den gesamten Vektor anstatt auf Nummer für Nummer wirken.

Wenn Sie dies in eine vertikale Matrix umwandeln und die Matrixmultiplikation verwenden, erhalten Sie die richtige Antwort, ohne dass eine explizite Summierung erforderlich ist:

Stewie Griffin
quelle
Oh, das ist grausam: Ich musste 2 Bytes hinzufügen, weil zwischen x und x – 1 ein Unterschied bestand, aber Sie mussten 4 Bytes hinzufügen, und jetzt bin ich 1 Byte voraus> :)
Greg Martin
6

JavaScript (ES6), 40 39 36 Byte

Eingabe: Integer nund Array von Integer (s) amit aktueller Syntax(n)(a)

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

Testfälle

Arnauld
quelle
Ich hatte eine etwas andere Formulierung für die gleiche Länge: f=(n,a)=>n--&&a.some(v=>n%v<1)*n+f(n,a). Das Beste, was ich nicht rekursiv machen konnte, waren 61 Bytes.
Neil
@Neil Ihr Kommentar hat mich ermutigt, nach einer weiteren Formulierung zu suchen. Interessanterweise spart die aktuelle Syntax 3 Bytes.
Arnauld
5

MATL , 9 Bytes

q:ti\~*us

Probieren Sie es online!

Luis Mendo
quelle
1
Ich überprüfe nur, ob ich das richtig gelesen habe (ohne die Dokumente zu überprüfen). Sie dekrementieren und erstellen einen Vektor 1 2 .... Du duplizierst es und nimmst Modul für den anderen Eingang. Sie negieren es und multiplizieren mit dem Vektor 1 2 .., verwenden Unique, um Duplikate loszuwerden und es schließlich zu summieren ...
Stewie Griffin
Genau! Ich bin auf dem Handy und habe daher keine Erklärung angegeben. Jetzt ist es nicht nötig :-)
Luis Mendo
5

Retina , 34 Bytes

Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.

\d+
$*
M&!`(.+)\1*(?=1¶.*\b\1\b)
1

Eingabeformat ist

50
2,3,5

Probieren Sie es online!

Martin Ender
quelle
4

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.

Rɪᴋᴇʀ
quelle
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
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.
Jonathan Allan
@JonathanAllan cool, thanks a lot!
Freitag,
4

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)]&
Greg Martin
quelle
1
Range is listable: Tr[Union@@Range[#2,#-1,#2]]& (and then save another byte by swapping the order of the inputs)
Martin Ender
4

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.
smls
quelle
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"
Brad Gilbert b2gills
@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
PS: I removed the phrase "implicitly declared" now, though, as it's not necessary for understanding the code.
smls
3

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.

JAD
quelle
3

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

Angs
quelle
(x`mod`) is the same as mod x.
Zgarb
@Zgarb whoops :)
Angs
3

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
Osable
quelle
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.)
Kevin Cruijssen
3

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

rahnema1
quelle
1
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 :-)
Stewie Griffin
I changed the order of the input, but here's a link ideone.com/8Bljrl
Stewie Griffin
2

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

quelle
2

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

t-clausen.dk
quelle
2

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
J. Sallé
quelle
2

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
Kenneth Taylor
quelle
whoops! I read too fast
Kenneth Taylor
Much better. Great answer!
mbomb007
1

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
Theo
quelle
You could do x,y,z=input() and give input in the form of (1000,3,5).
Skyler
1

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))
coredump
quelle
1

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.

AdmBorkBork
quelle
1

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.

Titus
quelle
1

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.

sprague44
quelle
1

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)

NonlinearFruit
quelle
1

Ruby, 52 48 46 bytes

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

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
cat
quelle
1

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
Shaggy
quelle
1

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 α denotes the set of numbers given as input:

f(x)={i|(i|x),iN}i.e. the set of divisors ofxg(x)=f(x)αi.e. the union of the divisors ofxwithαh(x)=|g(x)|>0i.e.g(x)is not empty

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 α to β according to the following rule:

βi={αih(αi)0h(αi)

where αi denotes the ith element of α, and the same for β. Finally, we can simply take the sum of β, as the 0 elements do not affect the sum.

caird coinheringaahing
quelle
1

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
streetster
quelle
0

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
Mego
quelle
0

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.

Kritixi Lithos
quelle