Wyzwanie

Twoim zadaniem jest napisanie programu lub funkcji, która przy dodatniej liczbie całkowitej N znajdzie wszystkie dodatnie liczby całkowite mniejsze lub równe N, które można wyrazić jako moc doskonałą na więcej niż jeden sposób.

Definicja

Doskonałym moc jest określona jako liczba i znaleziona przez m ^ k , gdzie:

• m i i są liczbami całkowitymi dodatnimi
• m! = k

Przypadki testowe

wejście -> wyjście
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

Podaj także czytelną, skomentowaną wersję.

Mathematica: 103 znaki

Spacje można usunąć

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

Stosowanie:

%[81]
{16, 64, 81}

Galaretka , 11 znaczących bajtów, wyzwanie po datach językowych

ḊḟÆR *@þ Ḋ  F  fḊ

Wypróbuj online!

Oto zupełnie inne rozwiązanie. To ciekawa hybryda wydajnego i nieefektywnego, wykorzystująca wydajny algorytm rdzeniowy w bardzo nieefektywnym opakowaniu (do tego stopnia, że ​​nie radzi sobie z bardzo dużymi liczbami). Jak poprzednio, wszystkie białe znaki są bez znaczenia.

Oto jak to działa. Ḋ(która pojawia się kilka razy) to lista liczb od 2 do wejścia włącznie:

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

Podstawowa obserwacja tutaj jest taka, że ​​liczba jest doskonałą mocą na wiele sposobów, tylko jeśli jest to doskonała moc z wykładnikiem wykładniczym (to nie jest 1). Generujemy listę tych, w których podstawa wynosi od 2 do wejścia, a wykładnik jest liczbą złożoną od 4 do wejścia; jest to bardzo powolne, ponieważ generuje kilka naprawdę dużych liczb, z których wszystkie są odpowiedzią na pytanie. Następnie zachowujemy tylko te odpowiedzi, które są w zasięgu.

Łatwo byłoby zmienić to na wysoce wydajną odpowiedź, sprawdzając, jaka była maksymalna moc w zasięgu i nie powtarzając dalej, ale byłoby to o wiele więcej bajtów, a to jest golfowy kod.

Perl: 68 znaków

Pobiera maksimum (1000) $Ni zwraca odpowiedź @a.

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

Do całego programu potrzebuję kolejnych 18 znaków:

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

Rubin - 101 znaków (bez białych znaków)

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}

Działa przez 1 <= limit <= 100,000,0005 sekund.

Test

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

Galaretka , 13 znaczących znaków, wyzwanie postdatate języka

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

Wypróbuj online!

Wszystkie białe znaki tutaj są nieznaczne. Użyłem go, aby pokazać strukturę mojej odpowiedzi, jak zadaje pytanie.

Oto jak to działa:

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

Na przykład, testując n = 256, sprawdzamy, ile razy każda z liczb od 2 do 256 dzieli się na 256. Jedyne liczby, które dzielą więcej niż jeden raz, to 2 (który dzieli 8 razy), 4 (który dzieli 4 razy), 8 (który dzieli dwa razy) i 16 (który dzieli dwa razy). Kiedy więc podnosimy liczbę podziałów do ustalonych tam mocy, otrzymujemy:

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

Daje to oryginalną wartość 256, liczbę razy równą sposobowi, że 256 jest mocą doskonałą, plus jeden (ostatni element daje 256, ponieważ 256 = 256¹). Więc jeśli widzimy 256 więcej niż dwa razy w tablicy (i robimy w tym przypadku; 8² to 64, ale wszystkie inne „interesujące” elementy dają 256), to musi być idealna moc.