Apakah ini nomor Proth?

37

Sebuah nomor Proth , dinamai François Proth, adalah angka yang dapat dinyatakan sebagai

N = k * 2^n + 1

Di mana kbilangan bulat positif ganjil dan nbilangan 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 > 1puas. 5 Juga merupakan nomor Proth karena dapat ditulis sebagai

(1 * 2^2) + 1

dan 2^2 > 1puas. Namun, 7 bukan nomor Proth karena satu-satunya cara untuk menuliskannya N = k * 2^n + 1adalah

(3 * 2^1) + 1

dan 2^1 > 3tidak 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!

DJMcMayhem
sumber

Jawaban:

41

Jelly , 5 byte

’&C²>

Cobalah online! atau verifikasi semua kasus uji .

Latar Belakang

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.

Bagaimana itu bekerja

’&C²>  Main link. Argument: N

’      Decrement; yield N - 1.
  C    Complement; yield 1 - N.
 &     Take the bitwise AND of both results.
   ²   Square the bitwise AND.
    >  Compare the square to N.
Dennis
sumber
Wow. itu luar biasa
jangan terang
46

Python, 22 byte

lambda N:N-1&1-N>N**.5

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**.5dalam implementasi.

Dennis
sumber
23
Saya sering Math.SE, dan mata saya benar-benar berharap untuk LaTeX yang indah di situs ini daripada terlihat seperti situs 90-an ...
qwr
Yang ini favorit saya.
Qix
9

Python 2, 23 byte

lambda n:(~-n&1-n)**2>n
feersum
sumber
9

Mathematica, 50 48 45 40 38 35 31 29 byte

Mathematica umumnya menyebalkan ketika datang ke kode golf, tetapi kadang-kadang ada built-in yang membuat semuanya terlihat sangat bagus.

1<#<4^IntegerExponent[#-1,2]&

Sebuah tes:

Reap[Do[If[f[i],Sow[i]],{i,1,1000}]][[2,1]]

{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}

Sunting: Sebenarnya, jika saya mencuri ide AND AND Dennis , saya bisa mendapatkannya hingga 23 22 20 byte.

Mathematica, 23 22 20 byte (terima kasih A Simmons )

BitAnd[#-1,1-#]^2>#&
Michael Lee
sumber
2
Selamat Datang di Programming Puzzles dan Code Golf! :)
Adnan
1
Tidak perlu memulainya g=, fungsi murni tidak masalah!
A Simmons
Oh manisnya. Perbaiki sekarang.
Michael Lee
Omong-omong, tes Anda dapat disederhanakan secara signifikan Select[Range@1000,f].
numbermaniac
8

05AB1E , 14 10 byte

Terima kasih kepada Emigna karena telah menghemat 4 byte!

Kode:

<©Ó¬oD®s/›

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:

[2, 2, 2, 2, 3, 5]

Kami membaginya menjadi dua bagian. Dengan menggunakan 2Q·0K, kita mendapatkan daftar dua:

[2, 2, 2, 2]

Dengan ®2K, kita mendapatkan daftar angka yang tersisa:

[3, 5]

Akhirnya, ambil produk keduanya. [2, 2, 2, 2]hasil menjadi 16 . Produk [3, 5]hasil menjadi 15 .

Test case ini benar sejak 16 > 15 .

Adnan
sumber
<©Ó¬oD®s/›atau <DÓ0èoDŠ/›untuk 10.
Emigna
@Emigna Itu jenius! Terima kasih :)
Adnan
7

Brain-Flak , 460 350 270 266 264 188 176 bytes

Cobalah 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

({}[()])      #Subtract one from input
(((<>())))    #Put three ones on the other stack
{
 {}           #Pop the crap off the top
 ([(
  ((({}<(({}){})>){}){}) #Multiply the top by four and the bottom by two
  <>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{} #Check if the power of four is greater than N-1
}
(<{}{}>) #Remove the power of 4
<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>) #Modulo N-1 by the power of two

Program ini bukan tumpukan bersih. Jika Anda menambahkan 4 byte tambahan, Anda dapat membuatnya menjadi bersih:

({}[()])(((<>()))){{}([(((({}<(({}){})>){}){})<>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}}(<{}{}>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>)
Wisaya Gandum
sumber
5

MATL , 9 byte

qtYF1)EW<

Output yang sebenarnya adalah 1. Falsy is 0atau output kosong. (Satu-satunya input yang menghasilkan output kosong adalah 1dan 2; sisanya menghasilkan salah satu 0atau 1).

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.

q    % Input x implicitly. Subtract 1
t    % Duplicate
YF   % Exponents of prime factorization of x-1
1)   % First entry: exponent of 2. Errors for x equal to 1 or 2
E    % Duplicate
W    % 2 raised to that. This is y squared
<    % Is x-1 less than y squared? Implicitly display
Luis Mendo
sumber
5

Brachylog , 28 byte

>N>0,2:N^P:K*+?,P>K:2%1,N:K=

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:

>N>0,2:N^P:K*+?,P>K:2%1,N:K=

>N>0                           input > N > 0
     2:N^P                     2^N = P
         P:K*+?                P*K+1 = input
                P>K            P > K
                  K:2%1        K%2 = 1
                        N:K=   [N:K] has a solution
Biarawati Bocor
sumber
5

Haskell, 55 46 byte

f x=length [x|k<-[1,3..x],n<-[1..x],k*2^n+1==x,2^n>k]>0

Sunting: Berkat nimi, sekarang 46 byte

f x=or[k*2^n+1==x|k<-[1,3..x],n<-[1..x],2^n>k]
X88B88
sumber
4
Selamat Datang di Programming Puzzles & Code Golf!
Dennis
Terima kasih sobat! Sudah lama bersembunyi di sini. Big fan btw, jelly sangat keren. Seandainya saya bisa belajar tetapi sayangnya, saya tidak benar-benar mengerti
X88B88
2
Kiat umum: jika Anda hanya tertarik pada panjang daftar yang dibuat oleh pemahaman, Anda dapat menggunakannya sum[1| ... ]. Di sini kita bisa pergi lebih jauh dan bergerak tes kesetaraan di depan |dan memeriksa dengan orjika salah satu dari mereka adalah benar: f x=or[k*2^n+1==x|k<-...,n<-...,2^n>k].
nimi
Wow. Kiat bagus. Saya pasti akan merevisinya.
X88B88
2
Jika Anda tertarik mempelajari Jelly, lihat wiki atau bergabunglah dengan ruang Jelly .
Dennis
5

ECMAScript Regex, 48 43 41 byte

Regex 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 lebih sedikit 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.

^x(?=(x(xx)*)\1*$)((\1x*)(?=\1\4*$)x)\3*$

Cobalah online!


 # Match Proth numbers in the domain ^x*$
 ^
 x                         # tail = tail - 1
 (?=(x(xx)*)\1*$)          # \1 = largest odd factor of tail
 
 # Calculate tail / \1, but require that the quotient, \3, be > \1
 # (and the quotient is implicitly a power of 2, because the divisor
 # is the largest odd factor).
 (                         # \3 = tail / \1, asserting that \3 > \1
     (\1x*)                # \4 = \3-1
     (?=\1\4*$)            # We can skip the test for divisibility by \1-1
                           # (and avoid capturing it) because we've already
                           # asserted that the quotient is larger than the
                           # divisor.
     x
 )
 \3*$
 

Kode mati
sumber
1
O_o wow, hanya 48 byte
ASCII
Neil's lebih mirip dengan milikku daripada dengan Dennis '
H.PWiz
4

Julia, 16 byte

!x=~-x&-~-x>x^.5

Kredit ke @Dennis untuk jawabannya dan beberapa kiat bermain golf!

Mama Fun Roll
sumber
Itu tidak berhasil. Di Julia, &memiliki prioritas yang sama dengan *.
Dennis
1
Oh benar Tetap: PI harus benar-benar menguji kode saya.
Mama Fun Roll
2
Anda bisa menggunakan -~-xbukan (1-x). Juga ada√x bukan x^.5, tetapi tidak menyimpan byte.
Dennis
4

R, 52 50 byte

x=scan()-1;n=0;while(!x%%2){x=x/2;n=n+1};2^(2*n)>x

Program dimulai dengan membagi N-1(disebut di sini Pdanx ) 2selama mungkin untuk menemukan 2^nbagian dari persamaan, meninggalkan k=(N-1)/2^n, dan kemudian menghitung apakah atau tidak klebih rendah daripada 2^n, menggunakan fakta bahwa2^n>x/2^n <=> (2^n)²>x <=> 2^2n>x

Frédéric
sumber
1
Anda dapat menarik P=di awal, dan mengubah ujung ke 2^n>xdan menyimpan seperti 5 atau 6 byte
user5957401
4

Regex (ECMAScript), 40 38 byte

-2 byte berkat Deadcode

^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$)

Cobalah online!

Versi yang dikomentari:

# Subtract 1 from the input N
^x

# Assert N is even.
# Capture \1 = biggest power of 2 that divides N.
# Capture \2 = 2.
(?=((xx)+?)(\1\1)*$)

# Assert no odd number > \1 divides N
(?!(\1x\2*)\4*$)
Grimmy
sumber
Wow, ini sangat keren. Begitu banyak cara untuk mengatasi masalah ini!
Deadcode
1
38 byte: ^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$)( Coba online )
Deadcode
2

J, 10 byte

%:<<:AND-.

Berdasarkan solusi bitwise @Dennis .

Mengambil input ndan mengembalikan 1 jika itu adalah nomor Proth lain 0.

Pemakaian

   f =: %:<<:AND-.
   f 16
0
   f 17
1
   (#~f"0) >: i. 100  NB. Filter the numbers [1, 100]
3 5 9 13 17 25 33 41 49 57 65 81 97

Penjelasan

%:<<:AND-.  Input: n
        -.  Complement. Compute 1-n
   <:       Decrement. Compute n-1
     AND    Bitwise-and between 1-n and n-1
%:          Square root of n
  <         Compare sqrt(n) < ((1-n) & (n-1))
mil
sumber
Hah. Saya tidak tahu AND. keren!
Conor O'Brien
2

Retina 0.8.2 , 47 byte

\d+
$*
+`(1+)\1
$+0
01
1
+`.10(0*1)$
1$1
^10*1$

k·2n+1(2k±1)·2n+1+1k=1

\d+
$*

Konversikan ke unary.

+`(1+)\1
$+0
01
1

Konversi ke biner.

+`.10(0*1)$
1$1

Jalankan formula generasi Proth berulang kali secara terbalik.

^10*1$

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:

^.(?=(.+?)(\1\1)*$)(?=((.*)\4.)\3*$).*(?!\1)\3$
Neil
sumber
2

ECMAScript Regex, 42 byte

^x(?=(x(xx)*)\1*$)(?=(x+?)((\3\3)*$))\4\1x

Cobalah online! (Menggunakan Retina)

Saya pada dasarnya kurangi 1, bagi dengan jumlah ganjil terbesar yang mungkin k, kemudian periksa bahwa setidaknya k+1tersisa.

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

H.Piz
sumber
Wow, ini luar biasa! Dilakukan dengan sangat baik. Perhatikan bahwa Anda dapat membuatnya sedikit lebih cepat dengan mengubah (\3\3)*)$ke(\3\3)*$)
Deadcode
Kerja bagus dengan kode Retina itu. Saya tidak tahu tentang $=dan $.=. Ini dapat ditingkatkan lebih baik lagi .
Deadcode
2
@Deadcode Jika Anda ingin memperbaiki header dan footer, maka lakukan beberapa perbaikan lebih lanjut .
Neil
@ Neil Itu terlihat seperti golf yang bagus, tapi sayangnya sepertinya ada bug. Coba nomor tunggal . Mereka tidak bekerja.
Deadcode
1
@Deadcode Maaf, saya tidak menyadari bahwa nomor tunggal adalah bagian dari "spec".
Neil
2

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:

({
  # (n+1)/2 to the other stack, n mod 2 to this stack
  <{({}[()]<(([{}]())<>{})<>>)}{}>
  # if 1 (n was odd) jump to the other stack and count the one
  {{}(<>)}{}
#end and push the sum -1, with a one under it
}<>[(())])
#use the one to get a power of two
{([()]{}<(({}){})>)}{}
#compare the power of two with the remainder after all the divisions
([({}[{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}
MegaTom
sumber
1

Maple, 100 byte (termasuk spasi)

IsProth:=proc(X)local n:=0;local x:=X-1;while x mod 2<>1 do x:=x/2;n:=n+1;end do;is(2^n>x);end proc:

Ditempatkan dengan baik untuk dibaca:

IsProth := proc( X )
    local n := 0;
    local x := X - 1;
    while x mod 2 <> 1 do
        x := x / 2;
        n := n + 1;
    end do;
    is( 2^n > x );
end proc:

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.

DSkoog
sumber
1

Java 1.7, 49 43 byte

Lain 6 byte debu berkat @charlie.

boolean g(int p){return p--<(p&-p)*(p&-p);}

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:

boolean f(int p){return(p-1&(1-p))>Math.sqrt(p);}

Menerapkan kekuatan dua ke sisi kiri ekspresi:

boolean g(int p){return Math.pow(p-1&(1-p),2)>p;}

Dapat memangkas satu byte jika nilai numerik positif dibolehkan mewakili 'kebenaran', dan nilai negatif 'palsu':

double g(int p){return Math.pow(p-1&(1-p),2)-p;}

Sayangnya karena 'Konversi Sempit Primitif' orang tidak bisa begitu saja menulis ini di Jawa dan mendapatkan hasil yang benar:

((p - 1 & (1 - p))^2) > p;

Dan setiap upaya untuk memperluas 'p' akan menyebabkan kesalahan kompilasi karena operator bitwise tidak didukung pada yaitu mengapung atau menggandakan :(

MH.
sumber
1
f = 47:boolean f(int p){return Math.sqrt(p--)<(p&-p);}
charlie
1
g = 43:boolean g(int p){return p--<(p&-p)*(p&-p);}
charlie
Yang bagus! Saya tahu harus ada cara untuk menyingkirkan Math.*panggilan; tidak tahu bagaimana caranya! Terima kasih!
MH.
1

Hy , 37 byte

(defn f[n](>(**(&(- n 1)(- 1 n))2)n))

Cobalah online!

Port of @Dennis 'menjawab.

adl
sumber
1

Japt , 12 10 9 byte

É&1-U)>Uq

Cobalah online!

Port of Dennis 'Jelly menjawab lagi. - 1 terima kasih kepada @Shaggy.

randomdude999
sumber
-1bisa É.
Shaggy
0

Cjam, 11 byte

Seperti kebanyakan dari kita, mendukung solusi hebat Dennis:

qi_(_W*&2#<

Cobalah online

A Simmons
sumber
0

C (137 byte)

int P(int N){int x=1,n=0,k=1,e=1,P=0;for(;e;n++){for(x=1,k=1;x&&x<N;k+=2){x=2<<n;x=x>k?x*k+1:0;if(x>N&&k==1)e=0;}if(x==N)P=1;}return P;}

Hanya datang untuk membaca jawaban setelah saya mencobanya.

Mempertimbangkan N=k*2^n+1kondisi k<2^n( k=1,3,5..dann=1,2,3..

Dengan n=1kami memiliki satu ktersedia untuk diuji. Saat kami bertambah, nkami mendapat beberapa k'stes 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 npada k=1nomor 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 ndan kemudian membuat syarat k<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.

IanC
sumber
0

Javascript ES7, 16 byte

x=>x--<(-x&x)**2

Port jawaban Julia saya, yang merupakan port jawaban @ Dennis's Jelly.

Terima kasih @Charlie selama 2 byte disimpan!

Mama Fun Roll
sumber
n=x=>x-1&1-x>x**.5; n(3)memberi saya 0(sebenarnya itu memberi saya 0 terlepas dari input)
eithed
Browser apa? Mungkin hanya itu.
Mama Fun Roll
Chrome 52. Firefox 48 memberikan jawaban yang sama untukn=x=>x-1&1-x>Math.pow(x,0.5); n(3)
eithed
Oke - ini yang diutamakan operator. Pasti (x-1&1-x)tanpa operator operator diutamakan:(x-1)&((1-x)>x**.5)
eithed
1
-1 byte: x=>x--**.5<(x&-x)orx=>x**.5<(--x&-x)
charlie
0

tinta , 60 byte

=p(n)
~n-=n>1
~temp x=1
-(k){n%2:{n<x}->->}
~x+=x
~n=n/2
->k

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

= is_proth(number) =

/* It's easy to check if a number is one less than a Proth number.
   We take the number and divide it by 2 until we can't.
   Once we can't, we've found the smallest possible "k".
   If we also keep track of how many times we divided, we have our corresponding "2^n"
   All we have to do then is compare those
*/

~ number -= (number > 1)            // So, we first subtract one. Except this implementation won't ever halt for 0, so we don't subtract if the input is 1 (this is fine since the desired outputs for inputs 1 and 2 are the same)
~ temp power_of_two = 1             // We declare a variable to store our "2^n"
- (check)
  {
  - number % 2:                     // Once we can't divide by 2 anymore, we've found the smallest possible "k"
    {number < power_of_two}         // At that point, we print whether it's smaller than the "2^n" we found
    ->->                            // And then we return to where we were called from
  }

  ~ number = number / 2             // We keep dividing by 2 until we can't.
  ~ power_of_two += power_of_two    // and update our "2^n" as we go
-> check
Sara J
sumber
0

Kode Mesin x86, 15 byte

4F 89 F8 F7 D8 21 F8 0F AF C0 39 C7 19 C0 C3

Bytes ini mendefinisikan fungsi yang mengambil argumen input (integer yang tidak ditandai) dalam EDIregister, mengikuti konvensi pemanggilan System V standar untuk sistem x86, dan mengembalikan hasil dalam EAXregister, seperti semua konvensi pemanggilan x86.

Dalam mnemonik assembler:

4F          dec   edi            ; input -= 1
89 F8       mov   eax, edi       ; \ temp
F7 D8       neg   eax            ; |      =
21 F8       and   eax, edi       ; /        (input & -input)
0F AF C0    imul  eax, eax       ; temp *= temp
39 C7       cmp   edi, eax       ; set CF if (input < temp)
19 C0       sbb   eax, eax       ; EAX = -CF
C3          ret                  ; return with result in EAX
                                 ;  (-1 for Proth number; 0 otherwise)

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:

unsigned IsProthNumber(unsigned input)
{
    --input;
    unsigned temp  = (input & -input);
    temp          *= temp;
    return (input < temp) ? -1 : 0;
}

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 SBBinstruksi 2-byte sebagai lawan dari SETBinstruksi 3-byte .

Cody Grey
sumber