Un nombre Cullen est un nombre contenu dans la séquence générée à l'aide de la formule:

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

Ta tâche:

Écrivez un programme ou une fonction qui reçoit une entrée et génère une valeur de vérité / fausse selon que l'entrée est un nombre Cullen.

Contribution:

Un entier non négatif entre 0 et 10 ^ 9 (inclus).

Sortie:

Une valeur de vérité / fausse qui indique si l'entrée est un nombre Cullen.

Cas de test:

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

Notation:

C'est le code-golf , donc le score le plus bas en octets l'emporte.

Pyth, 6 5 octets

/mh.<

essayez-le en ligne

Code machine x86_64 ( System V ABI ), 28 27 octets

-1 octet grâce à @Cody Gray, merci!

Un algorithme à temps constant!

_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

Explication:

Soit y un entier et x=y*2^y + 1. Prenant des journaux, nous avons y + log2(y) = log2(x-1)donc y=log2(x-1)-log2(y). En rebranchant la valeur de y, nous obtenons y=log2(x-1)-log2(log2(x-1)-log2(y)). Faire cela une fois de plus, on obtient: y=log2(x-1)-log2[log2(x-1)-log2(log2(x-1)-log2(log2(x-1)-log2(y)))].

Supprimons les derniers termes (de l'ordre de log2(log2(log2(log2(x)))), cela devrait être sûr!), Et supposons que x-1≈xnous obtenons: y≈log2(x)-log2[log2(x)-log2(log2(x))]

Maintenant, en laissant f(n) = floor(log2(n)), il peut être vérifié manuellement qui ypeut être exactement récupéré par:, y=f(x)-f[f(x)-f(f(x))]pour y <26 , et donc x ⩽ 10 ^ 9 , comme spécifié par le défi ⁽¹⁾ .

L'algorithme consiste alors simplement à calculer y étant donné x , et à vérifier que x == y * 2 ^ y + 1 . L'astuce est qu'elle f(n)peut simplement être implémentée en tant bsrqu'instruction (bit-scan reverse), qui retourne l'index du premier 1 bit en n , et y*2^yas y << y.

Code détaillé:

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

⁽¹⁾ En fait, cette égalité semble se maintenir pour des valeurs de y jusqu'à 50000.

Gelée , 7 6 octets

Ḷæ«`i’

Essayez-le en ligne!

Prend l'entrée comme argument de ligne de commande. Si on donne un nombre Cullen C ( n ), les sorties n +1 (ce qui est vrai dans Jelly, étant un entier non nul; notez que nous avons n ≥0 parce que l'entrée est un entier, et les nombres Cullen avec n négatif ne sont jamais des entiers) . Si on lui donne un nombre non Cullen, renvoie 0, ce qui est falsey dans Jelly.

Explication

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

Fondamentalement, formez un tableau de nombres Cullen moins un, puis recherchez l'entrée moins un dedans. Si l'entrée est un nombre Cullen, nous le trouverons, sinon nous ne le ferons pas. Notez que le tableau est nécessairement suffisamment long pour atteindre l'entrée, car C ( n ) est toujours supérieur à n .

JavaScript (ES6), 37 35 octets

Enregistré 2 octets grâce à Neil

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

Démo

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 octets

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

Essayez-le en ligne!

Ohm , 8 octets

@Dº*≥Dlε

Essayez-le en ligne!

           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 octets

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

Essayez-le en ligne!

05AB1E , 7 octets

ÝDo*¹<å

Essayez-le en ligne!

Explication:

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

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

Fonction anonyme. Vérifie si xest généré dans la séquence C (n) pour n dans [0, x].

3 octets golfés par Giuseppe.

Essayez-le en ligne!

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

En raison des similitudes entre toutes ces langues, ce code fonctionne pour chaque

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

Python, 40 octets

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

Essayez-le en ligne!

Python 2 , 36 octets

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

Essayez-le en ligne!

Sorties en ne plantant pas / plantant, comme actuellement autorisé par ce méta-consensus .

Python 2 , 42 octets

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

Essayez-le en ligne!

Sorties via code de sortie

R , 26 octets

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

Essayez-le en ligne!

Une approche légèrement différente de l' autre réponse R ; lit à partir de stdinet puisque l'entrée est garantie entre 0 et 10 ^ 9, il suffit de vérifier nentre 0 et 26.

APL (Dyalog) , 9 octets

Pour couvrir le cas de n = 1, il nécessite ⎕IO←0ce qui est par défaut sur de nombreux systèmes.

⊢∊1+⍳×2*⍳

Essayez-le en ligne!

⊢ [est] n (l'argument)

∊ un membre de

1 une

+ plus

⍳ les i ntegers 0… ( n -1)

× fois

2 deux

* au pouvoir de

⍳ les i ntegers 0… ( n -1)

Python 2 , 32 octets

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

Essayez-le en ligne!

Crée la liste des nombres Cullen jusqu'à 10^9, puis compte le nombre de fois que l'entrée y apparaît. Merci à Vincent d'avoir souligné au n<<n|1lieu de (n<<n)+1, économisant 2 octets.

D, 65 octets

Il s'agit d'un portage de l'algorithme de @ HatsuPointerKun vers D (l'original était déjà du code D, mais c'est avec des astuces spécifiques à D)

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

Comment? (D astuces spécifiques)

Le système de modèles de D est plus court que celui de C ++ et peut déduire des types. Et D initialise également ses variables à la valeur par défaut lors de la déclaration.

Mathematica, 30 octets

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

Fonction pure prenant un entier non négatif en entrée et retournant Trueou False. Si l'entrée est n, (r=Range@#-1)définit la variable rà être {0, 1, ..., n-1}, puis r2^r+1calcule de manière vectorielle les premiers nnombres Cullen. MemberQ[...,#]vérifie ensuite s'il ns'agit d'un élément de la liste.

Mathematica, 32 octets

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

Excel VBA, 45 octets

Fonction de fenêtre immédiate VBE anonyme qui prend les entrées de la cellule [A1]et les sorties dans la fenêtre immédiate VBE

Doit être exécuté dans un module propre ou avoir des valeurs pour i, j être réinitialisé à la valeur par défaut de 0 entre les exécutions

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

Entrée sortie

E / S comme vu dans la fenêtre immédiate 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 octets

f(X)réussit s'il peut trouver une valeur I où X = I * 2 ^ I + 1. L'indice de plage l'empêche de manquer d'espace de pile, mais il suffit pour la plage de nombres Cullen jusqu'à 10 ^ 9 dans la spécification de question.

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

par exemple

f(838860801).
true

cQuents , 9 octets

$0?1+$2^$

Essayez-le en ligne!

Explication

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

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

Explication

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 octets

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

Explication

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

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

Essayez-le en ligne. Truthy est un tableau contenant un nombre: ,3ou ,0cetera. Falsey est un tableau vide: ()ou !0selon votre interprète.

Java (OpenJDK 8) , 56 octets

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

Essayez-le en ligne!

Pari / GP , 25 octets

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

Essayez-le en ligne!