Nomor Cullen adalah angka apa pun yang terkandung dalam urutan yang dihasilkan menggunakan rumus:

C (n) = (n * 2 ^ n) +1.

Tugas Anda:

Tulis program atau fungsi yang menerima input dan mengeluarkan nilai kebenaran / kepalsuan berdasarkan apakah input tersebut adalah Nomor Cullen.

Memasukkan:

Integer non-negatif antara 0 dan 10 ^ 9 (inklusif).

Keluaran:

Nilai kebenaran / kepalsuan yang menunjukkan apakah input adalah Nomor Cullen.

Kasus uji:

Input:    Output:
1   --->  truthy
3   --->  truthy
5   --->  falsy
9   --->  truthy
12  --->  falsy
25  --->  truthy

Mencetak:

Ini adalah kode-golf , sehingga skor terendah dalam byte menang.

Pyth, 6 5 byte

/mh.<

coba online

kode mesin x86_64 ( System V ABI ), 28 27 byte

-1 byte terima kasih kepada @Cody Grey, terima kasih!

Algoritma waktu-konstan!

_cullen:
   0:   0f bd cf    bsrl    %edi, %ecx
   3:   0f bd c1    bsrl    %ecx, %eax
   6:   89 ca       movl    %ecx, %edx
   8:   29 c2       subl    %eax, %edx
   a:   0f bd c2    bsrl    %edx, %eax
   d:   29 c1       subl    %eax, %ecx
   f:   d3 e1       shll    %cl, %ecx
  11:   ff c1       incl    %ecx
  13:   31 c0       xorl    %eax, %eax
  15:   39 f9       cmpl    %edi, %ecx
  17:   0f 94 c0    sete    %al
  1a:   c3          retq

Penjelasan:

Biarkan y bilangan bulat dan x=y*2^y + 1. Mengambil log, kita memiliki y + log2(y) = log2(x-1), sehinggay=log2(x-1)-log2(y) . Memasukkan kembali nilai y, kita dapatkan y=log2(x-1)-log2(log2(x-1)-log2(y)). Melakukan satu kali ini lebih, kita memperoleh: y=log2(x-1)-log2[log2(x-1)-log2(log2(x-1)-log2(log2(x-1)-log2(y)))].

Mari kita hapus syarat terakhir (dari urutan log2(log2(log2(log2(x)))) , ini harus aman!), Dan berasumsi bahwa x-1≈x, kita memperoleh: y≈log2(x)-log2[log2(x)-log2(log2(x))]

Sekarang, membiarkan f(n) = floor(log2(n)), itu dapat diverifikasi secara manual yang ydapat diambil dengan tepat oleh:, y=f(x)-f[f(x)-f(f(x))]untuk y <26 , dan dengan demikian x ⩽ 10 ^ 9 , sebagaimana ditentukan oleh tantangan ⁽¹⁾ .

Algoritma kemudian hanya terdiri dari komputasi y diberikan x , dan verifikasi bahwa x == y * 2 ^ y + 1 . Kuncinya adalah bahwa f(n)hanya dapat diimplementasikan sebagai bsrinstruksi (bit-scan mundur), yang mengembalikan indeks 1-bit pertama dalam n , dany*2^y sebagaiy << y .

Kode terperinci:

_cullen:                                 ; int cullen(int x) {
   0:   0f bd cf    bsrl    %edi, %ecx   ;  int fx = f(x);
   3:   0f bd c1    bsrl    %ecx, %eax   ;  int ffx = f(f(x));
   6:   89 ca       movl    %ecx, %edx   
   8:   29 c2       subl    %eax, %edx   ;  int a = fx - ffx;
   a:   0f bd c2    bsrl    %edx, %eax   ;  int ffxffx = f(a);
   d:   29 c1       subl    %eax, %ecx   ;  int y = fx - ffxffx;
   f:   d3 e1       shll    %cl, %ecx    ;  int x_ = y<<y;
  11:   ff c1       incl    %ecx         ;  x_++;
  13:   31 c0       xorl    %eax, %eax
  15:   39 f9       cmpl    %edi, %ecx
  17:   0f 94 c0    sete    %al
  1a:   c3          retq                 ;  return (x_ == x);
                                         ; }

⁽¹⁾ Bahkan, kesetaraan ini tampaknya berlaku untuk nilai y hingga 50.000.

Jelly , 7 6 byte

Ḷæ«`i’

Cobalah online!

Mengambil input sebagai argumen baris perintah. Jika diberi nomor Cullen C ( n ), output n +1 (yang benar dalam Jelly, menjadi bilangan nol, perhatikan bahwa kita memiliki n ≥0 karena inputnya bilangan bulat, dan angka Cullen dengan negatif n tidak pernah bilangan bulat) . Jika diberi nomor non-Cullen, mengembalikan 0, yang merupakan falsey di Jelly.

Penjelasan

Ḷæ«`i’
Ḷ        Form a range from 0 to (the input minus 1)
 æ«      Left-shift each element in the range by 
   `       itself
    i’   Look for (the input minus 1) in the resulting array

Pada dasarnya, bentuk array angka Cullen minus satu, lalu cari input minus satu di dalamnya. Jika input adalah nomor Cullen, kami akan menemukannya, jika tidak kami tidak akan. Perhatikan bahwa array cukup panjang untuk mencapai input, karena C ( n ) selalu lebih besar dari n .

JavaScript (ES6), 37 35 byte

Disimpan 2 byte berkat Neil

f=(n,k,x=k<<k^1)=>x<n?f(n,-~k):x==n

Demo

f=(n,k,x=k<<k^1)=>x<n?f(n,-~k):x==n

console.log(JSON.stringify([...Array(1000).keys()].filter(n => f(n))))

Haskell, 28 byte

f n=or[x*2^x+1==n|x<-[0..n]]

Cobalah online!

Ohm , 8 byte

@Dº*≥Dlε

Cobalah online!

           Implicit input
@          Range [1,...,Input]
 D         Duplicate
  º        2^n each element
   *       Multiply those two array
    ≥      Increment everything (now I have an array of all Cullen Numbers)
     Dl    Push array length (= get input again, can't get again implicitly or using a function because it would be a string so I'd waste a byte again)
       ε   Is input in array?

PHP , 43 byte

for(;$argn>$c=1+2**$n*$n++;);echo$argn==$c;

Cobalah online!

05AB1E , 7 byte

ÝDo*¹<å

Cobalah online!

Penjelasan:

ÝDo*¹<å Example input: 9. Stack: [9]
Ý       Range 0-input. Stack: [[0,1,2,3,4,5,6,7,8,9]]
 D      Duplicate. Stack: [[0,1,2,3,4,5,6,7,8,9],[0,1,2,3,4,5,6,7,8,9]]
  o     2** each item in the list. Stack: [[0,1,2,3,4,5,6,7,8,9], [1,2,4,8,16,32,64,128,256,512]]
   *    Multiply the two lists. Stack: [[0, 2, 8, 24, 64, 160, 384, 896, 2048, 4608]]
    ¹   Push input again. Stack: [[0, 2, 8, 24, 64, 160, 384, 896, 2048, 4608],9]
     <  Decrement. Stack: [[0, 2, 8, 24, 64, 160, 384, 896, 2048, 4608],8]
      å Is the first item of the stack in the second item? Stack: [1]
        Implicit print.

R , 53 51 46 byte

pryr::f(x%in%lapply(0:x,function(y)(y*2^y+1)))

Fungsi anonim. Cek apakahx dihasilkan dalam urutan C (n) untuk n dalam [0, x].

3 byte golf oleh Giuseppe.

Cobalah online!

C, C ++, Java, C #, D: 70 byte

Karena kesamaan antara semua bahasa ini, kode ini berfungsi untuk masing-masing

int c(int n){for(int i=0;i<30;++i)if((1<<i)*i+1==n)return 1;return 0;}

Python, 40 byte

lambda n:any(x<<x==n-1for x in range(n))

Cobalah online!

Python 2 , 36 byte

f=lambda n,i=0:i<<i!=n-1and f(n,i+1)

Cobalah online!

Output dengan tidak menabrak / menabrak, seperti yang saat ini diizinkan oleh konsensus meta ini .

Python 2 , 42 byte

i=0
n=input()-1
while i<<i<n:i+=1
i<<i>n<c

Cobalah online!

Keluaran melalui kode keluar

R , 26 byte

a=0:26;scan()%in%(1+a*2^a)

Cobalah online!

Pendekatan yang sedikit berbeda dari jawaban R lainnya ; membaca dari stdindan karena input dijamin antara 0 dan 10 ^ 9, kita hanya perlu memeriksa nantara 0 dan 26.

APL (Dyalog) , 9 byte

Untuk menutupi kasus n = 1, diperlukan ⎕IO←0yang default pada banyak sistem.

⊢∊1+⍳×2*⍳

Cobalah online!

⊢ adalah n (argumen)

∊ anggota dari

1 satu

+ plus

⍳ yang saya ntegers 0 ... ( n -1)

× waktu

2 dua

* untuk kekuatan

⍳ yang saya ntegers 0 ... ( n -1)

Python 2 , 32 byte

[n<<n|1for n in range(26)].count

Cobalah online!

Buat daftar nomor Cullen hingga 10^9, lalu hitung berapa kali input muncul di dalamnya. Terima kasih kepada Vincent karena menunjukkan n<<n|1alih-alih (n<<n)+1, menghemat 2 byte.

D, 65 byte

Ini adalah port algoritme @ HatsuPointerKun ke D (kode aslinya sudah D, tapi ini dengan trik khusus-D)

T c(T)(T n){for(T i;i<30;++i)if((1<<i)*i+1==n)return 1;return 0;}

Bagaimana? (Trik spesifik D)

Sistem template D lebih pendek dari C ++, dan dapat menyimpulkan tipe. Dan D juga menginisialisasi variabel-variabelnya ke default setelah deklarasi.

Mathematica, 30 byte

MemberQ[(r=Range@#-1)2^r+1,#]&

Fungsi murni mengambil integer non negatif sebagai input dan return Trueatau False. Jika inputnya adalah n, maka (r=Range@#-1)tetapkan variabel yang rakan {0, 1, ..., n-1}, dan kemudian secara r2^r+1hitung menghitung nangka Cullen pertama . MemberQ[...,#]kemudian periksa apakah nmerupakan elemen dari daftar.

Mathematica, 32 byte

!Table[x*2^x+1,{x,0,#}]~FreeQ~#&

Excel VBA, 45 Bytes

Fungsi jendela langsung VBE anonim yang mengambil input dari sel [A1]dan ouput ke jendela langsung VBE

Harus dijalankan dalam modul bersih atau memiliki nilai untuk i, j disetel ulang ke nilai default 0 di antara proses

While j<[A1]:j=(i*2 ^ i)+1:i=i+1:Wend:?j=[A1]

Input output

I / O seperti yang terlihat di jendela langsung VBE

[A1]=25
While j<[A1]:j=(i*2 ^ i)+1:i=i+1:Wend:?j=[A1]
True

[A1]=1: i=0:j=0 ''# clearing module values
While j<[A1]:j=(i*2 ^ i)+1:i=i+1:Wend:?j=[A1]
True    

[A1]=5: i=0:j=0 ''# clearing module values
While j<[A1]:j=(i*2 ^ i)+1:i=i+1:Wend:?j=[A1]
False 

Swi-Prolog, 69 byte

f(X)berhasil jika dapat menemukan nilai I di mana X = I * 2 ^ I + 1. Petunjuk rentang menghentikannya kehabisan ruang tumpukan, tapi itu cukup untuk rentang angka Cullen hingga 10 ^ 9 dalam spesifikasi pertanyaan.

:-use_module(library(clpfd)).
f(X):-I in 0..30,X#=I*2^I+1,label([I]).

misalnya

f(838860801).
true

cQuents , 9 byte

$0?1+$2^$

Cobalah online!

Penjelasan

$0           n is 0-indexed
  ?          Mode query. Given input n, output true/false for if n is in the sequence.
   1+$2^$    Each item in the sequence equals `1+index*2^index`

TI-BASIC, 17 byte

max(Ans=seq(X2^X+1,X,0,25

Penjelasan

seq(X2^X+1,X,0,25 Generate a list of Cullen numbers in the range
Ans=              Compare the input to each element in the list, returning a list of 0 or 1
max(              Take the maximum of the list, which is 1 if any element matched

QBIC , 24 byte

[0,:|~a*(2^a)+1=b|_Xq}?0

Penjelasan

[0,:|           FOR a = 0 to b (input from cmd line)
~a*(2^a)+1=b    IF calculating this a results in b
|_Xq            THEN quit, printing 1
}               NEXT a
?0              We haven't quit early, so print 0 and end.

k, 19 bytes

{&1=x-{x**/x#2}'!x}

Try it online. Truthy is an array with a number in it: ,3 or ,0 et cetera. Falsey is an empty array: () or !0 depending on your interpreter.

Java (OpenJDK 8), 56 bytes

i->{int n,c;for(n=0;(c=n*(2<<n++-1)+1)<i;);return c==i;}

Try it online!

Pari/GP, 25 bytes

n->!prod(i=0,n,n-i*2^i-1)

Try it online!