Défi

Votre tâche consiste à écrire un programme ou une fonction qui, étant donné un entier positif N , trouve tous les entiers positifs inférieurs ou égaux à N qui peuvent être exprimés en puissance parfaite de plusieurs manières.

Définition

Une puissance parfaite est définie comme un nombre i trouvé par m ^ k , où:

• m et i sont des entiers positifs
• m! = k

Cas de test

entrée -> sortie
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

Veuillez également fournir une version lisible et commentée.

Mathematica: 103 caractères

Les espaces peuvent être supprimés

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

Usage:

%[81]
{16, 64, 81}

Jelly , 11 octets significatifs, défi de postdates de langue

ḊḟÆR *@þ Ḋ  F  fḊ

Essayez-le en ligne!

Voici une solution entièrement différente. Celui-ci est un curieux hybride efficace et inefficace, utilisant un algorithme de base efficace dans un wrapper très inefficace (à tel point qu'il ne peut pas gérer de très grands nombres). Comme précédemment, tous les espaces blancs n'ont aucun sens.

Voici comment ça fonctionne. Ḋ(qui apparaît plusieurs fois) est une liste de nombres de 2 à l'entrée incluse:

ḊḟÆ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 Ḋ

L'observation de base ici est qu'un nombre est une puissance parfaite de plusieurs manières, seulement s'il s'agit d'une puissance parfaite avec un exposant composite (ce n'est pas 1). Nous générons une liste de ceux dont la base est de 2 à l'entrée, et l'exposant est un nombre composite de 4 à l'entrée; c'est vraiment lent car cela génère de très gros nombres, qui sont tous une réponse à la question. Ensuite, nous ne gardons que les réponses qui sont à portée.

Il serait facilement possible de modifier cela en une réponse très efficace, en déterminant la puissance maximale dans la plage et en ne répétant pas plus, mais ce serait beaucoup plus d'octets, et c'est le code-golf.

Perl: 68 caractères

Obtient le maximum (1000) $Net renvoie la réponse @a.

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

Pour tout un programme, j'ai besoin de 18 autres caractères:

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

Ruby - 101 caractères (sans espace)

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}

Fonctionne pendant 1 <= limit <= 100,000,0005 secondes.

Tester

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

Jelly , 13 personnages significatifs, défi de postdates de langue

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

Essayez-le en ligne!

Tous les espaces ici sont insignifiants. Je l'ai utilisé pour montrer la structure de ma réponse, comme le demande la question.

Voici comment ça fonctionne:

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

Ainsi, par exemple, lorsque nous testons n = 256, nous vérifions le nombre de fois que chacun des nombres de 2 à 256 se divise en 256. Les seuls nombres qui se divisent plus d'une fois sont 2 (qui se divise 8 fois), 4 (qui divise 4 fois), 8 (qui se divise deux fois) et 16 (qui se divise deux fois). Ainsi, lorsque nous élevons le nombre de divisions aux pouvoirs qui y sont déterminés, nous obtenons:

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

Cela produit la valeur d'origine, 256, un nombre de fois égal à la façon dont 256 est une puissance parfaite, plus un (le dernier élément produit 256 car 256 = 256¹). Donc, si nous voyons 256 plus de deux fois dans le tableau (et nous le faisons dans ce cas; 8² est 64 mais les autres éléments "intéressants" produisent tous 256), cela doit être une puissance parfaite.