Tantangan

Tugas Anda adalah menulis sebuah program atau fungsi yang, diberi bilangan bulat positif N , menemukan semua bilangan bulat positif kurang dari atau sama dengan N yang dapat dinyatakan sebagai kekuatan sempurna dalam lebih dari satu cara.

Definisi

Kekuatan sempurna didefinisikan sebagai angka yang saya temukan oleh m ^ k , di mana:

• m dan i adalah bilangan bulat positif
• m! = k

Uji Kasus

input -> output
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

Harap berikan versi yang dapat dibaca dan dikomentari juga.

Mathematica: 103 karakter

Spasi dapat dihapus

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

Pemakaian:

%[81]
{16, 64, 81}

Jelly , 11 byte yang berarti, tantangan tanggal bahasa

ḊḟÆR *@þ Ḋ  F  fḊ

Cobalah online!

Inilah solusi yang sama sekali berbeda. Yang satu ini merupakan campuran yang aneh dari yang efisien dan tidak efisien, menggunakan algoritma inti yang efisien dalam pembungkus yang sangat tidak efisien (sedemikian rupa sehingga tidak dapat menangani angka yang sangat besar). Seperti sebelumnya, semua spasi putih tidak ada artinya.

Begini cara kerjanya. Ḋ(yang muncul beberapa kali) adalah daftar angka dari 2 hingga input inklusif:

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

Pengamatan dasar di sini adalah bahwa angka adalah kekuatan sempurna dalam banyak hal, hanya jika itu adalah kekuatan sempurna dengan eksponen komposit (yang bukan 1). Kami membuat daftar yang basisnya dari 2 ke input, dan eksponen adalah bilangan komposit dari 4 ke input; ini sangat lambat karena menghasilkan beberapa angka yang sangat besar, yang semuanya merupakan jawaban untuk pertanyaan itu. Maka kami hanya menyimpan jawaban yang ada dalam jangkauan.

Sangat mudah untuk memodifikasi ini menjadi jawaban yang sangat efisien, dengan mencari tahu apa daya maksimum dalam jangkauan dan tidak mengulangi lebih jauh, tetapi itu akan menjadi lebih banyak byte, dan ini adalah kode-golf.

Perl: 68 karakter

Mendapat maksimum (1000) dalam $Ndan mengembalikan jawaban dalam @a.

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

Untuk keseluruhan program, saya membutuhkan 18 karakter lagi:

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

Ruby - 101 karakter (tanpa spasi)

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}

Bekerja 1 <= limit <= 100,000,000dalam 5 detik.

Uji

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

Jeli , 13 karakter yang berarti, tantangan tanggal bahasa

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

Cobalah online!

Semua spasi putih di sini tidak signifikan. Saya menggunakannya untuk menunjukkan struktur jawaban saya, ketika pertanyaan diajukan.

Begini cara kerjanya:

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

Jadi misalnya, ketika menguji n = 256, kami memeriksa berapa kali masing-masing angka dari 2 hingga 256 dibagi menjadi 256. Satu-satunya angka yang membagi lebih dari sekali adalah 2 (yang membagi 8 kali), 4 (yang membagi 4 kali), 8 (yang membagi dua), dan 16 (yang membagi dua). Jadi, ketika kita meningkatkan jumlah divisi ke kekuatan yang ditentukan di sana, kita mendapatkan:

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

Ini menghasilkan nilai asli, 256, beberapa kali sama dengan cara 256 adalah kekuatan sempurna, ditambah satu (elemen terakhir menghasilkan 256 karena 256 = 256¹). Jadi jika kita melihat 256 lebih dari dua kali dalam array (dan kita lakukan dalam kasus ini; 8² adalah 64 tetapi elemen "menarik" lainnya semua menghasilkan 256), itu harus menjadi kekuatan yang sempurna.