Definisi
Bilangan bulat positif n
adalah angka praktis (OEIS urutan A005153 ) jika semua bilangan bulat positif yang lebih kecil dapat direpresentasikan sebagai jumlah dari pembagi yang berbeda dari n
.
Sebagai contoh, 18
adalah angka praktis: pembagi nya adalah 1, 2, 3, 6, 9, dan 18, dan bilangan bulat positif lainnya yang lebih kecil dari 18 dapat dibentuk sebagai berikut:
4 = 1 + 3 5 = 2 + 3 7 = 1 + 6
8 = 2 + 6 10 = 1 + 9 11 = 2 + 9
12 = 3 + 9 = 1 + 2 + 9 = 1 + 2 + 3 + 6
13 = 1 + 3 + 9 14 = 2 + 3 + 9 15 = 6 + 9
16 = 1 + 6 + 9 17 = 2 + 6 + 9
Tetapi 14
bukan angka praktis: pembagi-nya adalah 1, 2, 7, dan 14, dan tidak ada himpunan bagian yang menambah 4, 5, 6, 11, 12, atau 13.
Tantangan
Menulis sebuah program, fungsi, atau kata kerja yang mengambil sebagai masukan bilangan bulat positif x
dan baik kembali atau cetakan x th nomor praktis, diindeks dari 1 untuk konsistensi dengan Oei. Kode Anda harus cukup efisien sehingga dapat menangani input hingga 250000 dalam waktu kurang dari dua menit pada komputer desktop yang masuk akal. (NB implementasi referensi saya di Java mengelola 250000 dalam waktu kurang dari 0,5 detik, dan implementasi referensi saya di Python mengelolanya dalam 12 detik).
Uji kasus
Input Expected output
1 1
8 18
1000 6500
250000 2764000
1000000 12214770
3000000 39258256
sumber
Jawaban:
J (99 karakter)
Karena pernyataan masalah meminta "program, fungsi atau kata kerja ", seseorang harus membuat pengajuan J. J orang akan melihat saya tidak benar-benar golf (!) Atau mengoptimalkan ini. Seperti entri lainnya, saya menggunakan teorema Stewart, yang disebutkan di tautan OEIS, untuk menguji apakah setiap bilangan genap praktis atau tidak.
Saya tidak memiliki akses siap ke "komputer desktop yang masuk akal" dengan J diinstal. Pada netbook saya yang berusia enam tahun
f 250000
menghitung dalam 120,6 detik, yang tidak cukup di bawah dua menit, tetapi mungkin pada komputer yang sedikit lebih masuk akal ini selesai dalam waktu.sumber
Mathematica,
126121 karakterTerima kasih untuk belisarius.
Menggunakan rumus di wikipedia.
Contoh:
Butuh 70-an untuk menghitung
f[250000]
di komputer saya.sumber
(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&
Haskell - 329
Contoh:
Berikut ini adalah rangkaian pengujian kecil (tergantung pada yang di atas):
Hasil tes setelah dikompilasi dengan
ghc -O3
:sumber
parse error on input `='
. Apakah saya perlu menggunakan bendera atau lainnya?asdf.hs
dan menjalankannyaghci asdf.hs
, lalu dari sana Anda dapat mengaksesnyaf
ghc --make -O3 [filename]
. Anda juga bisa memuatnya dalam ghci dengan:l [filename]
tetapi mengingat kendala waktu yang dikompilasi mungkin yang terbaik. :)ghci
memuat file yang ditentukan dalam argumennyaghc
. Komputer Anda lebih cepat daripada komputer saya, tetapi masih dalam kriteria kinerja pada komputer saya pada 98 detik.Javascript,
306 307282BKira-kira 250rb 6s di laptop saya.
Kode un-golfed yang dikomentari: http://jsfiddle.net/82xb9/3/ sekarang dengan sigma-testing yang lebih baik dan kondisi if yang lebih baik (terima kasih komentar)
Versi pra-edit: http://jsfiddle.net/82xb9/ http://jsfiddle.net/82xb9/1/
sumber
k--;
denganreturn k-1
. Meskipun itu sedikit meningkatkan jumlah byte Anda, Anda dapat menyimpan beberapa dengan hal-hal seperti menggantip[i]>=P+2
denganp[i]>P+1
(dan mungkin dengan menghapus panggilan fungsi internal dan menggunakanbreak
sebaliknya).