[Question]
  [
A Cullen Number is any number that is contained in the sequence generated using the formula:
C(n) = (n\*2^n)+1. 
## Your Task:
Write a program or function that receives an input and outputs a truthy/falsy value based on whether the input is a Cullen Number. 
## Input:
A non-negative integer between 0 and 10^9 (inclusive). 
## Output:
A truthy/falsy value that indicates whether the input is a Cullen Number. 
## Test Cases:
```
Input:    Output:
1   --->  truthy
3   --->  truthy
5   --->  falsy
9   --->  truthy
12  --->  falsy
25  --->  truthy
```
## Scoring:
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the lowest score in bytes wins. 
  
[Answer]
## x86\_64 machine code ([System V ABI](https://en.wikipedia.org/wiki/X86_calling_conventions#System_V_AMD64_ABI)), 28 27 bytes
-1 byte thanks to @Cody Gray, thanks!
A constant-time algorithm!
```
_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
```
**Explanation:**
Let *y* an integer and `x=y*2^y + 1`.
Taking logs, we have `y + log2(y) = log2(x-1)`, thus `y=log2(x-1)-log2(y)`. Plugging back the value of y, we get `y=log2(x-1)-log2(log2(x-1)-log2(y))`. Doing this one more time, we obtain: `y=log2(x-1)-log2[log2(x-1)-log2(log2(x-1)-log2(log2(x-1)-log2(y)))]`. 
Let us remove the last terms (of the order of `log2(log2(log2(log2(x))))`, this should be safe!), and assume that `x-1≈x`, we obtain:
`y≈log2(x)-log2[log2(x)-log2(log2(x))]`
Now, letting `f(n) = floor(log2(n))`, it can be verified manually that `y` can be exactly retrieved by:
`y=f(x)-f[f(x)-f(f(x))]`,
for *y < 26*, and thus *x ⩽ 10^9*, as specified by the challenge(1). 
The algorithm then simply consists of computing *y* given *x*, and verify that *x == y\*2^y + 1*.
The trick is that `f(n)` can simply be implemented as the `bsr` instruction (bit-scan reverse), which returns the index of the first 1-bit in *n*, and `y*2^y` as `y << y`.
**Detailed 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);
                                         ; }
```
(1)In fact, this equality seems to hold for values of *y* up to 50000.
[Answer]
# **Pyth, ~~6~~ 5 bytes**
```
/mh.<
```
[try it online](https://pyth.herokuapp.com/?code=%2Fmh.<&input=25&debug=0)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~7~~ 6 bytes
```
Ḷæ«`i’
```
[Try it online!](https://tio.run/##y0rNyan8///hjm2Hlx1anZD5qGHm////jUwB "Jelly – Try It Online")
Takes input as a command-line argument. If given a Cullen number C(*n*), outputs *n*+1 (which is truthy in Jelly, being an nonzero integer; note that we have *n*≥0 because the input is an integer, and Cullen numbers with negative *n* are never integers). If given a non-Cullen number, returns 0, which is falsey in Jelly.
## Explanation
```
Ḷæ«`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
```
Basically, form an array of Cullen numbers minus one, then look for the input minus one in it. If the input is a Cullen number, we'll find it, otherwise we won't. Note that the array is necessarily long enough to reach to the input, because C(*n*) is always greater than *n*.
[Answer]
## JavaScript (ES6), ~~37~~ 35 bytes
*Saved 2 bytes thanks to 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))))
```
[Answer]
## Haskell, 28 bytes
```
f n=or[x*2^x+1==n|x<-[0..n]]
```
[Try it online!](https://tio.run/##y0gszk7Nyfn/P00hzza/KLpCyyiuQtvQ1javpsJGN9pATy8vNvZ/bmJmnoKtQkFRZl6JgopCbmKBQppCtLGOpY6hkY6Raex/AA "Haskell – Try It Online")
[Answer]
# [Ohm](https://github.com/MiningPotatoes/Ohm), 8 bytes
```
@Dº*≥Dlε
```
[Try it online!](https://tio.run/##y8/I/f/fweXQLq1HnUtdcs5t/f/fyBQA "Ohm – Try It 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?
```
[Answer]
# [PHP](https://php.net/), 43 bytes
```
for(;$argn>$c=1+2**$n*$n++;);echo$argn==$c;
```
[Try it online!](https://tio.run/##K8go@G9jX5BRwKWSWJSeZ6tkaGaoZP0/Lb9IwxosYqeSbGuobaSlpZIHRNra1prWqckZ@RDVtirJ1v//AwA "PHP – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 7 bytes
```
ÝDo*¹<å
```
[Try it online!](https://tio.run/##MzBNTDJM/f//8FyXfK1DO20OL/3/39AIAA "05AB1E – Try It Online")
**Explanation:**
```
Ý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.
```
[Answer]
# [R](https://www.r-project.org/), ~~53~~ ~~51~~ 46 bytes
```
pryr::f(x%in%lapply(0:x,function(y)(y*2^y+1)))
```
Anonymous function. Checks if `x` is generated in the sequence C(n) for n in [0,x].
3 bytes golfed by Giuseppe.
[Try it online!](https://tio.run/##K/r/P802rTQvuSQzP0@jQrM6Ma9So8LWNiexoCCnUsPQqkIHLlupqVGpZRRXqW2oqalZy5WmYawJJAyNQKSRKZhtYGRiCGMYaf7//x8A "R – Try It Online")
[Answer]
## C, C++, Java, C#, D : 70 bytes
Due to the similarities between all these languages, this code works for each
```
int c(int n){for(int i=0;i<30;++i)if((1<<i)*i+1==n)return 1;return 0;}
```
[Answer]
# Python, 40 bytes
```
lambda n:any(x<<x==n-1for x in range(n))
```
[Try it online!](https://tio.run/##FcoxCoAgGAbQq3yjgQ0mDUmepBqMysL6DXHQ01uuj/fmeHqSxUJjLrd51s2AlKHM0jgmrakVhw9IuAjBkN0ZNU2p5CpNkmPgEB1H1y8Kb7goMsdhmfvfBw)
[Answer]
# [Python 2](https://docs.python.org/2/), 36 bytes
```
f=lambda n,i=0:i<<i!=n-1and f(n,i+1)
```
[Try it online!](https://tio.run/##PcuxCsIwFIXhPU9x3CxewUQcDM3aJ3ATh2gTvFBvQ0zBPn0MCE6H/4OT1vKcxdQa3eRf99FDiN3Bct/zxsleexkRtw13uqtxzmCw4HoknAnaEMzpZhVSZilgUih5bd0@3LX5@SUvQSF8HiEV@9fBT@9Qvw "Python 2 – Try It Online")
Outputs by not crashing / crashing, as *currently* allowed by [this meta concensus](https://codegolf.meta.stackexchange.com/a/11908/64121).
---
# [Python 2](https://docs.python.org/2/), 42 bytes
```
i=0
n=input()-1
while i<<i<n:i+=1
i<<i>n<c
```
[Try it online!](https://tio.run/##PYzBCsIwEETv@xVLTooIpuLBkHjToyd/oMSFLtRNWFNsvz6mIF6GN7xh8lKGJF2N6UnBGFM5HEACS57KZru38Bl4JGTv2YvjXbCw8kV8rG3@09YBFl1aIs0UcX1rnJWl4EOnVmiOlAve@xddVZO6v7/145vqEc5gO@hOXw "Python 2 – Try It Online")
Outputs via exit code
[Answer]
# [R](https://www.r-project.org/), 26 bytes
```
a=0:26;scan()%in%(1+a*2^a)
```
[Try it online!](https://tio.run/##K/r/P9HWwMrIzLo4OTFPQ1M1M09Vw1A7UcsoLlHzv6GCsYKlgqGRgpHpfwA "R – Try It Online")
A slightly different approach than the [other R answer](https://codegolf.stackexchange.com/a/127079/67312); reads from `stdin` and since the input is guaranteed to be between 0 and 10^9, we just have to check `n` between 0 and 26.
[Answer]
# [APL (Dyalog)](https://www.dyalog.com/), 9 bytes
To cover the case of *n* = 1, it requires `⎕IO←0` which is default on many systems.
```
⊢∊1+⍳×2*⍳
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///qG@qp/@jtgkG/5OB5KOuRY86ugy1H/VuPjzdSAtI/f@ffGiFoYKxgqWCoZGCkSkA "APL (Dyalog Unicode) – Try It Online")
`⊢` [is] *n* (the argument)
`∊` a member of
`1` one
`+` plus
`⍳` the **i**ntegers 0 … (*n*-1)
`×` times
`2` two
`*` to the power of
`⍳` the **i**ntegers 0 … (*n*-1)
[Answer]
# [Python 2](https://docs.python.org/2/), 32 bytes
```
[n<<n|1for n in range(26)].count
```
[Try it online!](https://tio.run/##K6gsycjPM/qfZhvzPzrPxiavxjAtv0ghTyEzT6EoMS89VcPITDNWLzm/NK/kP5qMoYGBgaYVF2dmmkKaRh6IxVlQlJlXopD3HwA "Python 2 – Try It Online")
Creates the list of Cullen numbers up to `10^9`, then counts how many times the input appears in it. Thanks to Vincent for pointing out `n<<n|1` instead of `(n<<n)+1`, saving 2 bytes.
[Answer]
# TI-BASIC, 17 bytes
```
max(Ans=seq(X2^X+1,X,0,25
```
**Explanation**
```
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
```
[Answer]
# D, 65 bytes
This is a port of @HatsuPointerKun's algorithm to D (the original was already D code, but this is with D-specific tricks)
```
T c(T)(T n){for(T i;i<30;++i)if((1<<i)*i+1==n)return 1;return 0;}
```
# How? (D specific tricks)
D's template system is shorter than C++'s, and can infer types. And D also initializes its variables to the default upon declaration.
[Answer]
# [Nibbles](http://golfscript.com/nibbles/index.html), 5.5 bytes (11 nibbles)
```
?.`,$+~*^2
```
Returns 1-based index in list of Cullen numbers (truthy), or zero (falsy) if not a Cullen number.
```
?.`,$+~*^2      # full function
?.`,$+~*^2$$$   # (with implicit arguments shown):
 .              # map over
  `,$           # 0..input-1
                # with function:
     +          #   add
      ~         #   1 (default)
                #   to
        ^2      #   2 to the power of
          $     #   input
       *   $    #   multiplied by input
?           $   # and get the index of the input in this
                # (or zero if not found)
```
[![enter image description here](https://i.stack.imgur.com/thOmk.png)](https://i.stack.imgur.com/thOmk.png)
[Answer]
# [Julia 1.0](http://julialang.org/), 23 bytes
```
~n=n∈0:n.|>x->x*2^x+1
```
[Try it online!](https://tio.run/##XY5BasMwEEXX1ikGr@TWDrVLFg3I7TaXCCj1hE4REyGNQYGSdc6ZizhK3RSSWQ1/3vz/v0dHtk3TdGTD59PpZcWLnz41fXrqNum5nXb7AATEENAOjhijrhTksTVswUCUQH6ho3ckmmoom6bpy6pSBbEfJRPehoh6zVKDzTImj5@CQ75sjSkljPJ1KOEd8oawgp11EVWxH2V@P/76qMIHYnGs/2x7mIns@GFjxCBwezFwy1DIw9TmstdSAHOWen0Ulv/CNfyg3h6BtrsHuuU9cAE "Julia 1.0 – Try It Online")
[Answer]
# Mathematica, 30 bytes
```
MemberQ[(r=Range@#-1)2^r+1,#]&
```
Pure function taking a nonnegative integer as input and returning `True` or `False`. If the input is `n`, then `(r=Range@#-1)` sets the variable `r` to be `{0, 1, ..., n-1}`, and then `r2^r+1` vectorially computes the first `n` Cullen numbers. `MemberQ[...,#]` then checks whether `n` is an element of the list.
[Answer]
# Mathematica, 32 bytes
```
!Table[x*2^x+1,{x,0,#}]~FreeQ~#&
```
[Answer]
# Excel VBA, 45 Bytes
Anonymous VBE immediate window function that takes input from cell `[A1]` and ouputs to the VBE immediate window
*Must be run in a clean module or have values for i,j be reset to default value of 0 between runs*
```
While j<[A1]:j=(i*2 ^ i)+1:i=i+1:Wend:?j=[A1]
```
### Input / Output
I/O as seen in VBE immediate window
```
[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 
```
[Answer]
## Swi-Prolog, 69 bytes
`f(X)` succeeds if it can find a value I where X = I\*2^I+1. The range hint stops it running out of stack space, but it's enough for the range of Cullen numbers up to 10^9 in the question spec.
```
:-use_module(library(clpfd)).
f(X):-I in 0..30,X#=I*2^I+1,label([I]).
```
e.g.
```
f(838860801).
true
```
[Answer]
# [cQuents](https://github.com/stestoltz/cQuents), 9 bytes
```
$0?1+$2^$
```
[Try it online!](https://tio.run/##Sy4sTc0rKf7/X8XA3lBbxShO5f9/I1MA "cQuents – Try It Online")
## Explanation
```
$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`
```
[Answer]
# [Arturo](https://arturo-lang.io), 29 bytes
```
$=>[in?&map 0..25'n->1+n*2^n]
```
[Try it](http://arturo-lang.io/playground?hBfxpN)
[Answer]
# [Raku](https://raku.org/), 30 bytes
```
{$_∈({1+$++*2**$++}...*>$_)}
```
[Try it online!](https://tio.run/##K0gtyjH7n1upoJamYPu/WiX@UUeHRrWhtoq2tpaRlhaQqtXT09OyU4nXrP1fnFipoKQSr2Brp1CdpqASX6ukkJZfpGCop2dk@h8A "Perl 6 – Try It Online")
The parenthesized expression is a list of generated Cullen numbers, taken up to the point where a number is greater than the input argument (`* > $_`). Then we just check that the input argument is a member of that list (`∈`).
[Answer]
# [Japt](https://github.com/ETHproductions/japt) [`-d`](https://codegolf.meta.stackexchange.com/a/14339/), 7 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
```
ÑpU ¶NÉ
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&flags=LWQ&code=0XBVILZOyQ&input=MjU)
```
ÑpU ¶NÉ     :Implicit map of each U in the range [0,input)
Ñ           :Multiply by 2
 pU         :Raised to the power of U
    ¶       :Is equal to
     N      :Array of all inputs
      É     :Minus 1
            :Implicit output of whether or not any U returns true
```
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), 6 bytes
```
ʀ:E*›c
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyJBIiwiIiwiyoA6RSrigLpjIiwiIiwiMVxuM1xuNVxuOVxuMTJcbjI1Il0=)
## Explained
```
ʀ:E*›c
ʀ:     # push 2 copies of the range [0, input]
  E    # 2 ** x for x in ^
   *   # vectorised multiply with the other copy
    ›  # + 1
     c # contains the input?
```
[Answer]
# [Thunno](https://github.com/Thunno/Thunno) `D`, \$ 11 \log\_{256}(96) \approx \$ 9.05 bytes
```
RD2@z*s1-Aq
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72sJKM0Ly9_abSSi1LsgqWlJWm6FquDXIwcqrSKDXUdCyEiUIkFi4xMISwA)
#### Explanation
```
RD2@z*s1-Aq  # Implicit input
RD           # Push range(input) and duplicate
  2@         # Pop one copy and push 2 ** each
    z*       # Multiply elementwise
      s1-    # Push the input decremented
         Aq  # Is this in the list?
```
[Answer]
# [Pyt](https://github.com/mudkip201/pyt), 8 bytes
```
Đ0⇹ŘĐ«⁺∈
```
[Try it online!](https://tio.run/##ARoA5f9weXT//8SQMOKHucWYxJDCq@KBuuKIiP//MQ "Pyt – Try It Online")
```
Đ             implicit input; Đuplicate
 0⇹Ř          Řangify from 0 to n
    Đ         Đuplicate
     «        bitshift left
      ⁺       increment
       ∈      is input in list of Cullen numbers?; implicit print
```
]