Hitung angka praktis

18

Definisi

Bilangan bulat positif nadalah 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, 18adalah 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 14bukan 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 xdan 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
Peter Taylor
sumber
(IMHO) ini bahkan dapat menjadi langkah yang menarik jika kode tercepat (per bahasa?) Menang
Tampilan Nama
4
@SargeBorsch Jadi Anda akan melihat daftar 250 ribu entri di seluruh jawaban
Dr. belisarius
@belisarius poin bagus. tapi saya pikir kecurangan seperti itu bisa dengan mudah dilarang. Atau masalahnya mungkin memerlukan jawaban yang benar untuk nomor apa pun , tetapi kemudian akan ada kesulitan ketika melakukannya dalam bahasa tanpa bilangan bulat besar di perpustakaan standar ...: /
Nama Tampilan
Saya memiliki satu optimasi algoritme dalam pikiran, tetapi dengan aturan saat ini saya terlalu malas untuk mengimplementasikannya: P
Display Name
4
@SargeBorsch, jika Anda tidak ingin bermain golf kode Anda bebas mengunggahnya ke sesuatu seperti gist.github.com dan letakkan tautan di komentar di sini atau di obrolan. FWIW Saya lebih suka golf kode dengan kendala kinerja yang besar daripada kode tercepat karena dua alasan: pertama, panjang kode lebih terukur secara objektif; kedua, ia memperkenalkan elemen pengorbanan: kecepatan optimisasi mana yang dapat ditinggalkan untuk mempersingkat kode tanpa merusak kinerja?
Peter Taylor

Jawaban:

5

J (99 karakter)

f=:3 :0
'n c'=.0 1
while.c<y do.
'p e'=.__ q:n=.n+2
c=.c+*/(}.p)<:}:1+*/\(<:p^e+1)%<:p
end.
n+n=0
)

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 250000menghitung dalam 120,6 detik, yang tidak cukup di bawah dua menit, tetapi mungkin pada komputer yang sedikit lebih masuk akal ini selesai dalam waktu.

Omar
sumber
6

Mathematica, 126 121 karakter

Terima kasih untuk belisarius.

Menggunakan rumus di wikipedia.

f=(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&

Contoh:

f[1]

1

f[8]

18

f[250000]

2764000

Butuh 70-an untuk menghitung f[250000]di komputer saya.

alephalpha
sumber
3
Saya pikir Anda bisa mendapatkan kinerja yang lebih baik dengan mengorbankan satu char dengan mem-bypass bilangan bulat ganjil
Dr. belisarius
1
Dalam mengurangi kode dari pengiriman OEIS, Anda memperlambat eksekusi 10 kali lipat. Hanya ingin tahu, "menurut Anda mengapa kode Anda berjalan jauh lebih lambat daripada contoh OEIS?"
DavidC
@belisarius Saran Anda memotong waktu menjadi dua, seperti yang diharapkan.
DavidC
2
Hal yang sama dalam 119 karakter:(i=j=1;While[j<#,If[And@@Thread[#[[;;,1]]<2+Most@DivisorSum[FoldList[#Power@@#2&,1,#],#&]&@FactorInteger@++i],j++]];i)&
Dr. belisarius
3

Haskell - 329

s 1=[]
s n=p:(s$div n p)where d=dropWhile((/=0).mod n)[2..ceiling$sqrt$fromIntegral n];p=if null d then n else head d
u=foldr(\v l@((n,c):q)->if v==n then(n,c+1):q else(v,1):l)[(0,1)]
i z=(z<2)||(head w==2)&&(and$zipWith(\(n,_)p->n-1<=p)(tail n)$scanl1(*)$map(\(n,c)->(n*n^c-1)`div`(n-1))n)where w=s z;n=u w
f=((filter i[0..])!!)

Contoh:

> f 1
1
> f 13
32
> f 1000
6500

Berikut ini adalah rangkaian pengujian kecil (tergantung pada yang di atas):

import Data.Time.Clock
import System.IO

test x = do
    start <- getCurrentTime
    putStr $ (show x) ++ " -> " ++ (show $ f x)
    finish <- getCurrentTime
    putStrLn $ " [" ++ (show $ diffUTCTime finish start) ++ "]"

main = do
    hSetBuffering stdout NoBuffering
    mapM_ test [1, 8, 1000, 250000, 1000000, 3000000]

Hasil tes setelah dikompilasi dengan ghc -O3:

1 -> 1 [0.000071s]
8 -> 18 [0.000047s]
1000 -> 6500 [0.010045s]
250000 -> 2764000 [29.084049s]
1000000 -> 12214770 [201.374324s]
3000000 -> 39258256 [986.885397s]
mniip
sumber
Ketika saya mencoba ini dalam ghci itu mengeluh parse error on input `='. Apakah saya perlu menggunakan bendera atau lainnya?
Peter Taylor
1
@PeterTaylor Anda tidak dapat menempelkan definisi fungsi ke dalam ghci seperti itu. Yang paling sederhana yang dapat Anda lakukan adalah menyimpannya asdf.hsdan menjalankannya ghci asdf.hs, lalu dari sana Anda dapat mengaksesnyaf
mniip
@PeterTaylor ghc --make -O3 [filename]. Anda juga bisa memuatnya dalam ghci dengan :l [filename]tetapi mengingat kendala waktu yang dikompilasi mungkin yang terbaik. :)
Jonathan Van Matre
@JonathanVanMatre seperti yang terlihat di komentar di atas, ghcimemuat file yang ditentukan dalam argumennya
mniip
Ah, baiklah. Sementara itu saya sudah menjalankannya dengan kerangka uji Anda dan ghc. Komputer Anda lebih cepat daripada komputer saya, tetapi masih dalam kriteria kinerja pada komputer saya pada 98 detik.
Peter Taylor
2

Javascript, 306 307 282B

function y(r){for(n=r-1,k=1;n;k++)if(p=[],e=[],c=0,P=s=1,!((x=k)%2|1==x)){while(x>1){for(f=x,j=2;j<=Math.sqrt(f);j++)if(f%j==0){f=j;break}f!=p[c-1]?(p.push(f),e.push(2),c++):e[c-1]++,x/=f}for(i=0;c>i;i++){if(p[i]>P+1){s=0;break}P*=(Math.pow(p[i],e[i])-1)/(p[i]-1)}s&&n--}return k-1}

Kira-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/

alexander-brett
sumber
Pertanyaannya tidak meminta fungsi atau program (JS tidak memiliki kata kerja), jadi daripada tidak menghitung baris pertama Anda harus membungkus baris kedua dalam deklarasi fungsi dan mengganti final k--;dengan return k-1. Meskipun itu sedikit meningkatkan jumlah byte Anda, Anda dapat menyimpan beberapa dengan hal-hal seperti mengganti p[i]>=P+2dengan p[i]>P+1(dan mungkin dengan menghapus panggilan fungsi internal dan menggunakan breaksebaliknya).
Peter Taylor
Saya pikir bagian "pengujian sigma" dapat ditulis ulang untuk ukuran dan kecepatan: jsfiddle.net/3DTSa . Meskipun solusi JS ini sangat cepat.
user2846289