Eine Cullen-Zahl ist eine beliebige Zahl, die in der mit folgender Formel erzeugten Sequenz enthalten ist:

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

Deine Aufgabe:

Schreiben Sie ein Programm oder eine Funktion, die eine Eingabe empfängt und einen Wahrheits- / Falschwert ausgibt, basierend darauf, ob die Eingabe eine Cullen-Zahl ist.

Eingang:

Eine nicht negative ganze Zahl zwischen 0 und 10 ^ 9 (einschließlich).

Ausgabe:

Ein wahrer / falscher Wert, der angibt, ob die Eingabe eine Cullen-Zahl ist.

Testfälle:

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

Wertung:

Das ist Code-Golf , also gewinnt die niedrigste Punktzahl in Bytes.

Pyth, 6 5 Bytes

/mh.<

versuche es online

x86_64-Maschinencode ( System V ABI ), 28 27 Byte

-1 Byte danke an @Cody Gray, danke!

Ein Algorithmus mit konstanter Zeit!

_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

Erläuterung:

Sei y eine ganze Zahl und x=y*2^y + 1. Protokolle nehmen, haben wir y + log2(y) = log2(x-1)also y=log2(x-1)-log2(y). Wenn wir den Wert von y zurücksetzen, erhalten wir y=log2(x-1)-log2(log2(x-1)-log2(y)). Dadurch noch einmal, so erhalten wir: y=log2(x-1)-log2[log2(x-1)-log2(log2(x-1)-log2(log2(x-1)-log2(y)))].

Entfernen wir die letzten Begriffe (in der Größenordnung von log2(log2(log2(log2(x)))), das sollte sicher sein!) Und gehen x-1≈xwir davon aus, dass wir erhalten: y≈log2(x)-log2[log2(x)-log2(log2(x))]

Nun f(n) = floor(log2(n))kann manuell überprüft werden, ob ygenau abgerufen werden kann durch: y=f(x)-f[f(x)-f(f(x))]für y <26 und somit x x 10 ^ 9 , wie durch die Abfrage ^{(1) angegeben} .

Der Algorithmus besteht dann einfach darin, y mit gegebenem x zu berechnen und zu überprüfen, ob x == y * 2 ^ y + 1 ist . Der Trick ist, dass f(n)einfach als bsrBefehl (Bit-Scan-Reverse) implementiert werden kann , der den Index des ersten 1-Bit in n und y*2^yas zurückgibt y << y.

Ausführlicher Code:

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

⁽¹⁾ Tatsächlich scheint diese Gleichheit für Werte von y bis 50000 zu gelten.

Gelee , 7 6 Bytes

Ḷæ«`i’

Probieren Sie es online!

Übernimmt die Eingabe als Befehlszeilenargument. Wenn eine Cullen-Zahl C ( n ) angegeben wird, wird n +1 ausgegeben (was in Jelly wahr ist, da es sich um eine Ganzzahl ungleich Null handelt. Beachten Sie, dass n ≥ 0 ist, da die Eingabe eine Ganzzahl ist und Cullen-Zahlen mit negativem n niemals Ganzzahlen sind.) . Wenn eine Nicht-Cullen-Zahl angegeben wird, wird 0 zurückgegeben, was in Jelly falsch ist.

Erläuterung

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

Bilden Sie im Grunde genommen ein Array von Cullen-Zahlen minus eins und suchen Sie dann darin nach der Eingabe minus eins. Wenn die Eingabe eine Cullen-Zahl ist, werden wir sie finden, andernfalls nicht. Beachten Sie, dass das Array unbedingt lang genug ist, um den Eingang zu erreichen, da C ( n ) immer größer als n ist .

JavaScript (ES6), 37-35 Byte

2 Bytes gespart dank 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 Bytes

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

Probieren Sie es online!

Ohm , 8 Bytes

@Dº*≥Dlε

Probieren Sie es 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 Bytes

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

Probieren Sie es online!

05AB1E , 7 Bytes

ÝDo*¹<å

Probieren Sie es online!

Erläuterung:

Ý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)))

Anonyme Funktion. Überprüft, ob xin der Folge C (n) für n in [0, x] generiert wird.

3 Bytes Golf von Giuseppe.

Probieren Sie es online!

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

Aufgrund der Ähnlichkeiten zwischen all diesen Sprachen funktioniert dieser Code für jede Sprache

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

Python, 40 Bytes

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

Probieren Sie es online!

Python 2 , 36 Bytes

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

Probieren Sie es online!

Ausgaben durch Nichtabstürzen / Abstürzen, wie derzeit durch diese Metakonzession zulässig .

Python 2 , 42 Bytes

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

Probieren Sie es online!

Ausgänge über Exit-Code

R , 26 Bytes

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

Probieren Sie es online!

Ein etwas anderer Ansatz als die andere R-Antwort ; liest aus stdinund da der Eingang garantiert zwischen 0 und 10 ^ 9 liegt, müssen wir nur nzwischen 0 und 26 prüfen .

APL (Dyalog) , 9 Bytes

Um den Fall von n = 1 abzudecken , benötigt es⎕IO←0 was auf vielen Systemen Standard ist.

⊢∊1+⍳×2*⍳

Probieren Sie es online!

⊢ [ist] n (das Argument)

∊ ein Mitglied von

1 eins

+ Plus

⍳ die i ntegers 0 ... ( n - 1)

× mal

2 zwei

* hoch

⍳ die i ntegers 0 ... ( n - 1)

Python 2 , 32 Bytes

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

Probieren Sie es online!

Erstellt eine Liste mit Cullen-Zahlen bis zu 10^9und zählt dann, wie oft die Eingabe darin erscheint. Vielen Dank an Vincent für den Hinweis, n<<n|1anstatt (n<<n)+12 Bytes zu sparen.

D, 65 Bytes

Dies ist ein Port von @ HatsuPointerKuns Algorithmus zu D (das Original war bereits D-Code, aber dies ist mit D-spezifischen Tricks)

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

Wie? (D spezifische Tricks)

Das Vorlagensystem von D ist kürzer als das von C ++ und kann auf Typen schließen. Außerdem initialisiert D seine Variablen bei der Deklaration auf den Standardwert.

Mathematica, 30 Bytes

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

Reine Funktion, die eine nichtnegative Ganzzahl als Eingabe verwendet und Trueoder zurückgibt False. Wenn die Eingabe n, so (r=Range@#-1)setzt die Variable rzu sein {0, 1, ..., n-1}, und dann r2^r+1berechnet vektoriell die ersten nZahlen Cullen. MemberQ[...,#]prüft dann, ob nes sich um ein Element der Liste handelt.

Mathematica, 32 Bytes

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

Excel VBA, 45 Bytes

Anonyme VBE- [A1]Direktfensterfunktion, die Eingaben von Zellen und Ausgängen in das VBE-Direktfenster übernimmt

Muss in einem sauberen Modul ausgeführt werden oder Werte für i, j müssen zwischen den Durchläufen auf den Standardwert 0 zurückgesetzt werden

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

Input-Output

I / O wie im VBE-Direktfenster angezeigt

[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 Bytes

f(X)ist erfolgreich, wenn ein Wert I gefunden wird, bei dem X = I * 2 ^ I + 1 ist. Der Range-Hinweis verhindert, dass der Stack-Platz knapp wird, aber er reicht für den Bereich von Cullen-Zahlen bis 10 ^ 9 in der Frage-Spezifikation.

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

z.B

f(838860801).
true

cQuents , 9 Bytes

$0?1+$2^$

Probieren Sie es online!

Erläuterung

$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 Bytes

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

Erläuterung

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 Bytes

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

Erläuterung

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

Probieren Sie es online aus. Wahrheit ist ein Array mit einer Zahl: ,3oder so ,0weiter. Falsey ist ein leeres Array: ()oder !0abhängig von Ihrem Interpreter.

Java (OpenJDK 8) , 56 Byte

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

Probieren Sie es online!

Pari / GP , 25 Bytes

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

Probieren Sie es online!