Encuentre la suma de todos los números debajo de n que son múltiplos de algún conjunto de números

31

Casi equivalente a la primera pregunta del Proyecto Euler:

Si enumeramos todos los números naturales por debajo de 10 que son múltiplos de 3 o 5, obtenemos 3, 5, 6 y 9. La suma de estos múltiplos es 23.

Encuentra la suma de todos los múltiplos de 3 o 5 por debajo de 1000.

Reto:

Dado un entero positivo Ny un conjunto de al menos un entero positivo A, genera la suma de todos los enteros positivos menores Nque son múltiplos de al menos un miembro de A.

Por ejemplo, para el caso del Proyecto Euler, la entrada sería:

1000
3
5

Casos de prueba:

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
Cisplatino
fuente
44
1) ¿Contamos los números que son múltiplos de ambos dos veces? 2) ¿Podemos obtener solo otros dos números? o cualquier cantidad digamos uno o 3?
Wheat Wizard
3
¿Puedes dar algunos casos de prueba? Obviamente no publique la respuesta a la PE, pero ¿qué pasa con otros ejemplos?
Rɪᴋᴇʀ
1
@WheatWizard: la palabra "o" implica que cada número se cuenta solo una vez, como máximo. Sin embargo, estoy de acuerdo en que la pregunta debe dejar en claro cuántos argumentos "números para verificar múltiplos de" deben ser compatibles. ¿Exactamente dos? ¿Uno o mas? Cero o más?
sonríe el
1
¿Podemos tomar " números iguales o inferiores a 10 ", o tomar 9 como entrada en lugar de 10?
Stewie Griffin
"y un conjunto de al menos un entero positivo A" ¿qué tan grande puede ser el conjunto?
betseg

Respuestas:

13

Jalea , 6 bytes

ḍþṖḅTS

Pruébalo en línea!

Cómo funciona

ḍþṖḅ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
fuente
3
Por supuesto, @Dennis tiene que venir con algo que te hará preguntarte qué estás haciendo en ppcg
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

Función sin nombre que toma un entero ny una lista de enteros l. Atraviesa un rango de los números naturales (más cero) hasta, pero sin incluir, ny suma ( sum(...)) aquellos que tienen un resto después de la división de cero ( v%m<1) para anylos enteros men la lista l. Utiliza la multiplicación en lugar de un condicional para guardar 3 bytes.

Jonathan Allan
fuente
8

Octava, 38 36 33 bytes

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

Toma de entrada como: f(10, [3;5]). Esto sería 2 bytes más corto si la entrada pudiera serf(9,[3;5]) para el mismo caso de prueba.

Verifique todos los casos de prueba aquí.


Explicación:

@(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 puede disminuir previamente, por lo que usar en 1:--xlugar de1:x-1 (dos veces) ahorra dos bytes.

mod(a,b)da 1 2 0 1 2 0 1 2 0por mod(1:9,3). Si el segundo argumento es un vector vertical, replicará la primera entrada verticalmente y tomará el módulo para cada uno de los valores en el segundo argumento de entrada. Entonces, para la entrada mod(1:9, [3;5])esto da:

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

Asumir ~all(_,1)esto da truepara las columnas donde al menos un valor es cero, y falsedonde todos los valores son distintos de cero:

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

Se ,1necesita en caso de que solo haya un número eny . De lo contrario, actuaría en todo el vector en lugar de número por número.

Transponer esto a una matriz vertical y usar multiplicación matricial, nos dará la respuesta correcta, sin la necesidad de una suma explícita:

Stewie Griffin
fuente
Oh, eso es cruel: tuve que agregar 2 bytes debido a la diferencia entre x y x – 1, pero tenía que agregar 4 bytes, y ahora estoy adelante por 1 byte> :)
Greg Martin
6

JavaScript (ES6), 40 39 36 bytes

Entrada: entero ny conjunto de enteros acon sintaxis de curry(n)(a)

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

Casos de prueba

Arnauld
fuente
Tenía una formulación ligeramente diferente para la misma longitud: f=(n,a)=>n--&&a.some(v=>n%v<1)*n+f(n,a). Lo mejor que pude hacer de forma no recursiva fue 61 bytes.
Neil
@Neil Su comentario me animó a buscar otra formulación más. Curiosamente, la sintaxis de curry ahorra 3 bytes.
Arnauld
5

MATL , 9 bytes

q:ti\~*us

Pruébalo en línea!

Luis Mendo
fuente
1
Solo verifico si leí esto bien (sin consultar los documentos). Estás decrementando, creando un vector 1 2 .... Lo duplica y toma el módulo de la otra entrada. Lo niegas y multiplicas con el vector 1 2 .., lo usas para deshacerte de los duplicados y finalmente lo sumas ...
Stewie Griffin
¡Exactamente! Estoy en el móvil, así que no incluí una explicación. Ahora no es necesario :-)
Luis Mendo
5

Retina , 34 bytes

El recuento de bytes asume la codificación ISO 8859-1.

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

El formato de entrada es

50
2,3,5

Pruébalo en línea!

Martin Ender
fuente
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

Después de escribir esto, noté que mi código era similar a la respuesta existente de Python, sin embargo, se me ocurrió de forma independiente y lo estoy publicando de todos modos.

Rɪᴋᴇʀ
fuente
No necesita el punto y coma en el ejecutivo, ya que tiene un salto de línea después de todos modos. ¡Sabía que mi respuesta podría ser superada!
Theo
La especificación dice "un conjunto de al menos un entero positivo"; esto parece manejar solo el caso donde el conjunto es dos enteros. También tener x=y=0en una línea separada ahorraría cuatro bytes.
Jonathan Allan
@JonathanAllan genial, muchas gracias!
Rɪᴋᴇʀ
4

Mathematica, 37 27 bytes

¡Gracias a Martin Ender por una observación astuta que condujo a grandes ahorros de bytes!

Tr[Union@@Range[#,#2-1,#]]&

Función sin nombre que toma dos argumentos, una lista # de enteros (los divisores deseados A) y un entero #2(el límite superior N), y devuelve un entero. Range[#,#2-1,#]da, para cada elemento dde la lista #, todos los múltiplos de dmenor o igual que #-1(por lo tanto, menor que #); La unión de estas listas se calcula y se suma con Tr.

Versión previa:

Tr[x=#;Union@@(Range[#,x-1,#]&/@#2)]&
Greg Martin
fuente
1
Rangees listable: Tr[Union@@Range[#2,#-1,#2]]&(y luego guarda otro byte intercambiando el orden de las entradas)
Martin Ender
4

Perl 6 , 25 bytes

{sum grep *%%@_.any,^$^a}

Una lambda que toma los números de entrada como argumentos. (Un argumento para N, y un número arbitrario de argumentos para A).

( Pruébelo en línea. )

Explicación:

  • { ... }: Una lambda.
  • $^a: Primer argumento de la lambda.
  • @_: Argumentos restantes de la lambda ("parámetro variadic").
  • ^$^a: Rango de 0a $^a - 1.
  • * %% @_.any: Otra lambda, que prueba su argumento *usando el operador divisible por %%contra un any- Unión de la lista @_.
  • grep PREDICATE, RANGE: itera el rango de números y devuelve aquellos para los cuales el predicado es verdadero.
smls
fuente
Creo que agregar ^para declarar un parámetro de marcador de posición es bastante explícito. Especialmente porque podrías usarlo más tarde en el bloque como solo $a. Creo que solo $_ @_ %_ selfse puede considerar que se declara implícitamente. Creo que debería leer esa línea " declarar el primer parámetro como marcador de posición "
Brad Gilbert b2gills
@ BradGilbertb2gills: Quise decir que implícitamente se convierte en parte de la firma de la lambda, a pesar de que el código no introdujo una firma antes del cuerpo de la lambda. @_, y %_en el caso de las funciones, no son diferentes en ese sentido: ellos también solo se convierten en parte de la firma si aparecen en el cuerpo. Sólo $_ (y selfy %_en los métodos) puede llegar a ser parte de una firma por defecto.
sonríe el
PD: ahora eliminé la frase "declarada implícitamente", ya que no es necesaria para entender el código.
sonríe el
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))

Toma un vector de STDIN en el siguiente formato: [N, a_1, a_2, ...]. Soporta cualquier cantidad de a. Para cada uno a, se crea la secuencia aa N-1con tamaño de paso a. Luego toma la suma de todas las entradas únicas en ese vector.

JAD
fuente
3

Haskell, 42 39 bytes

a!b=sum[x|x<-[1..a-1],any((<1).mod x)b]

Uso:

Main> 50![2,3,5]
857

Gracias a @Zgarb por 3 bytes

Angs
fuente
(x`mod`)es el mismo que mod x.
Zgarb
@Zgarb whoops :)
Angs
3

05AB1E , 9 bytes

FND²%P_*O

Pruébalo en línea!

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
fuente
Alternativa de 8 bytes o 8 bytes usando un filtro . (Sin embargo, el primer 8-byter no fue posible cuando publicaste tu respuesta. Dado que à(máximo) aparece en la lista ahora, pero no antes)
Kevin Cruijssen
3

Octava, 49 37 bytes

@(A,N)sum(unique((z=(1:N)'.*A)(z<N)))

la función se llamará como f([2 3 4],50)

Supongamos que A=[2 3 4];necesitamos tener una suma de números como

sum(
2,4,6...,50-1 ,
3,6,9...,50-1,
4,8,12,...50-1)

podemos multiplicar [2 3 4]por 1:50para obtener matriz(1:N)'.*A

[2 4 6 ... 2*50
3 6 9 ... 3*50
4 8 12 ...4*50]

luego extraiga de la matriz aquellos que sean menores de 50: z(z<N)

Como hay elementos repetidos en la matriz, extraemos valores únicos y los sumamos.

respuesta anterior : (esta solución fallará si N == 1)

@(A,N)sum((k=uint64(1:N-1))(any(k==(k./A').*A')))

la función debe llamarse como f(unit64([2 3 4]),uint64(50))

rahnema1
fuente
1
¡Muy agradable! Casi tan ordenado como la otra respuesta de octava, pero un enfoque completamente diferente. ¡Esto no se me pasó por la cabeza en absoluto! Sin embargo, podría beneficiarme tener alguna explicación y tal vez un enlace a ideone, pero ya tiene mi voto :-)
Stewie Griffin
Cambié el orden de la entrada, pero aquí hay un enlace ideone.com/8Bljrl
Stewie Griffin
2

Pyth, 10 bytes

s{sm:0hQdt

Explicación

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

fuente
2

T-SQL, 87 bytes

Esto funcionará siempre que @itenga un valor de 2048 o inferior

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

Pruébalo

t-clausen.dk
fuente
2

APL (Dyalog Unicode) , 12 bytes

+/⊢∘⍳∩∘∊×∘⍳¨

Pruébalo en línea!

Función tácita anónima. Gracias a @ Adám por ayudarme a reducir 3 bytes de esto. Usos ⎕IO←0.

Cómo:

+/⊢∘⍳∩∘∊×∘⍳¨  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é
fuente
2

Pip , 43 41 39 35 bytes

b^:sFc,a{f:0Fdb{f?0c%d?0(f:i+:c)}}i

Pruébalo en línea!

Explicación:

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
fuente
whoops! Leí demasiado rápido
Kenneth Taylor
Mucho mejor. ¡Gran respuesta!
mbomb007
1

Python 2, 80 bytes

Esto es muy largo Definitivamente se puede acortar. Tomar los 3 números como entradas separadas definitivamente está afectando el puntaje.

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
fuente
Podría hacer x,y,z=input()y dar su opinión en forma de (1000,3,5).
Skyler
1

Lisp común, 77

(lambda(n x)(loop for i below n when(some(lambda(u)(zerop(mod i u)))x)sum i))

Sin golf

(lambda (limit seeds)
  (loop for i below limit
        when (some (lambda (u) (zerop (mod i u))) seeds)
          sum i))
volcado de memoria
fuente
1

PowerShell , 57 bytes

param($a,$b)(1..--$a|?{$i=$_;$b|?{!($i%$_)}})-join'+'|iex

Pruébalo en línea!

Solución iterativa. Toma la entrada como un número $ay como una matriz literal $b. Bucles de 1hasta uno a continuación $a(vía --$a), utilizando un Where-Objectoperador|?{...} con una cláusula para seleccionar ciertos números.

La cláusula se establece $icomo el número actual antes de enviar la matriz de entrada $ba otra |?{...}, aquí seleccionando aquellos elementos donde el número actual se divide de manera uniforme por al menos uno de los números en $b. Esos elementos de $beso se dividen equitativamente quedan en la tubería.

Por lo tanto, si hay al menos un elemento de $b, la tubería contiene un elemento, por lo que el exterior Wherees $truey el número actual queda en la tubería. De lo contrario, sin elementos de $bla tubería, el exterior Wherees $false, por lo que el número actual no se coloca en la tubería.

Esos números se -joinagrupan en parens, se editan junto con +signos y se canalizan a |iex(abreviatura Invoke-Expressiony similar a eval). El resultado de la suma se deja en la tubería y la salida es implícita.

AdmBorkBork
fuente
1

PHP, 78 76 74 bytes

for(;++$i<$argv[$f=$k=1];$s+=$i*!$f)for(;$v=$argv[++$k];)$f*=$i%$v;echo$s;

El bucle externo se ejecuta $idesde 1 hasta el primer argumento a continuación y se agrega $ia $ssi no$f está establecido. Los multiplica bucle interno con ( argumento módulo) para todos los argumentos posteriores, el establecimiento de si
$f$i$f0$i es el múltiplo de cualquiera de ellos.

Corre con -r.

Tito
fuente
1

Scala, 47 bytes

n=>1.to(n(0)-1).filter(i=>n.exists(i%_==0)).sum

n es una lista que contiene un primer argumento N, el resto son elementos deA

Funciona filtrando los números donde no existe al menos una A de la cual i es un múltiplo, luego sumando. Estrictamente hablando, deberíamos usar n.tail.existsdentro del cierre, pero como siempre es menor que N y, por lo tanto, nunca es un múltiplo de N, la solución aún está completa sin esto.

sprague44
fuente
1

Java 8, 75 bytes

(N,A)->IntStream.range(1,N).filter(x->A.stream().anyMatch(y->x%y==0)).sum()

La firma del método para esto es int f(int N, List<Integer> A)

Fruta no lineal
fuente
1

Ruby, 52 48 46 bytes

->b{b[s=0].times{|x|b.find{|y|x%y<1&&s+=x}};s}
GB
fuente
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;}

Requiere este conjunto de encabezados en la misma carpeta, y la fnv-hashbiblioteca que se encuentra allí también. Compilar comogcc 1.c ../fnv-hash/libfnv.a -o 1 -DNODEBUG

Programa de prueba:

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

salidas

23
23
23
gato
fuente
1

Japt -x, 9 7 6 bytes

Ç*VøZâ

Intentalo

           :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
Lanudo
fuente
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

Pruébalo en línea!

Estructura de árbol:

struct tree

Cómo funciona

Muy simple, colocamos cada número (las líneas con Eachellas) a través de una serie de funciones (las líneas con Lellas), luego, en base a los resultados de esas funciones, descartamos algunos números y guardamos el resto, antes de finalmente sumarlos. . De hecho, podemos definir esas funciones, dondeα denota el conjunto de números dados como entrada:

F(X)={yoEl |(yoEl |X),yonorte}es decir, el conjunto de divisores deXsol(X)=F(X)αes decir, la unión de los divisores deXconαh(X)=El |sol(X)El |>0 0es decirsol(X)no está vacío

Esto es lo que representan las líneas 5 a 10 . Las líneas 11 a 16 son simplemente la aplicación de esas tres funciones. Una vez que hemos definido todas las funciones, mutamosα a β de acuerdo con la siguiente regla:

βyo={αyoh(αyo)0 0h(αyo)

dónde αyo denota el yoth elemento de αy lo mismo para β. Finalmente, simplemente podemos tomar la suma deβ, como el 0 0 Los elementos no afectan la suma.

caird coinheringaahing
fuente
1

K (oK) , 15 14 bytes

Solución:

{+/&|/~y!\:!x}

Pruébalo en línea!

Ejemplos:

{+/&|/~y!\:!x}[50;,2]
600
{+/&|/~y!\:!x}[10;3 5]
23

Explicación:

{+/&|/~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
callejero
fuente
0

En realidad , 13 bytes

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

Pruébalo en línea!

Explicación:

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

Procesamiento, 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;}

Utiliza el forenfoque de bucle simple , suma todos los múltiplos y lo devuelve. La entrada es el formato int, int[]matriz.

Kritixi Lithos
fuente