Divisor adecuado mash-up

20

Un divisor propio es un divisor de un número n , que no es n en sí mismo. Por ejemplo, los divisores propios de 12 son 1, 2, 3, 4 y 6.

Se le dará un número entero x , x ≥ 2, x ≤ 1000 . Su tarea es sumar todos los divisores propios más altos de los enteros de 2 a x (inclusive) (OEIS A280050 ).

Ejemplo (con x = 6):

  • Encuentre todos los enteros entre 2 y 6 (inclusive): 2,3,4,5,6.

  • Obtenga los divisores adecuados de todos ellos y elija los más altos de cada número:

    • 2 -> 1
    • 3 -> 1
    • 4 -> 1, 2
    • 5 -> 1
    • 6 -> 1, 2, 3 .
  • Resumiendo los más altos divisores propios: 1 + 1 + 2 + 1 + 3 = 8.

  • El resultado final es 8.

Casos de prueba

Entrada | Salida
------- + ---------
       El |
 2 | 1
 4 | 4 4
 6 | 8
 8 | 13
 15 | 41
 37 | 229
 100 1690
 1000 | 165279

Reglas

Sr. Xcoder
fuente
Salvadera.
Sr. Xcoder
55
Si vas a hacer algo en la caja de arena, déjalo allí durante más de dos horas.
Peter Taylor
@PeterTaylor Realicé un sandbox en la publicación solo para recibir comentarios, porque este es un desafío muy simple que generalmente no publicaría en la sandbox. Por cierto, gracias por la edición.
Sr. Xcoder

Respuestas:

13

Oasis , 4 bytes

Código:

nj+U

Pruébalo en línea!

Explicación:

Versión extendida:

nj+00

    0   = a(0)
   0    = a(1)

a(n) =

n       # Push n
 j      # Get the largest divisor under n
  +     # Add to a(n - 1)
Adnan
fuente
5

Casco , 7 bytes

ṁȯΠtptḣ

Pruébalo en línea!

Explicación

Husk no tiene una función integrada para calcular los divisores directamente (todavía), por lo que en su lugar estoy usando factorización prima. El divisor propio más grande de un número es el producto de sus factores primos, excepto el más pequeño. Mapeo esta función en el rango de 2 a la entrada, y sumo los resultados.

ṁȯΠtptḣ  Define a function:
      ḣ  Range from 1 to input.
     t   Remove the first element (range from 2).
ṁ        Map over the list and take sum:
 ȯ        The composition of
    p     prime factorization,
   t      tail (remove smallest prime) and
  Π       product.
Zgarb
fuente
5

Python 2 , 50 bytes

f=lambda n,k=2:n/k and(f(n,k+1),n/k+f(n-1))[n%k<1]

Esto es lento y ni siquiera puede hacer frente a la entrada 15 en TIO.

Pruébalo en línea!

Sin embargo, la memorización ( gracias @ musicman523 ) se puede utilizar para verificar todos los casos de prueba.

Pruébalo en línea!

Versión alternativa, 52 bytes.

A un costo de 2 bytes, podemos elegir si calcular f(n,k+1)o no n/k+f(n-1).

f=lambda n,k=2:n>1and(n%k and f(n,k+1)or n/k+f(n-1))

Con algunos trucos, esto funciona para todos los casos de prueba, incluso en TIO.

Pruébalo en línea!

Dennis
fuente
Como fes una función pura , puede memorizarla para ejecutar los casos más grandes en TIO
musicman523
Correcto, no poder usar un decorador me echó. ¡Gracias!
Dennis
4

Jalea , 6 bytes

ÆḌ€Ṫ€S

Pruébalo en línea!

Cómo funciona

ÆḌ€Ṫ€S
ÆḌ€    map proper divisor (1 would become empty array)
           implicitly turns argument into 1-indexed range
   Ṫ€  map last element
     S sum
Monja permeable
fuente
4

JavaScript (ES6), 40 bytes

f=(n,i=2)=>n<2?0:n%i?f(n,i+1):n/i+f(n-1)
<input type=number oninput=o.textContent=f(this.value)><pre id=o>

Un número es igual al producto de su divisor propio más alto y su factor primo más pequeño.

Neil
fuente
la pila se desborda por n>352(al menos en este fragmento, no sé si depende de mi navegador / máquina) mientras se supone que debe admitir al menos hasta n=1000.
officialaimm
@officialaimm Funciona n=1000si usas, por ejemplo node --stack_size=8000.
Neil
4

05AB1E , 9 8 bytes

-1 Byte gracias al truco de factor principal de Leaky Nun en su respuesta de Pyth

L¦vyÒ¦PO

Pruébalo en línea!

Explicación

L¦vyÒ¦PO
L¦       # Range [2 .. input]
  vy     # For each...
    Ò¦    # All prime factors except the first one
      P   # Product
       O  # Sum with previous results
         # Implicit print

Solución alternativa de 8 bytes (que no funciona en TIO)

L¦vyѨθO    

y una solución alternativa de 9 bytes (que funciona en TIO)

L¦vyѨ®èO    
Datboi
fuente
4

Retina , 31 24 bytes

7 bytes gracias a Martin Ender.

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

Pruébalo en línea!

Cómo funciona

La expresión regular /^(1+)\1+$/captura el divisor propio más grande de un cierto número representado en unario. En el código, \1+se convierte en una sintaxis anticipada.

Monja permeable
fuente
4

Mathematica, 30 bytes

Divisors[i][[-2]]~Sum~{i,2,#}&
J42161217
fuente
4

Pyth , 13 9 8 bytes

1 byte gracias a jacoblaw.

tsm*FtPh

Banco de pruebas .

Cómo funciona

El divisor propio más grande es el producto de los factores primos, excepto el más pequeño.

Monja permeable
fuente
8 bytes
jacoblaw
4

Python 2 (PyPy) , 73 71 70 bytes

n=input();r=[0]*n;d=1
while n:n-=1;r[d+d::d]=n/d*[d];d+=1
print sum(r)

No es la respuesta más corta de Python, pero esto simplemente pasa por los casos de prueba. TIO maneja entradas de hasta 30,000,000 sin sudar; mi computadora de escritorio maneja 300,000,000 en un minuto.

A un costo de 2 bytes , la condición n>dpodría usarse para una aceleración de ~ 10%.

¡Gracias a @xnor por la r=[0]*nidea, que ahorró 3 bytes!

Pruébalo en línea!

Dennis
fuente
Es curioso, acabo de escribir básicamente el mismo código .
xnor
l=[0]*ndebería permitirte deshacerte de él -2. execmata un poco la velocidad, pero incluso un whilebucle sería más corto que mi enfoque.
Dennis
Esto parece ser marginalmente más rápido que mi enfoque. ¿Te importa si edito eso en mi respuesta?
Dennis
Por favor, adelante.
xnor
1
@ Mr.Xcoder No en PyPy, pero sí, los tamices funcionan bien para este tipo de problema.
Dennis
4

Haskell, 48 46 43 bytes

f 2=1
f n=until((<1).mod n)pred(n-1)+f(n-1)

Pruébalo en línea!

Editar: @rogaos guardó dos bytes. ¡Gracias!

Editar II: ... y @xnor otros 3 bytes.

nimi
fuente
-2 bytes:f 2=1 f n=last[d|d<-[1..n-1],mod n d<1]+f(n-1)
vroomfondel
@rogaos: ¡Gracias! He intentado la recursividad explícita, pero no la eliminé sum, así que pensé que no es más corta.
nimi
1
untilahorra un poco más:until((<1).mod n)pred(n-1)+f(n-1)
xnor
4

Japt , 8 + 2 = 10 8 6 bytes

òâ1 xo

Pruébalo

  • 1 byte guardado gracias a ETHproductions.

Explicación

    :Implicit input of integer U.
ò   :Generate an array of integers from 1 to U, inclusive
â   :Get the divisors of each number,
1   :  excluding itself.
x   :Sum the main array
o   :by popping the last element from each sub-array.
    :Implicit output of result
Lanudo
fuente
Tenga en -xcuenta que cuenta como dos bytes de acuerdo con esta publicación . Sin embargo, creo que puede guardar un byte con ò2_â1 o( âexcluye el número original cuando se le da un argumento)
ETHproductions
Gracias, @ETHproductions; Había extrañado ambas cosas. Me pregunto si eso se aplica retroactivamente a todas las soluciones donde contamos las banderas como 1 byte. Estaba trabajando en una solución alternativa que de todos modos no usaba una bandera; señalar âel argumento me consiguió el ahorro que estaba buscando.
Shaggy
Supongo que sí, ya que realmente no estábamos siguiendo un consenso antes. Por cierto, me había estado jugando con õ Åantes y nos pareció un par de 8 y 9 byters: õ Åx_/k g, õ Åx_k Å×, õ Åx_â¬o. Y al combinar õy Åcon tu xotruco de genio encontré una solución de 7 bytes :-)
ETHproductions
3

MATL, 12 bytes

q:Q"@Z\l_)vs

Pruébalo en MATL Online

Explicación

        % Implicitly grab input (N)
q       % Subtract one
:       % Create an array [1...(N-1)]
Q       % Add one to create [2...N]
"       % For each element
  @Z\   % Compute the divisors of this element (including itself)
  l_)   % Grab the next to last element (the largest that isn't itself)
  v     % Vertically concatenate the entire stack so far
  s     % Sum the result
Suever
fuente
3

Cubix , 27 39 bytes

?%\(W!:.U0IU(;u;p+qu.@Op\;;

Pruébalo en línea!

Cubified

      ? % \
      ( W !
      : . U
0 I U ( ; u ; p + q u .
@ O p \ ; ; . . . . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

Míralo correr

  • 0IUConfigure la pila con un acumulador y el número entero inicial. U-turn en el bucle exterior
  • :(? duplicar la parte superior actual de la pila, disminuir y probar
  • \pO@ Si el bucle cero alrededor del cubo a un espejo, agarra la parte inferior de la pila, salida y detener
  • %\! si es positivo, mod, relect y prueba.
    • u;.W si es verdad, gire en u, elimine el resultado del mod y el carril cambie nuevamente al bucle interno
    • U;p+qu;;\(si falsey, giro en U, elimine el resultado del mod, lleve el acumulador a la parte superior, agregue el divisor entero actual (superior) empuje hacia abajo y gire en U. Limpie la pila para tener solo el acumulador y el número entero actual, disminuya el número entero e ingrese nuevamente al bucle externo.
MickyT
fuente
3

C # (.NET Core) , 74 72 bytes

n=>{int r=0,j;for(;n>1;n--)for(j=n;--j>0;)if(n%j<1){r+=j;j=0;}return r;}

Pruébalo en línea!

  • 2 bytes afeitados gracias a Kevin Cruijssen.
Charlie
fuente
1
Yo sé que ha sido alrededor de un año, pero se puede jugar golf breaka j=0.
Kevin Cruijssen
@KevinCruijssen es un truco muy simple pero efectivo. ¡Buena idea!
Charlie
2

Python 3 , 78 75 73 71 bytes

Ni siquiera cerca de la respuesta de Python de la monja permeable en el recuento de bytes.

f=lambda z:sum(max(i for i in range(1,y)if 1>y%i)for y in range(2,z+1))

Pruébalo en línea!

officialaimm
fuente
1
Te estás acercando a la primera revisión de mi respuesta ... puedes consultar mi historial de edición.
Leaky Nun
Oh, jaja ... juro que no lo robé ... :)
officialaimm
2

Pitón 3 , 69 63 59 bytes

4 bytes gracias a Dennis.

f=lambda n:n-1and max(j for j in range(1,n)if n%j<1)+f(n-1)

Pruébalo en línea!

Establecí el límite de recursión en 2000 para que esto funcione para 1000.

Monja permeable
fuente
+1 Tienes mis puntos brownie! Esa es la solución de la que estaba hablando cuando decía "menos de 70 bytes" ...
Sr. Xcoder
Además, esto también funciona en Python 2
Mr. Xcoder
2

Carbón , 37 bytes

A⁰βF…·²N«A⟦⟧δF⮌…¹ι«¿¬﹪ικ⊞δκ»A⁺β⌈δβ»Iβ

Pruébalo en línea!

El enlace es a la versión detallada. Me llevó casi todo el día descubrir cómo podría resolver una pregunta no relacionada con el arte ASCII en Charcoal, pero finalmente lo obtuve y estoy muy orgulloso de mí. :-RE

Sí, estoy seguro de que se puede jugar mucho al golf. Acabo de traducir mi respuesta de C # y estoy seguro de que las cosas se pueden hacer de manera diferente en Charcoal. Al menos resuelve el 1000caso en un par de segundos ...

Charlie
fuente
2

Python 2 (PyPy) , 145 bytes

Debido a que convertir las competiciones de código de golf en competencias de código más rápido es divertido, aquí hay un algoritmo O ( n ) que, en TIO, resuelve n = 5,000,000,000 en 30 segundos. ( El tamiz de Dennis es O ( n log n )).

import sympy
n=input()
def g(i,p,k,s):
 while p*max(p,k)<=n:l=k*p;i+=1;p=sympy.sieve[i];s-=g(i,p,l,n/l*(n/l*k+k-2)/2)
 return s
print~g(1,2,1,-n)

Pruébalo en línea!

Cómo funciona

Contamos el tamaño del conjunto.

S = {( a , b ) | 2 ≤ an , 2 ≤ b ≤ divisor propio más grande ( a )},

reescribiéndolo como la unión, sobre todos los números primos p ≤ √n, de

S p = {( pd , b ) | 2 ≤ dn / p , 2 ≤ bd },

y utilizando el principio de inclusión-exclusión :

El | S | = ∑ (−1) m - 1 | S p 1 ∩ ⋯ ∩ S p m | sobre m ≥ 1 y primos p 1 <⋯ < p m ≤ √n,

dónde

S p 1 ∩ ⋯ ∩ S p m = {( p 1 p m e , b ) | 1 ≤ e n / ( p 1 p m ), 2 ≤ b p 1 p m - 1 e },
| S p 1 ∩ ⋯ ∩ S p m | = ⌊ n / ( p 1 p m ) ⌋⋅ ( p 1p m- 1 ) ⌋ + 1) - 2) / 2. ⋅ (⌊ n / ( p 1p m

La suma tiene Cn términos distintos de cero, donde C converge a alguna constante que probablemente sea 6⋅ (1 - ln 2) / π 2 ≈ 0.186544. El resultado final es entonces | S | + n - 1.

Anders Kaseorg
fuente
Oooh, eso es rápido ...
Sr. Xcoder
2

NewStack , 5 bytes

Afortunadamente, en realidad hay un incorporado.

Nᵢ;qΣ

El desglose:

Nᵢ       Add the first (user's input) natural numbers to the stack.
  ;      Perform the highest factor operator on whole stack.
   q     Pop bottom of stack.
    Σ    Sum stack.

En inglés real:

Ejecutemos un ejemplo para una entrada de 8.

Nᵢ: Haga una lista de números naturales del 1 al 8: 1, 2, 3, 4, 5, 6, 7, 8

;: Calcule los mayores factores: 1, 1, 1, 2, 1, 3, 1, 4

q. Eliminar el primer elemento:1, 1, 2, 1, 3, 1, 4

ΣY toma la suma: 1+1+2+1+3+1+4=13

Graviton
fuente
1+1+2+1+3+1+4= 13no 8. Aparte de eso: gran respuesta, entonces +1.
Kevin Cruijssen
@KevinCruijssen ¡Vaya, gracias por atrapar eso!
Graviton
2

Java 8, 78 74 72 bytes

n->{int r=0,j;for(;n>1;n--)for(j=n;j-->1;)if(n%j<1){r+=j;j=0;}return r;}

Puerto de la respuesta C # de @CarlosAlejo .

Pruébalo aquí

Respuesta anterior (78 bytes):

n->{int r=0,i=1,j,k;for(;++i<=n;r+=k)for(j=1,k=1;++j<i;k=i%j<1?j:k);return r;}

Pruébalo aquí

Explicación (de la respuesta anterior):

n->{                    // Method with integer parameter and integer return-type
  int r=0,              //  Result-integers
      i=1,j,k;          //  Some temp integers
  for(;++i<=n;          //  Loop (1) from 2 to `n` (inclusive)
      r+=k)             //    And add `k` to the result after every iteration
    for(j=1,k=1;++j<i;  //   Inner loop (2) from `2` to `i` (exclusive)
      k=i%j<1?j:k       //    If `i` is dividable by `j`, replace `k` with `j`
    );                  //   End of inner loop (2)
                        //  End of loop (2) (implicit / single-line body)
  return r;             //  Return result-integer
}                       // End of method
Kevin Cruijssen
fuente
1

Apilado , 31 bytes

[2\|>[divisors:pop\MAX]map sum]

Pruébalo en línea! (Todos los casos de prueba excepto 1000, que excede el límite de tiempo en línea de 60 segundos).

Explicación

[2\|>[divisors:pop\MAX]map sum]
 2\|>                               range from 2 to the input inclusive
     [                ]map          map this function over the range
      divisors                      get the divisors of the number (including the number)
              :pop\                 pop a number off the array and swap it with the array
                   MAX              gets the maximum value from the array
                           sum      sum's all the max's
Conor O'Brien
fuente