Liczba Cullen to dowolna liczba zawarta w sekwencji wygenerowanej za pomocą wzoru:

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

Twoje zadanie:

Napisz program lub funkcję, która odbiera dane wejściowe i wyświetla wartość prawda / fałsz na podstawie tego, czy dane wejściowe są liczbą Cullen.

Wkład:

Nieujemna liczba całkowita od 0 do 10 ^ 9 (włącznie).

Wydajność:

Wartość prawda / fałsz wskazująca, czy dane wejściowe są liczbą Cullen.

Przypadki testowe:

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

Punktacja:

To jest golf golfowy , więc wygrywa najniższy wynik w bajtach.

Pyth, 6 5 bajtów

/mh.<

spróbuj online

Kod maszynowy x86_64 ( System V ABI ), 28 27 bajtów

-1 bajt dzięki @Cody Gray, dzięki!

Algorytm stałego czasu!

_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

Wyjaśnienie:

Niech y jest liczbą całkowitą i x=y*2^y + 1. Mamy y + log2(y) = log2(x-1)więc dzienniki y=log2(x-1)-log2(y). Ponownie podając wartość y, otrzymujemy y=log2(x-1)-log2(log2(x-1)-log2(y)). Robi to jeszcze raz, otrzymujemy: y=log2(x-1)-log2[log2(x-1)-log2(log2(x-1)-log2(log2(x-1)-log2(y)))].

Usuńmy ostatnie warunki (z rzędu log2(log2(log2(log2(x))))powinno to być bezpieczne!) I załóżmy x-1≈x, że otrzymujemy: y≈log2(x)-log2[log2(x)-log2(log2(x))]

Teraz, pozwalając f(n) = floor(log2(n)), można zweryfikować ręcznie, że ymożna je dokładnie pobrać :,y=f(x)-f[f(x)-f(f(x))] dla y <26 , a zatem x ⩽ 10 ^ 9 , jak określono w wyzwaniu ⁽¹⁾ .

Algorytm składa się po prostu z obliczenia y dla x i sprawdzenia, czy x == y * 2 ^ y + 1 . Sztuczka polega na tym, że f(n)można ją po prostu zaimplementować jako bsrinstrukcję (odwrócenie skanowania bitów), która zwraca indeks pierwszego 1-bitu w n , i y*2^yas y << y.

Szczegółowy kod:

_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);
                                         ; }

⁽¹⁾ W rzeczywistości wydaje się, że ta równość obowiązuje dla wartości y do 50000.

Galaretka , 7 6 bajtów

Ḷæ«`i’

Wypróbuj online!

Pobiera dane wejściowe jako argument wiersza polecenia. Jeśli podano liczbę Cullen C ( n ), wyprowadza n +1 (co jest prawdą w Jelly, która jest niezerową liczbą całkowitą; zwróć uwagę, że mamy n ≥0, ponieważ wejście jest liczbą całkowitą, a liczby Cullen z ujemną n nigdy nie są liczbami całkowitymi) . Jeśli podano liczbę inną niż Cullen, zwraca 0, co jest falsey w galaretce.

Wyjaśnienie

Ḷæ«`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

Zasadniczo utwórz tablicę liczb Cullena minus jeden, a następnie poszukaj danych wejściowych minus jeden. Jeśli dane wejściowe to liczba Cullena, znajdziemy je, w przeciwnym razie nie będziemy. Zauważ, że tablica musi być wystarczająco długa, aby dotrzeć do wejścia, ponieważ C ( n ) jest zawsze większe niż n .

JavaScript (ES6), 37 35 bajtów

Zaoszczędzono 2 bajty dzięki Neilowi

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

Próbny

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 bajtów

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

Wypróbuj online!

Ohm , 8 bajtów

@Dº*≥Dlε

Wypróbuj 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 bajty

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

Wypróbuj online!

05AB1E , 7 bajtów

ÝDo*¹<å

Wypróbuj online!

Wyjaśnienie:

Ý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 bajtów

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

Funkcja anonimowa. Sprawdza, czy xjest generowany w sekwencji C (n) dla nw [0, x].

3 bajty grał w golfa Giuseppe.

Wypróbuj online!

C, C ++, Java, C #, D: 70 bajtów

Ze względu na podobieństwa między tymi wszystkimi językami ten kod działa dla każdego z nich

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

Python, 40 bajtów

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

Wypróbuj online!

Python 2 , 36 bajtów

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

Wypróbuj online!

Dane wyjściowe nie ulegają awariom / awariom, jak obecnie zezwala ten meta concensus .

Python 2 , 42 bajty

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

Wypróbuj online!

Dane wyjściowe za pośrednictwem kodu wyjścia

R , 26 bajtów

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

Wypróbuj online!

Nieco inne podejście niż druga odpowiedź R ; odczytuje z, stdina ponieważ gwarantowane jest wejście od 0 do 10 ^ 9, musimy tylko sprawdzić nod 0 do 26.

APL (Dyalog) , 9 bajtów

Aby objąć przypadek n = 1, wymaga ⎕IO←0domyślnej wartości w wielu systemach.

⊢∊1+⍳×2*⍳

Wypróbuj online!

⊢ [is] n (argument)

∊ członek

1 jeden

+ plus

⍳ z I ntegers 0 ... ( n -1)

× czasy

2 dwa

* do potęgi

⍳ z I ntegers 0 ... ( n -1)

Python 2 , 32 bajty

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

Wypróbuj online!

Tworzy listę liczb Cullen do 10^9, a następnie zlicza, ile razy pojawia się na niej dane wejściowe. Dzięki Vincent za wskazanie n<<n|1zamiast (n<<n)+1oszczędzania 2 bajtów.

D, 65 bajtów

Jest to port algorytmu @ HatsuPointerKun do D (oryginał był już kodem D, ale dotyczy to sztuczek specyficznych dla D)

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

W jaki sposób? (D określone triki)

System szablonów D jest krótszy niż C ++ i może wnioskować o typach. Po deklaracji D inicjuje również zmienne do wartości domyślnych.

Mathematica, 30 bajtów

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

Czysta funkcja przyjmująca nieujemną liczbę całkowitą jako dane wejściowe i zwracające Truelub False. Jeśli dane wejściowe są n, to (r=Range@#-1)ustawia zmienną rna {0, 1, ..., n-1}, a następnie r2^r+1oblicza wektorowo pierwsze nliczby Cullen. MemberQ[...,#]następnie sprawdza, czy njest elementem listy.

Mathematica, 32 bajty

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

Excel VBA, 45 bajtów

Anonimowa funkcja bezpośredniego okna VBE, która przenosi dane wejściowe z komórki [A1]i wysyła dane do bezpośredniego okna VBE

Musi być uruchamiany w czystym module lub mieć wartości dla i, j być resetowany do wartości domyślnej 0 między przebiegami

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

Wejście wyjście

I / O jak widać w bezpośrednim oknie 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 bajtów

f(X)powiedzie się, jeśli może znaleźć wartość I, gdzie X = I * 2 ^ I + 1. Wskazówka zakresu powstrzymuje go przed wyczerpaniem miejsca na stosie, ale wystarcza dla zakresu liczb Cullen do 10 ^ 9 w specyfikacji pytania.

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

na przykład

f(838860801).
true

cQuents , 9 bajtów

$0?1+$2^$

Wypróbuj online!

Wyjaśnienie

$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 bajtów

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

Wyjaśnienie

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 bajty

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

Wyjaśnienie

[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 bajtów

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

Wypróbuj online. Prawda jest tablicą z liczbą: ,3lub ,0et cetera. Falsey jest pustą tablicą: ()lub w !0zależności od tłumacza.

Java (OpenJDK 8) , 56 bajtów

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

Wypróbuj online!

Pari / GP , 25 bajtów

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

Wypróbuj online!