Desafio

Sua tarefa é escrever um programa ou função que, dado um número inteiro positivo N , encontre todos os números inteiros positivos menores ou iguais a N que possam ser expressos como uma potência perfeita em mais de uma maneira.

Definição

Um poder perfeito é definido como um número i encontrado por m ^ k , onde:

• m e i são números inteiros positivos
• m! = k

Casos de teste

entrada -> saída
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

Forneça também uma versão legível e comentada.

Mathematica: 103 caracteres

Os espaços podem ser removidos

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

Uso:

%[81]
{16, 64, 81}

Geléia , 11 bytes significativos, desafio pós-datas de idiomas

ḊḟÆR *@þ Ḋ  F  fḊ

Experimente online!

Aqui está uma solução totalmente diferente. Esse é um híbrido curioso de eficiente e ineficiente, usando um algoritmo de núcleo eficiente em um invólucro muito ineficiente (tanto que ele não consegue lidar com números muito grandes). Como antes, todo o espaço em branco não tem sentido.

Aqui está como isso funciona. Ḋ(que aparece várias vezes) é uma lista de números de 2 à 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 Ḋ

A observação básica aqui é que um número é uma potência perfeita de várias maneiras, apenas se for uma potência perfeita com um expoente composto (que não seja 1). Geramos uma lista daqueles em que a base é de 2 para a entrada e o expoente é um número composto de 4 para a entrada; isso é muito lento porque gera alguns números realmente grandes, todos os quais são uma resposta para a pergunta. Então, mantemos apenas as respostas que estão dentro do alcance.

Seria fácil modificar isso em uma resposta altamente eficiente, calculando qual era a potência máxima no intervalo e não repetindo mais, mas isso seria muito mais bytes, e isso é código-golfe.

Perl: 68 caracteres

Obtém o máximo (1000) $Ne retorna a resposta @a.

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

Para um programa inteiro, preciso de outros 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 (sem espaço em branco)

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.

Teste

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

Gelatina , 13 caracteres significativos, desafio pós-datas de idiomas

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

Experimente online!

Todo espaço em branco aqui é insignificante. Usei-o para mostrar a estrutura da minha resposta, como a pergunta.

Veja 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

Por exemplo, ao testar n = 256, verificamos o número de vezes que cada um dos números de 2 a 256 se divide em 256. Os únicos números que se dividem mais de uma vez são 2 (que divide 8 vezes), 4 (que divide 4 vezes), 8 (que divide duas vezes) e 16 (que divide duas vezes). Portanto, quando aumentamos o número de divisões para os poderes determinados lá, obtemos:

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

Isso produz o valor original, 256, um número de vezes igual ao modo como 256 é uma potência perfeita, mais uma (o último elemento produz 256 porque 256 = 256¹). Portanto, se vemos 256 mais do que duas vezes na matriz (e vemos neste caso; 8² é 64, mas todos os outros elementos "interessantes" produzem 256), deve ser uma potência perfeita.