Sebuah nomor Proth , dinamai François Proth, adalah angka yang dapat dinyatakan sebagai
N = k * 2^n + 1
Di mana k
bilangan bulat positif ganjil dan n
bilangan bulat positif sehingga 2^n > k
. Mari kita gunakan contoh yang lebih konkret. Ambil 3. 3 adalah nomor Proth karena dapat ditulis sebagai
(1 * 2^1) + 1
dan 2^1 > 1
puas. 5 Juga merupakan nomor Proth karena dapat ditulis sebagai
(1 * 2^2) + 1
dan 2^2 > 1
puas. Namun, 7 bukan nomor Proth karena satu-satunya cara untuk menuliskannya N = k * 2^n + 1
adalah
(3 * 2^1) + 1
dan 2^1 > 3
tidak puas.
Tantangan Anda cukup sederhana: Anda harus menulis sebuah program atau fungsi yang, diberi bilangan bulat postive, menentukan apakah itu nomor Proth atau tidak. Anda dapat mengambil input dalam format apa pun yang masuk akal, dan akan menghasilkan nilai kebenaran jika itu adalah nomor Proth dan nilai palsu jika bukan. Jika bahasa Anda memiliki fungsi "Deteksi nomor proth", Anda dapat menggunakannya.
Tes IO
Berikut adalah 46 nomor Proth pertama hingga 1000. ( A080075 )
3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 289, 321, 353, 385, 417, 449, 481, 513, 545, 577, 609, 641, 673, 705, 737, 769, 801, 833, 865, 897, 929, 961, 993
Setiap input yang valid lainnya harus memberikan nilai palsu.
Seperti biasa, ini adalah kode-golf, jadi celah standar berlaku, dan jawaban terpendek dalam byte menang!
Teori bilangan menyenangkan fakta:
Perdana diketahui terbesar yang bukan Perdana Mersenne adalah 19249 * 2^13018586 + 1
, yang kebetulan juga menjadi nomor Proth!
sumber
Python, 22 byte
Ini adalah port jawaban Jelly saya . Uji di Ideone .
Bagaimana itu bekerja
Biarkan j menjadi bilangan bulat yang benar-benar positif. j + 1 mengaktifkan semua bit set trailing j dan bit unset yang berdekatan. Misalnya, 10011 2 + 1 = 10100 2 .
Karena ~ j = - (j + 1) = -j - 1 , -j = ~ j + 1 , jadi -n menerapkan hal di atas pada bitwise BUKAN dari j (yang mengubah semua bit), sehingga mengubah semua bit sebelum yang terakhir 1 .
Dengan mengambil j & -j - bitwise AND dari j dan -j - semua bit sebelum dan setelah bit set terakhir dibatalkan (karena tidak sama dalam j dan -j ), sehingga menghasilkan kekuatan tertinggi 2 yang membagi j secara merata.
Untuk input N , kami ingin menerapkan hal di atas ke N - 1 untuk menemukan 2 n , kekuatan tertinggi 2 yang membagi N - 1 . Jika m = N - 1 , -m = - (N - 1) = 1 - N , maka (N - 1) & (1 - N) menghasilkan 2 n .
Yang tersisa untuk diuji adalah jika 2 n > k . Jika k> 0 , ini benar jika dan hanya jika (2 n ) 2 > k2 n , yang benar itu sendiri jika dan hanya jika (2 n ) 2 ≥ k2 n + 1 = N .
Akhirnya, jika (2 n ) 2 = N = k2 n + 1 , 2 n harus ganjil ( 1 ) sehingga paritas kedua belah pihak dapat cocok, menyiratkan bahwa k = 0 dan N = 1 . Dalam hal ini (N - 1) & (1 - N) = 0 & 0 = 0 dan ((N - 1) & (1 - N)) 2 = 0 <1 = N .
Karena itu, ((N - 1) & (1 - N)) 2 > N benar jika dan hanya jika N adalah nomor Proth.
Mengabaikan ketidakakuratan floating point, ini setara dengan kode
N-1&1-N>N**.5
dalam implementasi.sumber
Python 2, 23 byte
sumber
Mathematica,
5048454038353129 byteMathematica umumnya menyebalkan ketika datang ke kode golf, tetapi kadang-kadang ada built-in yang membuat semuanya terlihat sangat bagus.
Sebuah tes:
Sunting: Sebenarnya, jika saya mencuri ide AND AND Dennis , saya bisa mendapatkannya hingga
232220 byte.Mathematica,
232220 byte (terima kasih A Simmons )sumber
g=
, fungsi murni tidak masalah!Select[Range@1000,f]
.05AB1E ,
1410 byteTerima kasih kepada Emigna karena telah menghemat 4 byte!
Kode:
Menggunakan pengkodean CP-1252 . Cobalah online! .
Penjelasan:
Untuk penjelasannya, mari kita gunakan angka 241 . Kami pertama-tama mengurangi angka satu per satu dengan
<
. Itu menghasilkan 240 . Sekarang, kami menghitung faktor utama (dengan duplikat) menggunakanÒ
. Faktor utama adalah:Kami membaginya menjadi dua bagian. Dengan menggunakan
2Q·0K
, kita mendapatkan daftar dua:Dengan
®2K
, kita mendapatkan daftar angka yang tersisa:Akhirnya, ambil produk keduanya.
[2, 2, 2, 2]
hasil menjadi 16 . Produk[3, 5]
hasil menjadi 15 .Test case ini benar sejak 16 > 15 .
sumber
<©Ó¬oD®s/›
atau<DÓ0èoDŠ/›
untuk 10.Brain-Flak ,
460350270266264188176 bytesCobalah online!
Penjelasan
Program melewati kekuatan dua dan empat hingga menemukan kekuatan dua lebih besar dari N-1. Ketika menemukannya, ia memeriksa pembagian N-1 dengan kekuatan dua menggunakan modulo dan output hasilnya
Program ini bukan tumpukan bersih. Jika Anda menambahkan 4 byte tambahan, Anda dapat membuatnya menjadi bersih:
sumber
MATL , 9 byte
Output yang sebenarnya adalah
1
. Falsy is0
atau output kosong. (Satu-satunya input yang menghasilkan output kosong adalah1
dan2
; sisanya menghasilkan salah satu0
atau1
).Cobalah online!
Penjelasan
Biarkan x menunjukkan input. Biarkan y menjadi kekuatan terbesar 2 yang membagi x −1, dan z = ( x −1) / y . Perhatikan bahwa z secara otomatis aneh. Maka x adalah angka Proth jika dan hanya jika y > z , atau ekuivalen jika y 2 > x −1.
sumber
Brachylog , 28 byte
Cobalah online!
Verifikasi semua testcans sekaligus. (Sedikit dimodifikasi.)
Penjelasan
Brachylog, yang merupakan turunan dari Prolog, sangat bagus dalam membuktikan berbagai hal.
Di sini, kami membuktikan hal-hal ini:
sumber
Haskell,
5546 byteSunting: Berkat nimi, sekarang 46 byte
sumber
sum[1| ... ]
. Di sini kita bisa pergi lebih jauh dan bergerak tes kesetaraan di depan|
dan memeriksa denganor
jika salah satu dari mereka adalah benar:f x=or[k*2^n+1==x|k<-...,n<-...,2^n>k]
.ECMAScript Regex,
484341 byteRegex Neil dan H.PWiz (keduanya juga citarasa ECMAScript) sangat cantik. Ada cara lain untuk melakukannya, yang secara kebetulan sangat rapi adalah 1 byte lebih banyak dari Neil, dan sekarang dengan golf yang disarankan H.PWiz (terima kasih!), Adalah 1 byte
lebihsedikit dari H.PWiz's.Peringatan: Meskipun ukuran regex ini kecil, ia mengandung spoiler utama . Saya sangat merekomendasikan belajar bagaimana memecahkan masalah matematika unary di ECMAScript regex dengan mencari tahu wawasan matematika awal secara mandiri. Ini adalah perjalanan yang menarik bagi saya, dan saya tidak ingin merusaknya untuk siapa pun yang mungkin ingin mencobanya sendiri, terutama mereka yang tertarik pada teori bilangan. Lihat posting ini sebelumnya untuk daftar masalah yang direkomendasikan untuk ditandai dengan spoiler bertanda satu per satu.
Jadi jangan membaca lebih jauh jika Anda tidak ingin beberapa sihir regex unary canggih dimanjakan untuk Anda . Jika Anda ingin mencoba mencari tahu sendiri keajaiban ini, saya sangat menyarankan memulai dengan memecahkan beberapa masalah dalam ECMAScript regex sebagaimana diuraikan dalam posting yang ditautkan di atas.
Jadi, regex ini bekerja cukup sederhana: Dimulai dengan mengurangi satu. Kemudian ia menemukan faktor ganjil terbesar, k . Kemudian kita bagi dengan k (menggunakan algoritma pembagian dijelaskan secara singkat dalam paragraf spoiler-tag dari nomor faktor saya posting regex ) Kami diam-diam melakukan pernyataan simultan bahwa hasil bagi lebih besar dari k . Jika divisi cocok, kami memiliki nomor Proth; jika tidak, kita tidak melakukannya.
Saya dapat menjatuhkan 2 byte dari regex ini (43 → 41) menggunakan trik yang ditemukan oleh Grimy yang dapat memperpendek pembagian dalam kasus bahwa hasil bagi dijamin lebih besar dari atau sama dengan pembagi.
Cobalah online!
sumber
Julia, 16 byte
Kredit ke @Dennis untuk jawabannya dan beberapa kiat bermain golf!
sumber
&
memiliki prioritas yang sama dengan*
.-~-x
bukan(1-x)
. Juga ada√x
bukanx^.5
, tetapi tidak menyimpan byte.R,
5250 byteProgram dimulai dengan membagi
N-1
(disebut di siniP
danx
)2
selama mungkin untuk menemukan2^n
bagian dari persamaan, meninggalkank=(N-1)/2^n
, dan kemudian menghitung apakah atau tidakk
lebih rendah daripada2^n
, menggunakan fakta bahwa2^n>x/2^n <=> (2^n)²>x <=> 2^2n>x
sumber
P=
di awal, dan mengubah ujung ke2^n>x
dan menyimpan seperti 5 atau 6 byteRegex (ECMAScript),
4038 byte-2 byte berkat Deadcode
Cobalah online!
Versi yang dikomentari:
sumber
^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$)
( Coba online )J, 10 byte
Berdasarkan solusi bitwise @Dennis .
Mengambil input
n
dan mengembalikan 1 jika itu adalah nomor Proth lain 0.Pemakaian
Penjelasan
sumber
AND
. keren!Retina 0.8.2 , 47 byte
Konversikan ke unary.
Konversi ke biner.
Jalankan formula generasi Proth berulang kali secara terbalik.
Cocokkan kasus dasar formula generasi Proth.
Sunting: Saya pikir itu benar-benar mungkin untuk mencocokkan nomor Proth secara langsung dengan nomor yang tidak disorot dengan satu regex. Ini saat ini membawa saya 47 byte, 7 byte lebih dari kode Retina saya saat ini untuk memeriksa apakah nomor unary adalah nomor Proth:
sumber
ECMAScript Regex, 42 byte
Cobalah online! (Menggunakan Retina)
Saya pada dasarnya kurangi 1, bagi dengan jumlah ganjil terbesar yang mungkin
k
, kemudian periksa bahwa setidaknyak+1
tersisa.Ternyata regex saya sangat mirip dengan yang Neil berikan di akhir jawabannya . Saya menggunakan
x(xx)*
bukan(x*)\2x
. Dan saya menggunakan metode yang lebih pendek untuk memeriksak < 2^n
sumber
(\3\3)*)$
ke(\3\3)*$)
$=
dan$.=
. Ini dapat ditingkatkan lebih baik lagi .Brain-Flak , 128 byte
Cobalah online!
Saya menggunakan algoritma yang sangat berbeda dari solusi Brain-Flak yang lebih lama .
Pada dasarnya, saya membaginya dengan 2 (pembulatan) sampai saya menekan angka genap. Lalu saya hanya membandingkan hasil dari divisi terakhir dengan keduanya dengan kekuatan berapa kali saya dibagi.
Penjelasan:
sumber
Maple, 100 byte (termasuk spasi)
Ditempatkan dengan baik untuk dibaca:
Ide yang sama seperti beberapa yang lain; bagilah X dengan 2 hingga X tidak lagi dapat habis dibagi 2, lalu periksa kriteria 2 ^ n> x.
sumber
Java 1.7,
4943 byteLain 6 byte debu berkat @charlie.
Cobalah! (ideone)
Dua cara, sama panjangnya. Seperti kebanyakan jawaban di sini, kredit diberikan ke @Dennis tentu saja untuk ekspresi.Mengambil akar dari sisi kanan ekspresi:
Menerapkan kekuatan dua ke sisi kiri ekspresi:
Dapat memangkas satu byte jika nilai numerik positif dibolehkan mewakili 'kebenaran', dan nilai negatif 'palsu':
Sayangnya karena 'Konversi Sempit Primitif' orang tidak bisa begitu saja menulis ini di Jawa dan mendapatkan hasil yang benar:
Dan setiap upaya untuk memperluas 'p' akan menyebabkan kesalahan kompilasi karena operator bitwise tidak didukung pada yaitu mengapung atau menggandakan :(sumber
boolean f(int p){return Math.sqrt(p--)<(p&-p);}
boolean g(int p){return p--<(p&-p)*(p&-p);}
Math.*
panggilan; tidak tahu bagaimana caranya! Terima kasih!Hy , 37 byte
Cobalah online!
Port of @Dennis 'menjawab.
sumber
C (gcc) , 29
30byteCobalah online!
sumber
Japt ,
12109 byteCobalah online!
Port of Dennis 'Jelly menjawab lagi. - 1 terima kasih kepada @Shaggy.
sumber
-1
bisaÉ
.Cjam, 11 byte
Seperti kebanyakan dari kita, mendukung solusi hebat Dennis:
Cobalah online
sumber
C (137 byte)
Hanya datang untuk membaca jawaban setelah saya mencobanya.
Mempertimbangkan
N=k*2^n+1
kondisik<2^n
(k=1,3,5..
dann=1,2,3..
Dengan
n=1
kami memiliki satuk
tersedia untuk diuji. Saat kami bertambah,n
kami mendapat beberapak's
tes lagi seperti:n = 1; k = 1
n = 2; k = 1 k = 3
n = 3; k = 1 k = 3 k = 5 k = 7
...
Iterasi melalui kemungkinan tersebut kita bisa yakin N bukan nomor Prouth jika untuk diberikan
n
padak=1
nomor yang diperoleh lebih besar dari N dan tidak ada iterasi lainnya adalah pertandingan.Jadi kode saya pada dasarnya "brute-forces" jalannya untuk menemukan N.
Setelah membaca jawaban lain dan menyadari Anda dapat memfaktorkan N-1 dengan 2 untuk menemukan
n
dan kemudian membuat syaratk<2^n
, saya pikir kode saya bisa lebih kecil dan lebih efisien menggunakan metode ini.Itu patut dicoba!
Diuji semua angka yang diberikan dan beberapa angka "tidak benar". Fungsi mengembalikan 1 jika nomor tersebut adalah nomor Prouth dan 0 jika bukan.
sumber
Javascript ES7, 16 byte
Port jawaban Julia saya, yang merupakan port jawaban @ Dennis's Jelly.
Terima kasih @Charlie selama 2 byte disimpan!
sumber
n=x=>x-1&1-x>x**.5; n(3)
memberi saya0
(sebenarnya itu memberi saya 0 terlepas dari input)n=x=>x-1&1-x>Math.pow(x,0.5); n(3)
(x-1&1-x)
tanpa operator operator diutamakan:(x-1)&((1-x)>x**.5)
x=>x--**.5<(x&-x)
orx=>x**.5<(--x&-x)
C # (.NET Core) , 17 byte
Cobalah online!
Pelabuhan MegaTom ini C jawabannya .
Saya mencoba solusi berbasis LINQ, tapi ini terlalu bagus.
sumber
tinta , 60 byte
Cobalah online!
Berdasarkan jawaban @ DSkoog's Maple - itu bukan yang pertama dari jenisnya yang diposting, tapi itu yang pertama dari jenisnya yang saya lihat.
Tidak disatukan
sumber
Kode Mesin x86, 15 byte
Bytes ini mendefinisikan fungsi yang mengambil argumen input (integer yang tidak ditandai) dalam
EDI
register, mengikuti konvensi pemanggilan System V standar untuk sistem x86, dan mengembalikan hasil dalamEAX
register, seperti semua konvensi pemanggilan x86.Dalam mnemonik assembler:
Cobalah online!
Ini adalah solusi yang sangat mudah — dan secara konseptual mirip dengan versi C MegaTom . Bahkan, Anda bisa menulis ini dalam C sebagai sesuatu seperti berikut ini:
tetapi kode mesin di atas lebih baik golf daripada apa yang akan Anda dapatkan dari kompiler C, bahkan ketika itu diatur untuk mengoptimalkan ukuran.
Satu-satunya "cheat" di sini adalah mengembalikan -1 sebagai nilai "true" dan 0 sebagai nilai "falsy". Trik ini memungkinkan penggunaan
SBB
instruksi 2-byte sebagai lawan dariSETB
instruksi 3-byte .sumber