Desafío

Su tarea es escribir un programa o función que, dado un entero positivo N , encuentre todos los enteros positivos menores o iguales a N que puedan expresarse como una potencia perfecta en más de una forma.

Definición

A poder perfecto se define como un número i encontrado por m ^ k , donde:

• m y i son enteros positivos
• m! = k

Casos de prueba

entrada -> salida
1000 -> 16, 64, 81, 256, 512, 625, 729
56 -> 16
999 -> 16, 64, 81, 256, 512, 625, 729
81 -> 16, 64, 81
1500 -> 16, 64, 81, 256, 512, 625, 729, 1024, 1296

Proporcione también una versión legible y comentada.

Mathematica: 103 caracteres

Se pueden eliminar espacios

Select[Flatten@
       Table[
        Solve[Log@#/Log@b == k, k, Integers] /. k -> #, {b, 2, #}] & /@ Range@#, 
Length@# > 2 &][[All, 1, 1]] &  

Uso:

%[81]
{16, 64, 81}

Jelly , 11 bytes significativos, desafío de postdates de idioma

ḊḟÆR *@þ Ḋ  F  fḊ

Pruébalo en línea!

Aquí hay una solución completamente diferente. Este es un curioso híbrido de eficiente e ineficiente, que utiliza un algoritmo central eficiente en un contenedor muy ineficiente (tanto que no puede manejar números muy grandes). Como antes, todo el espacio en blanco no tiene sentido.

Así es como funciona. Ḋ(que aparece varias veces) es una lista de números del 2 a la entrada inclusive:

ḊḟÆR *@þ Ḋ  F  fḊ
ḊḟÆR                Ḋ, with all primes between 2 and the input removed
                    (i.e. all composite numbers from 4 to the input)
     *@þ Ḋ          Exponentiate all Ḋ elements with all ḊḟÆR elements
            F       Flatten the result (it had a nested structure)
               fḊ   Keep only elements in Ḋ

La observación básica aquí es que un número es una potencia perfecta en múltiples formas, solo si es una potencia perfecta con un exponente compuesto (que no es 1). Generamos una lista de aquellos donde la base es de 2 a la entrada, y el exponente es un número compuesto de 4 a la entrada; Esto es realmente lento porque genera algunos números realmente grandes, todos los cuales son una respuesta a la pregunta. Entonces solo mantenemos las respuestas que están dentro del rango.

Fácilmente sería posible modificar esto en una respuesta altamente eficiente, calculando cuál era la potencia máxima en el rango y no iterando más, pero eso sería mucho más bytes, y esto es código de golf.

Perl: 68 caracteres

Obtiene el máximo (1000) $Ny devuelve la respuesta @a.

for $x ( 2..$N ) {
    $c{$x**$_}++ for 2..log($N)/log$x
}
@a = grep { $c{$_} > 1 } keys %c

Para todo un programa, necesito otros 18 caracteres:

$m = shift;
for $x ( 2..$m ) {
    $c{$x**$_}++ for 2..log($m)/log$x
}
print join ' ', grep { $c{$_} > 1 } keys %c

Ruby - 101 caracteres (sin espacios en blanco)

f=->l{c=Hash.new{0}
2.upto(1E4){|i|2.upto(20){|j|c[i**j]+=1}}
c.map{|k,v|v>1&&k<=l&&k||p}.compact.sort}

Funciona por 1 <= limit <= 100,000,0005 segundos.

Prueba

> f[10000]
[16, 64, 81, 256, 512, 625, 729, 1024, 1296, 2401, 4096, 6561, 10000]

Jelly , 13 personajes significativos, desafío de postdates de lenguaje

R  µ  ọḊ *@Ḋ ċ >2  µ  Ðf

Pruébalo en línea!

Todo el espacio en blanco aquí es insignificante. Lo usé para mostrar la estructura de mi respuesta, como la pregunta pregunta.

Así es como funciona:

R  µ  ọḊ *@Ḋ ċ >2  µ  Ðf
R                     Ðf    Find all numbers n from 1 to the input, such that:
   µ               µ          (grouping marks, like {} in C)
       Ḋ   Ḋ                  Take the range from 2 to n
      ọ                       Find the number of times each divides n
         *@                   Raise the range from 2 to n to these powers
             ċ                Count the number of times n appears
               >2             and the result must be greater than 2

Entonces, por ejemplo, al probar n = 256, verificamos el número de veces que cada uno de los números del 2 al 256 se divide en 256. Los únicos números que se dividen más de una vez son 2 (que divide 8 veces), 4 (que divide 4 veces), 8 (que divide dos veces) y 16 (que divide dos veces). Entonces, cuando aumentamos el número de divisiones a los poderes determinados allí, obtenemos:

2⁸, 3, 4⁴, 5, 6, 7, 8², 9, 10, 11, 12, 13, 14, 15, 16², 17, ..., 255, 256

Esto produce el valor original, 256, varias veces igual a la forma en que 256 es una potencia perfecta, más uno (el último elemento produce 256 porque 256 = 256¹). Entonces, si vemos 256 más de dos veces en la matriz (y lo hacemos en este caso; 8² es 64 pero los otros elementos "interesantes" producen 256), debe ser una potencia perfecta.