Potencias de números enteros

19

Algunos números como 64se pueden expresar como una potencia de número entero de múltiples maneras:

64 ^ 1
 8 ^ 2
 4 ^ 3
 2 ^ 6

Genere una matriz ordenada de todas las potencias posibles (aquí [1,2,3,6]) en el menor número de bytes posible.


Entrada

Un número entero positivo que es mayor que 1 y menor que 10000.


Salida

Una matriz de potencias de números enteros p(incluidos 1) para los cuales la entrada se puede expresar como a^pcon números enteros a. Las salidas pueden tener decimales, siempre que estén en orden.

Cualquier problema de punto flotante debe ser manejado por el programa.


Ejemplos

Input: 3
Output: [1]

Input: 9
Output: [1, 2]

Input: 81
Output: [1, 2, 4]

Input: 729
Output: [1, 2, 3, 6]

Marcador

Para que su puntaje aparezca en el tablero, debe estar en este formato:

# Language, Bytes

Los tachados no deberían causar un problema.

Puertas de Zach
fuente
1
Mi respuesta se imprime [1 2 3 6]para el último caso de prueba. ¿Podría también imprimir [6 3 2 1], [1.0 2.0 3.0 6.0]o [6.0 3.0 2.0 1.0]?
Dennis
2
¿Qué podemos suponer sobre los tamaños de entrada y la aritmética de punto flotante? Esto afecta la solución en la que intentas tomar raíces del número y ver si el resultado es entero.
xnor
44
Creo que las referencias a las raíces confundían a todos, así que lo reescribí en términos de poderes. Siéntase libre de cambiar las cosas nuevamente.
xnor
1
Agradezco la edición! Las sugerencias y revisiones son siempre bienvenidas, siempre que mejoren la calidad de mi pregunta (lo cual creo que hizo la suya). Hace poco comencé a hacer preguntas en esta red en particular, y encuentro que la comunidad en general es acogedora. ¡La crítica y la corrección son muy apreciadas! @xnor
Zach Gates
1
¡Simplemente encuentre la potencia válida más grande y luego enumere sus factores!
SuperJedi224

Respuestas:

10

Pyth, 10 bytes

f}Q^RTSQSQ

Demostración

Para cada potencia, genera la lista de todos los números hasta la entrada llevada a esa potencia, y luego verifica si la entrada está en la lista.

isaacg
fuente
10

Haskell, 38

f n=[b|b<-[1..n],n`elem`map(^b)[1..n]]

Muy claro. La comprensión de la lista encuentra valores bpara los que naparece la entrada [1^b, 2^b, ..., n^b]. Basta comprobar ben el rango [1..n].

xnor
fuente
9

Pitón 2, 53

lambda n:[i/n for i in range(n*n)if(i%n+1)**(i/n)==n]

Brute fuerza todas las combinaciones de bases en exponentes en [0, n-1] y bases en [1, n].

Feersum
fuente
8

Python 3, 56 bytes

lambda n:[i for i in range(1,n)if round(n**(1/i))**i==n]

Esto es realmente torpe. Comprueba si cada iraíz potencial -th da un número entero redondeándolo, tomándole el poder de i, y verificando que sea igual al original.

Verificar directamente que la raíz es un número entero es complicado porque los puntos flotantes dan cosas como 64**(1/3) == 3.9999999999999996. Redondeándolo a un entero, verifiquemos si tomar la potencia vuelve al valor original. Gracias a ypercube por sugerir esto, ahorrando 1 byte.

Feersum tiene una solución más corta y más inteligente . Todos ustedes realmente deberían votar eso.

xnor
fuente
¿No sería exacto si lo marcaras round(n**(1/i),0)**i==n?
ypercubeᵀᴹ
@ypercube Buena llamada, además de 0ser la precisión predeterminada para la ronda, esto ahorra un byte.
xnor
7

Pyth, 11 10 12 bytes

fsmqQ^dTSQSQ

Comprueba todas las combinaciones posibles de poderes. Muy lento.

orlp
fuente
5

CJam, 23 bytes

rimF{1=:E){E\d%!},}%:&p

Esto funciona tomando la factorización prima de n y calculando la intersección de los divisores de todos los exponentes.

Es un poco más largo que mi otra solución , pero esperar que funcione (y terminar al instante) para todos los enteros entre 2 y 2 63 - 1 .

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

ri                       Read an integer from STDIN.
  mF                     Push its prime factorization.
    {             }%     For each [prime exponent]:
     1=:E                  Retrieve the exponent and save it in E.
         ){     },         Filter; for each I in [0 ... E]:
           E\d%              Compute E % Double(I).
                             (Casting to Double is required to divide by 0.)
               !             Push the logical NOT of the modulus.
                           Keep I if the result is truhty, i.e., if I divides E.
                    :&   Intersect all resulting arrays of integers.
                      p  Print the resulting array.
Dennis
fuente
5

APL, 17 bytes

(X=⌊X←N*÷⍳N)/⍳N←⎕

Mi primer programa APL; Se agradecen las sugerencias de golf.

              N←⎕  ⍝ Store input into N
             ⍳     ⍝ The list [1 2 ... N]
            /      ⍝ Select the elements A for which
      N*÷⍳N)       ⍝ N^(1/A)
(X=⌊X←             ⍝ equals its floor (that is, is an integer)
lirtosiast
fuente
Por favor agregue pseudocódigo / explicación. Pero +1 (no puedo votar en este momento) por usar APL (- siendo breve antes de que fuera genial ) :-)
mınxomaτ
También +1, mucho amor por APL. Máximo vehículo de golf.
Según el pseudocódigo, es poco probable que funcione (a menos que APL realice una prueba de igualdad de punto flotante aproximada). Por ejemplo, con pow(pow(7,3),1./3))me meto 6.99999999999999en C o Python. Esto se debe a que se pierde precisión al calcular 1 / A.
feersum
@feersum No sé sobre intérpretes fuera de línea, pero todos los poderes de 3 funcionan correctamente en tryapl.org.
lirtosiast
@ThomasKwa Parece que efectivamente se usa una prueba de igualdad aproximada. dyalog.com/uploads/documents/Papers/tolerant_comparison/…
feersum
3

JavaScript (ES5), 73 bytes 81 bytes 79 bytes 75 bytes

for(n=+prompt(),p=Math.pow,i=0;i++<n;)p(.5+p(n,1/i)|0,i)==n&&console.log(i)

Comprueba si la potencia entera más cercana de la posible raíz es igual n. ~~(.5+...)es equivalente a Math.round(...)para expresiones dentro del rango entero (0 a 2 ^ 31 - 1).

Editar: se usó la &&lógica diferida en lugar de ifreducir 2 bytes y se agregó un mensaje de entrada ya que la pregunta agregó una aclaración. Anteriormente asumía que la entrada estaba almacenada n.

Edición 2: se modificó ~~(.5+...)para .5+...|0guardar dos bytes evitando la agrupación.

Edición 3: eliminada varpara guardar 4 bytes. En modo no estricto, esto es aceptable.

Patrick Roberts
fuente
Puede recortar un par de bytes haciendo malabares con las expresiones: for (var p = Math.pow, i = 1; i ++ <n; p (~~ (.5 + p (n, 1 / i)), i) == n && console .log (i));
@Alhadis gracias por tu aporte, haré una edición en un momento
Patrick Roberts
@PatrickRoberts Podrías exprimir p=Math.powen el guardado rápido 1 byte
Downgoat
@vihan, eso sería una declaración inválida, ya que varse requiere
Patrick Roberts
A menos que quisieras decir en forlugar de prompt...
Patrick Roberts
3

Brachylog , 8 bytes

≥^↙.?≥ℕ≜

Pruébalo en línea!

Toma la entrada a través de su variable de entrada y genera cada potencia a través de su variable de salida, en orden ascendente según sea necesario, a diferencia de la solución anterior ≥ℕ≜^↙.?∧que tiene exactamente la misma longitud.

≥           Some number which is less than or equal to
            the input,
 ^          when raised to the power of
  ↙.        the output,
    ?       is the input.
       ≜    Label
            the output
      ℕ     as a whole number
     ≥      which is less than or equal to
    ?       the input.

No tengo ninguna justificación rigurosa para afirmar que cada exponente no sea mayor que la entrada, pero para que el programa realmente termine, necesita ser limitado.

ḋḅlᵛfes una solución mucho más corta (sin generador) para todos los casos de prueba dados, pero falla si la entrada no es una potencia de un producto de primos distintos. (Ahora que lo pienso, ya que todos los casos de prueba son poderes de primos, ḋlftambién funciona ...) Lo mejor que se me ocurrió para salvar la idea ḋḅlᵐḋˢ⊇ᵛ×f, sale a 10 bytes.

Cadena no relacionada
fuente
3

Jalea , 6 bytes

ÆEg/ÆD

Pruébalo en línea!

    ÆD    The list of divisors of
ÆE        the exponents in the prime factorization of the input
   /      reduced by
  g       greatest common divisor.
Cadena no relacionada
fuente
2

JavaScript ES7, 66 bytes

Aprovecha las comprensiones experimentales de matrices. Solo funciona en Firefox.

n=>[for(i of Array(n).keys(m=Math.pow))if(m(0|.5+m(n,1/i),i)==n)i]

Posible golf. Probablemente intentaré reducir las expresiones un poco más y espero encontrar una alternativa a la Array(n).keys()sintaxis larga .

Podría ser más corto, pero JavaScript tiene una precisión de coma flotante horrible.

Downgoat
fuente
Ah, aprendí algo nuevo ... genial.
Patrick Roberts
2

CJam, 20 bytes

ri_,1df+\1$fmL9fmO&p

Para la entrada n , esto calcula el registro b n para todo b menor o igual a n y mantiene los resultados que son enteros.

Esto debería funcionar para todos los enteros entre 2 y 9,999 . El tiempo de ejecución es aproximadamente O (n) .

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

ri                   e# Read an integer N from STDIN.
  _,                 e# Copy N and transform it into [0 ... N-1].
    1df+             e# Add 1.0 to each, resulting in [1.0 ... Nd].
        \1$          e# Swap the array with N and copy the array.
           fmL       e# Mapped log base N: N [1.0 ... Nd] -> [log1(N) ... logN(N)]
              9fmO   e# Round each logarithm to 9 decimals.
                  &  e# Intersect this array with [1.0 ... Nd].
                   p e# Print the result.
Dennis
fuente
¿Es 15.625 la única entrada en la que falla o es la única que falló que probó?
Beta Decay
Definitivamente hay otros. De hecho, me acabo de enterar de que también falló en 4913 , lo que hizo que mi revisión anterior no fuera válida.
Dennis
2

Rubí, 50

->n{(1..n).map{|i|(n**(1.0/i)+1e-9)%1>1e-8||p(i)}}

Imprime a la pantalla.

Rubí, 57

->n{a=[]
(1..n).map{|i|(n**(1.0/i)+1e-9)%1>1e-8||a<<i}
a}

Devuelve una matriz.

En programa de prueba:

f=->n{(1..n).map{|i|(n**(1.0/i)+1e-9)%1>1e-8||puts(i)}}

g=->n{a=[]
(1..n).map{|i|(n**(1.0/i)+1e-9)%1>1e-8||a<<i}
a}

f.call(4096)
puts g.call(4096)

Calcula cada raíz y las prueba en el módulo 1 para ver si el resto es menor que 1e-8. Debido a la precisión limitada, se calcula que algunas raíces enteras válidas tienen la forma 0.9999 ..., de ahí la necesidad de agregarles 1e-9.

Se calcula hasta la enésima raíz de n, que es una exageración total, pero parecía la forma más corta de escribir un bucle no infinito.

Level River St
fuente
2

Stax , 6 bytes

£ÅeÉåC

Ejecutar y depurarlo

Todos los divisores de la mcd de exponentes en la factorización prima. Es lo mismo que el algoritmo de gelatina.

recursivo
fuente
2

DC, 104 bytes

La entrada se toma del terminal, la salida se imprime y también en la pila.

Porque esto usa el? operador, necesita usar dc -e "<solution>"o dc <file with solution in it>.

Nadie ve mis respuestas, y mucho menos las vota, pero realmente disfruto resolviendo problemas en DC. Es la solución menos eficiente en este hilo hasta ahora, pero pensé que lo publicaría de todos modos.

1sb?sn[lesi]ss[lble1+dse^dln=sln>c]sc[liSflq1+sq]sm[Lfplq1-dsq0<p]dsp[lb1+sb0si0selcxli0!=mlbln!=h]dshxx

cosas de arranque

1sb           Store 1 in register b
?sn           Store user input in register n
[lesi]ss      A macro to copy the e to the i register, stored in the s register

Macro para elevar una base a todas las potencias hasta que el resultado sea mayor que el objetivo o igual al objetivo

[lble1+dse^dln=sln>c]sc
[lb                 ]   load our base num (register b)
[  le               ]   load our exponent (register e)
[    1+dse          ]   add 1 to the exponent, copy and store in the e register
[         ^d        ]   raise the base to the exponent and copy it
[           ln=s    ]   load the user input, if that is equal to the power result run the macro in register s
[               ln>c]   load the user input, if it's greater than the power result run the macro in register c (this one)
[                   ]sc save this macro in register c

Macro para guardar un valor de exponente válido como se encuentra en las macros de exponente anteriores en otra pila

[liSflq1+sq]sm
[liSf      ]     copy the i register to the top of the stack in register f
[    lq1+sq]     add 1 to the q register
[          ]sm   save this macro in the m register

Macro para ejecutar la macro 2x anterior (macro c) a través de todas las bases desde 2 hasta nuestro número objetivo

[lb1+sb0si0selcxli0!=mlbln!=h]dsh
[lb1+sb                      ]     add 1 to the base number
[      0si0se                ]     reset the i and e registers (previously found value and exponent
[            lcx             ]     load and run the c macro
[               li0!=m       ]     load the result of the c macro and if it's not 0, run m to save it to the f stack
[                     lbln!=h]     if our base number is not equal to our target number, run macro h (this macro)
[                            ]dsh  duplicate this macro and save one copy, so that one is left on the stack to run later

Macro para imprimir los valores de la pila f

[Lfplq1-dsq0<p]dsp
[Lfp          ]      load the top value from the f register and print it
[   lq1-dsq   ]      load the q register and subtract one from it and save it
[          0<p]      if the q register is greater than 0, run macro p (this macro) again
[             ]dsp   duplicate this macro and save one copy, so that one is left on the stack to run later

xx finally run the two macros on the stack (h and then p)

FlexEast
fuente
1
Supongo que no mucha gente conoce DC. Responder nuevas preguntas (especialmente ser una de las primeras respuestas) ayudará a obtener más atención. También puede intentar usar enlaces TIO para sus respuestas, ya que es muy popular. Aquí está DC en TIO .
mbomb007
¡Gracias! ¡Definitivamente lo usaré para las respuestas que van hacia adelante!
FlexEast
1

Ruby , 46 bytes

nortemisisimi=norte

->n{(0..n).select{|e|(1..n).find{|b|b**e==n}}}

Pruébalo en línea!

Tinta de valor
fuente
0

Japt , 10 bytes

õ
f@mpX øN

Intentalo

õ            :Implicit input of integer U
õ            :Range [1,U]
f@mpX øN     :Reassign to U
f            :Filter
 @           :By passing each X through the following function
  m          :  Map U
   pX        :    Raise to the power of X
      ø      :  Contains
       N     :    Any element of the (singelton) array of inputs
Lanudo
fuente