Suma los poderes que hay

35

Un desafío simple pero con suerte no del todo trivial:

Escriba un programa o función que sume los kpoderes th que dividen un número n. Más específicamente:

  • Entrada: dos enteros positivos ny k(o un par ordenado de enteros, etc.)
  • Salida: la suma de todos los divisores positivos de neso son las kpotencias de los enteros

Por ejemplo, 11! = 39916800 tiene seis divisores que son cubos, a saber, 1, 8, 27, 64, 216, y 1728. Por lo tanto entradas dadas 39916800y 3, el programa debe devolver su suma, 2044.

Otros casos de prueba:

{40320, 1} -> 159120
{40320, 2} -> 850
{40320, 3} -> 73
{40320, 4} -> 17
{40320, 5} -> 33
{40320, 6} -> 65
{40320, 7} -> 129
{40320, 8} -> 1
{46656, 1} -> 138811
{46656, 2} -> 69700
{46656, 3} -> 55261
{46656, 4} -> 1394
{46656, 5} -> 8052
{46656, 6} -> 47450
{46656, 7} -> 1
{1, [any positive integer]} -> 1

Este es el código de golf, así que cuanto más corto sea el código, mejor. Doy la bienvenida al código de golf en todo tipo de idiomas diferentes, incluso si algún otro idioma puede escapar con menos bytes que el tuyo.

Greg Martin
fuente
12
Cuando vi por primera vez tu desafío, tuve la extraña sensación de que era el título de una canción de Metallica.
Arnauld
1
¿Qué? ¿No hay Mathematica incorporado para esto?
boboquack

Respuestas:

13

05AB1E , 9 bytes

DLImDŠÖÏO

Pruébalo en línea!

Explicación

Entrada de ejemplo 46656, 3

D          # duplicate first input
           # STACK: 46656, 46656
 L         # range [1 ... first input]
           # STACK: 46656, [1 ... 46656]
  Im       # each to the power of second input
           # STACK: 46656, [1, 8, 27 ...]
    D      # duplicate
           # STACK: 46656, [1, 8, 27 ...], [1, 8, 27 ...]
     Š     # move down 2 spots on the stack
           # STACK: [1, 8, 27 ...], 46656, [1, 8, 27 ...]
      Ö    # a mod b == 0
           # STACK: [1, 8, 27 ...], [1,1,1,1,0 ...]
       Ï   # keep only items from first list which are true in second
           # STACK: [1, 8, 27, 64, 216, 729, 1728, 5832, 46656]
        O  # sum
           # OUTPUT: 55261
Emigna
fuente
6

Mathematica, 28 bytes

Tr[Divisors@#⋂Range@#^#2]&

Toma de funciones sin nombre ny kcomo entradas en ese orden.

Martin Ender
fuente
2
DivisorSumestá frustrantemente cerca de ser útil aquí.
ngenisis
5

Haskell , 37 35 34 bytes

n!k=sum[x^k|x<-[1..n],n`mod`x^k<1]

Pruébalo en línea! Uso:

Prelude> 40320 ! 1
159120

El código es bastante ineficiente porque siempre computa 1^k, 2^k, ..., n^k.

Editar: guardado un byte gracias a Zgarb.

Explicación:

n!k=             -- given n and k, the function ! returns
 sum[x^k|        -- the sum of the list of all x^k
   x<-[1..n],    -- where x is drawn from the range 1 to n
   n`mod`x^k<1]  -- and n modulus x^k is less than 1, that is x^k divides n
Laikoni
fuente
1
mod n(x^k)puede ser n`mod`x^k.
Zgarb
5

Python 2, 54 52 bytes

lambda x,n:sum(i**n*(x%i**n<1)for i in range(1,-~x))

Gracias @Rod por cortar 2 bytes.

hashcode55
fuente
Puede reemplazar x%i**n==0con x%i**n<1, y moverse al otro lado comoi**n*(x%i**n<1)
Rod
4

Ruby, 45 bytes

->n,m{(1..n).reduce{|a,b|n%(c=b**m)<1?a+c:a}}

Sería más corto usando "sum" en Ruby 2.4. ¿Hora de actualizar?

GB
fuente
44
Hora de actualizar.
Yytsi
4

MATL , 10 bytes

t:i^\~5M*s

Pruébalo en línea!

Cómo funciona

Ejemplo con 46656, 6.

t      % Implicitly input n. Duplicate
       % STACK: 46656, 46656
:      % Range
       % STACK: 46656, [1 2 ... 46656]
i      % Input k
       % STACK: 46656, [1 2 ... 46656], 6
^      % Power, element-wise
       % STACK: 46656, [1 64 ... 46656^6]
\      % Modulo
       % STACK: [0 0 0 1600 ...]
~      % Logically negate
       % STACK: [true true true false ...]
5M     % Push second input to function \ again
       % STACK: [true true true false ...], [1^6 2^6 ... 46656^6]
*      % Multiply, element-wise
       % STACK: [1 64 729 0 ...]
s      % Sum of array: 47450
       % Implicitly display
Luis Mendo
fuente
4

Jalea , 7 6 bytes

-1 byte gracias a Dennis (atraviesa un rango implícito)
Una eficiencia inteligente que también ahorra Dennis a un costo de 0 bytes
(Anteriormente ÆDf*€Sfiltraría mantener esos divisores que son una potencia de k de cualquier número natural hasta n . Pero tenga en cuenta que n puede ¡solo tengo un divisor de i k si tiene un divisor de i de todos modos!)

ÆDf*¥S

Pruébalo en línea!

¿Cómo?

ÆDf*¥S - Main link: n, k
ÆD     - divisors of n  -> divisors = [1, d1, d2, ..., n]
    ¥  - last two links as a dyadic chain
  f    -     filter divisors keeping those that appear in:
   *   -     exponentiate k with base divisors (vectorises)
       - i.e. [v for v in [1, d1, d2, ..., n] if v in [1^k, d1^k, ..., n^k]]
     S - sum
Jonathan Allan
fuente
3

JavaScript (ES7), 56 53 bytes

Toma ny ken sintaxis curry (n)(k).

n=>k=>[...Array(n)].reduce(p=>n%(a=++i**k)?p:p+a,i=0)

Casos de prueba

Arnauld
fuente
3

Perl 6 , 39 bytes

->\n,\k{sum grep n%%*,({++$**k}...*>n)}

Cómo funciona

->\n,\k{                              }  # A lambda taking two arguments.
                        ++$              # Increment an anonymous counter
                           **k           # and raise it to the power k,
                       {      }...       # generate a list by repeatedly doing that,
                                  *>n    # until we reach a value greater than n.
            grep n%%*,(              )   # Filter factors of n from the list.
        sum                              # Return their sum.

Intentalo

smls
fuente
2

Japt , 10 bytes

Ahorró muchos bytes gracias a @ETHproductions

òpV f!vU x

Explicación

òpV f!vU x
ò           // Creates a range from 0 to U
 pV         // Raises each item to the power of V (Second input)
    f       // Selects all items Z where
     !vU    //   U is divisible by Z
            //   (fvU would mean Z is divisible by U; ! swaps the arguments)
         x  // Returns the sum of all remaining items

¡Pruébelo en línea!

Oliver
fuente
¿ vUDetecta números divisibles por Uo números que se dividen U?
Greg Martin
@GregMartin fvUfiltra a los elementos que son divisibles por U; f!vUfiltra a los elementos que Ues divisible por. !intercambia los argumentos.
Oliver
Genial, por lo que el código se ve bien, pero es posible que sea necesario modificar la explicación.
Greg Martin
@GregMartin Debería ser más claro ahora.
ETHproductions
2

Scala 63 bytes

(n:Int,k:Int)=>1 to n map{Math.pow(_,k).toInt}filter{n%_==0}sum
jaxad0127
fuente
2

Python 2 , 50 bytes

f=lambda n,k,i=1:n/i and(n%i**k<1)*i**k+f(n,k,i+1)

Pruébalo en línea! Las entradas grandes pueden exceder la profundidad de recursión dependiendo de su sistema e implementación.

xnor
fuente
2

JavaScript (ES7), 49 46 bytes

n=>g=(k,t=i=0,p=++i**k)=>p>n?t:g(k,t+p*!(n%p))
Neil
fuente
Ya que no estás recurriendo, ¿por qué no n=>k=>? +1.
Yytsi
@ TuukkaX Se me ocurrió algo mejor. (De hecho, tuve esto antes icomo local, lo que cuesta 4 bytes adicionales, y olvidé que podía abusar ide la misma manera que lo hice con mi otra formulación.)
Neil
1

PHP, 86 bytes

$n=$argv[1];$k=$argv[2];for($i=1;$i<=$n**(1/$k);$i++)if($n%$i**$k<1)$s+=$i**$k;echo$s;

Pruébalo aquí!

Descompostura :

$n=$argv[1];$k=$argv[2];       # Assign variables from input
for($i=1;$i<=$n**(1/$k);$i++)  # While i is between 1 AND kth root of n
    if($n%$i**$k<1)            #     if i^k is a divisor of n
        $s+=$i**$k;            #         then add to s
echo$s;                        # echo s (duh!)
roberto06
fuente
golf, pero no probado: for(;$x<$n=$argv[1];)$n%($x=++$i**$argv[2])?:$s+=$x;echo$s;59 bytes; requiere PHP 5.6 o posterior.
Titus
1

CJam , 20 bytes

Probablemente no sea un golf óptimo, pero no veo ningún cambio obvio que hacer ...

ri:N,:)rif#{N\%!},:+

Pruébalo en línea!

Gato de negocios
fuente
1

Utilidades Bash + Unix, 44 bytes

bc<<<`seq "-fx=%.f^$2;s+=($1%%x==0)*x;" $1`s

Pruébalo en línea!

Pruebas de funcionamiento:

for x in '40320 1' '40320 2' '40320 3' '40320 4' '40320 5' '40320 6' '40320 7' '40320 8' '46656 1' '46656 2' '46656 3' '46656 4' '46656 5' '46656 6' '46656 7' '1 1' '1 2' '1 3' '1 12' ; do echo -n "$x "; ./sumpowerdivisors $x; done

40320 1 159120
40320 2 850
40320 3 73
40320 4 17
40320 5 33
40320 6 65
40320 7 129
40320 8 1
46656 1 138811
46656 2 69700
46656 3 55261
46656 4 1394
46656 5 8052
46656 6 47450
46656 7 1
1 1 1
1 2 1
1 3 1
1 12 1
Mitchell Spector
fuente
1

Python , 56 bytes

lambda n,k:sum(j*(j**k**-1%1==n%j)for j in range(1,n+1))

Pruébalo en línea!

Bastante sencillo. Lo único notable es que j**k**-1%1siempre devuelve un flotante en [0,1) mientras que n%jsiempre devuelve un entero no negativo, por lo que solo pueden ser iguales si ambos son 0 .

Dennis
fuente
1

Lote, 138 bytes

@set s=n
@for /l %%i in (2,1,%2)do @call set s=%%s%%*n
@set/at=n=0
:l
@set/an+=1,p=%s%,t+=p*!(%1%%p)
@if %p% lss %1 goto l
@echo %t%

Como Batch no tiene un operador de energía, estoy abusando set/acomo una forma de eval. Muy lento cuando k=1. La aritmética de enteros de 32 bits limita los valores admitidos de ny k:

           n   k
  (too slow)   1
 <1366041600   2
 <1833767424   3
 <2019963136   4
 <2073071593   5
 <1838265625   6
 <1801088541   7
 <1475789056   8
 <1000000000   9
 <1073741824  10
 <1977326743  11
  <244140625  12
 <1220703125  13
  <268435456  14
 <1073741824  15
   <43046721  16
  <129140163  17
  <387420489  18
 <1162261467  19
    <1048576  20
           ...
 <1073741824  30
Neil
fuente
0

R, 28 bytes directos, 43 bytes para la función

si n, k en la memoria:

sum((n%%(1:n)^k==0)*(1:n)^k)

para una función:

r=function(n,k)sum((n%%(1:n)^k==0)*(1:n)^k)
Zahiro Mor
fuente