Sebuah jumlah yang melimpah adalah nomor di mana jumlah dari pembagi tepat adalah lebih besar dari jumlah aslinya. Sebagai contoh, pembagi yang tepat dari 12 adalah:
1, 2, 3, 4, 6
Dan menjumlahkan hasil ini dalam 16. Karena 16 lebih besar dari 12, 12 berlimpah. Perhatikan bahwa ini tidak termasuk "Angka sempurna", mis. Angka yang sama dengan jumlah pembagi yang tepat, seperti 6 dan 28.
Tugas Anda hari ini adalah menulis program atau fungsi yang menentukan apakah jumlahnya banyak atau tidak. Program Anda harus mengambil bilangan bulat tunggal sebagai input, dan menampilkan nilai kebenaran / kepalsuan tergantung pada apakah jumlahnya berlimpah atau tidak. Anda dapat mengasumsikan bahwa input akan selalu valid dan lebih besar dari 0, jadi untuk input yang buruk, perilaku tidak terdefinisi baik-baik saja.
Anda dapat mengambil input dan output Anda dalam format yang masuk akal, misalnya STDIN / STDOUT, file, atau argumen / nilai pengembalian semua akan diterima.
Untuk referensi, berikut adalah angka melimpah hingga 100:
12,
18,
20,
24,
30,
36,
40,
42,
48,
54,
56,
60,
66,
70,
72,
78,
80,
84,
88,
90,
96,
100
Dan banyak lagi dapat ditemukan di A005101
Karena ini adalah kode-golf , celah standar ditolak, dan cobalah menulis kode sesingkat mungkin dalam bahasa apa pun yang Anda pilih!
sumber
Jawaban:
ECMAScript Regex,
1085855597536511508504 byteMencocokkan jumlah yang melimpah di ECMAScript regex adalah binatang yang sama sekali berbeda dari melakukannya dalam hampir semua rasa regex lainnya. Kurangnya referensi atau rekursi maju / bersarang berarti bahwa tidak mungkin untuk secara langsung menghitung atau menjaga total apa pun yang berjalan. Kurangnya tampilan membuatnya sering menjadi tantangan bahkan untuk memiliki cukup ruang untuk bekerja.
Banyak masalah harus didekati dari perspektif yang sama sekali berbeda, dan Anda akan bertanya-tanya apakah mereka dapat dipecahkan sama sekali. Ini memaksa Anda untuk menggunakan jaring yang jauh lebih luas dalam menemukan properti matematika mana dari angka yang Anda kerjakan yang mungkin dapat digunakan untuk membuat masalah tertentu dapat dipecahkan.
Kembali pada bulan Maret-April 2014 saya membangun solusi untuk masalah ini di ECMAScript regex. Pada awalnya saya punya alasan untuk mencurigai masalah itu benar-benar mustahil, tetapi kemudian teukon ahli matematika membuat sketsa ide yang membuat kasus yang menggembirakan untuk membuatnya terlihat dapat dipecahkan - tetapi ia menjelaskan bahwa ia tidak berniat membangun regex (dia telah berkompetisi / bekerja sama dengan saya dalam membangun / golf regex sebelumnya, tetapi mencapai batasnya pada titik ini dan puas untuk membatasi kontribusinya lebih lanjut untuk berteori).
Seperti dengan regex saya diposting beberapa hari yang lalu, saya akan memberikan peringatan: Saya sangat merekomendasikan belajar bagaimana menyelesaikan masalah matematika unary di ECMAScript regex. Ini merupakan perjalanan yang menarik bagi saya, dan saya tidak ingin merusaknya bagi siapa pun yang mungkin ingin mencobanya sendiri, terutama mereka yang tertarik pada teori bilangan. Lihat posting itu untuk daftar masalah yang direkomendasikan untuk ditandai dengan spoiler bertanda satu per satu.
Jadi jangan membaca lebih jauh jika Anda tidak ingin sihir regex unary yang dalam rusak bagi Anda . Posting saya sebelumnya hanya sedikit. Jika Anda ingin mencoba mencari tahu sendiri keajaiban ini, saya sangat menyarankan memulai dengan menyelesaikan beberapa masalah dalam ECMAScript regex sebagaimana diuraikan dalam pos yang ditautkan di atas.
Sebelum memposting regex ECMAScript saya, saya pikir akan menarik untuk menganalisis .NET murni solusi regex Martin Ender ,
^(?!(1(?<=(?=(?(\3+$)((?>\2?)\3)))^(1+)))*1$)
. Ternyata sangat mudah untuk memahami regex itu, dan elegan dalam kesederhanaannya. Untuk menunjukkan perbedaan antara solusi kami, berikut adalah versi regex-nya yang dikomentari dan dicetak dengan bagus (tetapi tidak dimodifikasi):Coba .NET regex online
Sekarang, kembali ke regex ECMAScript saya. Pertama, ini dalam format mentah, spasi-dan-komentar-bebas:
^(?=(((?=(xx+?)\3+$)(x+)\4*(?=\4$))+(?!\3+$)(?=(xx(x*?))\5*$)x)(x+))(?=\1(x(x*))(?=\8*$)\6\9+$)(?=(.*)((?=\8*$)\5\9+$))(?=(x*?)(?=(x\11)+$)(?=\12\10|(x))(x(x*))(?=\15*$)(?=\11+$)\11\16+$)(?=(x(x*))(?=\17*$)\7\18+$)((?=(x*?(?=\17+$)(?=\17+?(?=((xx(x*))(?=\18+$)\22*$))(x+).*(?=\17$)\24*(?=\24$)(?!(xx+)\25*(?!\22+$)\25$)\22+$)((?=(x\7)+$)\15{2}\14|)))(?=.*(?=\24)x(x(x*))(?=\28*$)\23\29*$)(?=.*(x((?=\28*$)\22\29+$)))(.*(?!\30)\20|(?=.*?(?!x\20)(?=\30*$)(x(x*))(?=\33*$)(?=\31+$)\31\34+$).*(?=\33\21$)))+$
(ubah
\14
ke\14?
untuk kompatibilitas dengan PCRE, .NET, dan hampir semua citarasa regex lainnya yang bukan ECMAScript)Cobalah online!
Cobalah online! (lebih cepat, versi 537 byte regex)
Dan sekarang ringkasan singkat dari kisah di baliknya.
Pada awalnya itu sangat tidak jelas, setidaknya bagi saya, bahwa bahkan mungkin untuk mencocokkan bilangan prima dalam kasus umum. Dan setelah menyelesaikan itu, hal yang sama berlaku untuk kekuatan 2. Dan kemudian kekuatan angka gabungan. Dan kotak yang sempurna. Dan bahkan setelah menyelesaikannya, melakukan perkalian secara umum tampaknya tidak mungkin pada awalnya.
Dalam loop skrip ECMAS, Anda hanya dapat melacak satu nomor yang berubah; angka itu tidak dapat melebihi input, dan harus berkurang di setiap langkah. Regex kerja pertama saya untuk mencocokkan pernyataan perkalian yang benar A * B = C adalah 913 byte, dan bekerja dengan memfaktorkan A, B, dan C ke dalam kekuatan utama mereka - untuk setiap faktor utama, berulang kali membagi pasangan faktor daya utama A dan C dengan basis utama mereka sampai yang sesuai dengan A mencapai 1; yang berkorespondensi dengan C kemudian dibandingkan dengan faktor kekuatan utama B. Kedua kekuatan dari prime yang sama ini "multiplexed" menjadi satu angka dengan menambahkannya bersama-sama; ini akan selalu dipisahkan secara jelas pada setiap iterasi loop berikutnya, untuk alasan yang sama bahwa sistem angka posisi bekerja.
Kami mendapat perkalian hingga 50 byte menggunakan algoritma yang sama sekali berbeda (yang teukon dan saya dapat tiba secara mandiri, meskipun hanya butuh beberapa jam dan ia langsung ke sana, sedangkan saya butuh beberapa hari bahkan setelah itu menarik perhatian saya bahwa ada metode singkat): untuk A≥B, A * B = C jika ada hanya jika C adalah angka terkecil yang memenuhi C≡0 mod A dan C≡B mod A-1. (Mudahnya, perkecualian A = 1 tidak memerlukan penanganan khusus di regex, di mana 0% 0 = 0 menghasilkan kecocokan.) Saya hanya tidak bisa melupakan seberapa rapi itu bahwa cara elegan untuk melakukan penggandaan ada dalam suatu rasa regex minimal. (Dan persyaratan A≥B dapat diganti dengan persyaratan bahwa A dan B adalah kekuatan utama dari kekuatan yang sama. Untuk kasus A≥B, ini dapat dibuktikan menggunakan teorema sisa Cina.)
Jika ternyata tidak ada algoritma yang lebih sederhana untuk perkalian, jumlah regex yang melimpah mungkin akan berada di urutan sepuluh ribu byte atau lebih (bahkan dengan mempertimbangkan bahwa saya memasukkan algoritma 913 byte turun ke 651 byte). Ia melakukan banyak perkalian dan pembagian, dan regex ECMAScript tidak memiliki subrutin.
Saya mulai mengerjakan masalah angka melimpah secara tangensial pada tanggal 23 Maret 2014, dengan membangun solusi untuk apa yang pada saat itu tampaknya menjadi sub-masalah ini: Mengidentifikasi faktor utama dari multiplisitas tertinggi, sehingga dapat dibagi dari N di awal, meninggalkan ruang untuk melakukan beberapa perhitungan yang diperlukan. Pada saat itu, rute ini tampaknya merupakan rute yang menjanjikan untuk ditempuh. (Solusi awal saya akhirnya menjadi cukup besar pada 326 byte, kemudian golf turun menjadi 185 byte.) Tetapi metode teukon sketsa akan menjadi sangat rumit, sehingga ternyata, saya mengambil rute yang agak berbeda. Itu terbukti cukup untuk membagi faktor daya prima terbesar N yang sesuai dengan faktor prima terbesar pada N; melakukan ini untuk prime multiplicity tertinggi akan menambah kompleksitas dan panjang yang tidak perlu ke regex.
Yang tersisa adalah memperlakukan jumlah pembagi sebagai produk dari jumlah bukan jumlah yang lurus. Seperti yang dijelaskan oleh teukon pada 14 Maret 2014:
Saya terpesona melihat hal ini. Saya tidak pernah berpikir untuk menghitung jumlah alikuot dengan cara itu, dan formula inilah yang membuat solvabilitas pencocokan angka melimpah di ECMAScript regex terlihat masuk akal.
Pada akhirnya, alih-alih menguji untuk hasil penjumlahan atau perkalian yang melebihi N, atau menguji bahwa hasil seperti itu yang dipisah-pisahkan oleh M melebihi N / M, saya melakukan pengujian jika hasil pembagian kurang dari 1. Saya tiba di versi kerja pertama pada 7 April 2014.
Sejarah lengkap optimasi golf saya di regex ini ada di github. Pada titik tertentu satu optimasi akhirnya membuat regex jauh lebih lambat, jadi sejak saat itu saya mempertahankan dua versi. Mereka:
regex untuk pencocokan angka berlimpah.txt
regex untuk pencocokan angka berlimpah - shortest.txt
Regex ini sepenuhnya kompatibel dengan ECMAScript dan PCRE, tetapi optimasi baru-baru ini melibatkan penggunaan grup tangkap yang berpotensi tidak berpartisipasi
\14
, jadi dengan menjatuhkan kompatibilitas PCRE dan mengubahnya\14?
menjadi\14
keduanya dapat dikurangi dengan 1 byte.Ini adalah versi terkecil, dengan optimasi yang diterapkan (membuatnya hanya ECMAScript), diformat ulang agar sesuai dengan blok kode StackExchange dengan (kebanyakan) tidak diperlukan pengguliran horizontal:
sumber
Python 2 ,
4140 byteOutput adalah melalui kode keluar , jadi 0 benar dan 1 palsu.
Cobalah online!
Bagaimana itu bekerja
Setelah mengatur semua n , k , dan j ke input dari STDIN, kita masukkan loop while . Kata loop akan pecah segera setelah -k - 1 = ~ k ≥ 0 , yaitu, k ≤ -1 / k <0 .
Dalam setiap iterasi, pertama-tama kita mengurangi j untuk mempertimbangkan hanya pembagi n yang tepat . Jika j adalah pembagi dari n ,
n%j
hasilkan 0 dan j >> n% j * n = j / 2 0 = j akan dikurangi dari k . Namun, jika j tidak tidak membagi n ,n%j
positif, jadin%j*n
setidaknya n> log 2 j dan j >> n% j * n = j / 2 n% j * n = 0 dikurangi dari k .Untuk angka yang melimpah, k akan mencapai nilai negatif sebelum atau ketika j menjadi 1 , karena jumlah pembagi n yang tepat benar-benar lebih besar dari n . Dalam hal ini, kami keluar dari loop sementara dan program selesai secara normal.
Namun, jika n adalah tidak berlimpah, j akhirnya mencapai 0 . Dalam hal ini,
n%j
melempar ZeroDivisionError dan program keluar dengan kesalahan.sumber
~k<0
mewah, tapi saya pikir-1<k
juga melakukan trik;)Brachylog , 5 byte
Cobalah online!
Penjelasan
sumber
Jelly , 3 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Python , 44 byte
Cobalah online!
sumber
range(n)
. Modulus sial itu nolMathematica, 17 byte
Penjelasan
sumber
AbundantNumberQ
, jadi itu akan menghemat beberapa byte :)05AB1E ,
54 byte-1 byte berkat skottinet
Cobalah online! atau Coba 0 hingga 100
sumber
Retina ,
5045 byteInput dalam unary , output
1
untuk angka melimpah,0
jika tidakTidak ada yang khusus-Retina tentang solusi ini. Di atas adalah .NET regex murni yang hanya cocok dengan angka berlimpah.
Cobalah online! (Test suite yang menyaring input desimal dengan regex di atas.)
sumber
Retina , 34 byte
Hitungan byte mengasumsikan penyandian ISO 8859-1.
Input dalam unary , output
1
untuk angka melimpah,0
jika tidakCobalah online!
Penjelasan
Kami mulai dengan mendapatkan semua pembagi input. Untuk melakukan ini, kami mengembalikan (
!
) semua kecocokan tumpang tindih (&
) (M
) dari regex(1+)$(?<=^\1+)
. Regex cocok dengan beberapa akhiran input, asalkan seluruh input adalah kelipatan dari akhiran itu (yang kami pastikan dengan mencoba mencapai awal untuk string menggunakan hanya salinan akhiran itu). Karena cara mesin regex mencari kecocokan, ini akan menghasilkan daftar pembagi dalam urutan menurun (dipisahkan oleh baris baris).Panggung itu sendiri hanya cocok dengan umpan baris (
¶
) dan menghapusnya. Namun,1>
batasnya adalah, yang melewatkan pertandingan pertama. Jadi ini secara efektif menambahkan semua pembagi kecuali input itu sendiri. Kita berakhir dengan input pada baris pertama dan jumlah semua pembagi yang tepat pada baris kedua.Akhirnya, kami mencoba untuk mencocokkan setidaknya satu lagi
1
di baris kedua daripada yang ada di baris pertama. Jika itu masalahnya, jumlah pembagi yang tepat melebihi input. Retina menghitung jumlah kecocokan dari regex ini, yang akan1
berjumlah banyak dan0
sebaliknya.sumber
Majelis 8086,
23282524 byteBelum dirakit:
Contoh program pengujian, pengujian N = [12..1000]:
Output [2..1000]
Output [12500..12700]
Output [25100..25300]
Pembaruan:
sumber
JLE
denganJBE
menggandakan rentang angka yang dapat diuji ini sebelum overflows mulai menyebabkannya memberikan negatif palsu. Kemudian alih-alih mulai gagal pada 12600 (aliquot jumlah 35760), itu akan mulai gagal pada 25200 (jumlah aliquot 74744). Yang lebih baik adalah mendeteksi flag carry dan memperlakukannya sebagai angka yang melimpah tanpa perlu menghitung jumlah sebenarnya> 16 bit.JC
atauJNC
untuk bertindak apakah jumlahnya banyak atau tidak.Sebenarnya , 5 byte
Cobalah online!
sumber
05AB1E , 4 byte
Cobalah online!
Bagaimana itu bekerja
Maaf memposting di pertanyaan lama, saya baru saja melalui posting lama untuk latihan dan melihat solusi saya lebih pendek dari solusi 05AB1E terbaik berikutnya.
sumber
Sorry to post in old question
Jangan khawatir tentang itu! Saya selalu senang melihat jawaban tentang tantangan lama saya, dan sebenarnya dianjurkan di sini . :)PARI / GP , 15 byte
Variannya
n->sigma(n,-1)>2
, sayangnya, lebih lama.sumber
Java 8, 53 byte (lebih banyak jika Anda memasukkan kode upacara)
Cobalah online
Penjelasan:
sumber
return
jika saya tidak salah, sehingga akan lebih pendek:n->IntStream.range(1,n).filter(e->n%e<1).sum()>n
(tidak 100% jika ini benar, saya hampir tidak pernah memprogram di Java 8). Selamat datang di PPCG!n->java.util.stream.IntStream.range(1,n).filter(e->n%e<1).sum()>n
65 byte (dengan asumsi saya mendapatkan paket langsung dari atas kepala saya)Powershell,
5149 BytesSaya berharap saya bisa menghapus beberapa tanda kurung.
-2 Terima kasih kepada AdmBorkBork, alih-alih tidak menghitung input pada rentang awal, kami hanya memperhitungkannya pada pemeriksaan akhir.
Loop melalui rentang
1..
ke$i
nput, minus 1, temukan di mana (?
) modulo input terbalik oleh angka saat ini adalah$true
(alias hanya 0) - maka-join
semua angka tersebut bersama-sama dengan+
daniex
string yang dihasilkan untuk menghitungnya, kemudian lihat apakah jumlah bagian ini lebih besar dari input.sumber
param($i)((1..$i|?{!($i%$_)})-join"+"|iex)-gt2*$i
MATL, 6 byte
Output 1 untuk angka melimpah, 0 sebaliknya.
Bagaimana itu bekerja
sumber
QBIC , 22 byte
Ini adalah adaptasi dari tes primitif QBIC . Alih-alih menghitung pembagi dan memeriksa apakah itu kurang dari tiga, ini menjumlahkan pembagi yang tepat. Ini hanya berjalan di sepanjang setengah dari
1 to n
, di mana tes primality berjalan1 to n
sepenuhnya.Penjelasan:
sumber
JavaScript (ES6), 33 byte
sumber
Japt ,
9 76 byteDisimpan 2 byte berkat produk ETH. Disimpan 1 byte berkat obarakon.
Cobalah online!
sumber
â
1 byte, setidaknya dalam unicode (0xE2).â
satu byte.â
diberi argumen yang benar, itu akan menghapus angka aktual dari daftar yang tersisa, sehingga Anda dapat melakukanâ1 x >U
untuk menyimpan beberapa byte :-)<Uâ1 x
untuk menghemat satu byte. Japt menambahkanU
di depan program.Cubix , 38 byte
Coba di sini
0I:
- mengatur stack dengan 0, n, n (s, n, d)^
- mulai dari loop)?
- decrement d dan uji untuk 0. 0 keluar loop%?
-mod terhadap n dan uji. 0 sebab;rrw+s;rU
yang berputar s ke atas dan menambahkan d, memutar s ke bawah dan bergabung kembali loop;<
- Bersihkan dan bergabung kembali loop.Pada loop keluar
;<
- Hapus d dari tumpukan dan redirect-?
- Hapus n dari s dan uji, 0LOU@
belok kiri, output dan keluar, negatif0O@
mendorong nol, output dan keluar. positif;O
menghapus perbedaan dan keluaran n. Jalur kemudian melewati belok kiri yang mengarahkan ke@
pintu keluarsumber
Bash Murni, 37 byte
Terima kasih kepada @ Dennis untuk mengatur ulang kode - menghemat 6 byte dan menghilangkan output insidental ke stderr.
Input dilewatkan sebagai argumen.
Output dikembalikan dalam kode keluar: 0 untuk berlimpah, 1 untuk tidak berlimpah.
Output ke stderr harus diabaikan.
Tes berjalan:
sumber
RProgN , 8 Bytes
Dijelaskan
Cobalah online!
sumber
Batch, 84 byte
Output
-1
untuk jumlah yang banyak,0
jika tidak. Bekerja dengan mengurangi semua faktor dari2n
dan kemudian menggeser 31 hasil tempat untuk mengekstrak bit tanda. Formulasi alternatif, juga 84 byte:Output
1
untuk jumlah yang melimpah. Bekerja dengan mengurangi semua faktor darin
dan kemudian membandingkan hasilnya dengan-n
. (set/a
adalah satu-satunya cara Batch melakukan aritmatika jadi saya tidak dapat dengan mudah mengatur loop.)sumber
Perl 6,
7224 byte1..a
.a
.a
.Berkat @ b2gills.
sumber
$^a
setelah yang pertama dapat disingkat menjadi adil$a
. tetapi bahkan lebih singkat jika Anda menuliskannya{$_ <sum grep $_%%*,^$_}
juga Melihat versi sebelumnya,[+](LIST)
berfungsi (tanpa spasi)J, 19 byte
Terima kasih kepada Conor O'Brien karena memotongnya menjadi 19 byte!
<[:+/i.#~i.e.]%2+i.
Sebelumnya: (34 byte)
f=:3 :'(+/((i.y)e.y%2+i.y)#i.y)>y'
Mengembalikan 1 jika berlimpah dan 0 jika tidak.
Keluaran:
sumber
f=:
sebagai bagian dari jumlah byte Anda. Juga, Anda bisa turun ke 19 dengan mengonversi ke kata kerja diam-diam:<[:+/i.#~i.e.]%2+i.
(f g h) y' is the same as
(fy) g (hy). When
f` adalah penutup,([: g h) y
kira-kira sama dengang h y
. Adapun~
, ini beralih argumen kiri dan kanan. Penting untuk diketahui bahwa~
itu bukan kata kerja tetapi sebenarnya kata keterangan. Itu memodifikasi kata kerja. Misalnya, kita dapat memiliki sesuatu seperti2 %~ 8
. Di sini,~
memodifikasi%
untuk mengalihkan argumennya, sehingga ekspresi setara dengan8 % 2
.#~
dievaluasi setelah kata kerja di sebelah kanannya dieksekusi, jadi argumen kiri menjadi hasil di sebelah kananPyth, 11 byte
Tua:
Saya tidak dapat menggunakan
!%
sebagai pfn untuk#
, karena ini dua fungsi. Membuat saya sedih :(.sumber
>sPf!%QTS
k ,
19 1615 bytePengembalian
1
untuk yang benar, dan0
untuk yang salah.Cobalah online!
sumber
PowerShell , 43 byte
Cobalah online!
sumber
Common Lisp, 63 byte
Cobalah online!
sumber
F #, 51 byte
Cobalah online!
Saring semua angka yang tidak terbagi rata
n
, lalu jumlahkan dan bandingkann
.sumber