25
\$\begingroup\$

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 , so the lowest score in bytes wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ What's the range of n? In particular, is 1 a Cullen Number? \$\endgroup\$ – user62131 Jun 17 '17 at 20:15
  • 3
    \$\begingroup\$ @ais523 according to OEIS, it is. n seems to be 0-based. \$\endgroup\$ – steenbergh Jun 17 '17 at 20:25
  • \$\begingroup\$ Fair enough. Just needed to know whether my Jelly answer should have an or R in it :-) \$\endgroup\$ – user62131 Jun 17 '17 at 20:25
  • 2
    \$\begingroup\$ Related \$\endgroup\$ – DJMcMayhem Jun 17 '17 at 20:36
  • \$\begingroup\$ Umm, what's with the downvote? \$\endgroup\$ – Gryphon - Reinstate Monica Jun 20 '17 at 13:47

26 Answers 26

7
\$\begingroup\$

Pyth, 6 5 bytes

/mh.<

try it online

\$\endgroup\$
16
\$\begingroup\$

x86_64 machine code (System V 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.

\$\endgroup\$
  • 4
    \$\begingroup\$ Well, I'm pretty sure this qualifies as the most interesting code for this challenge so far. +1 \$\endgroup\$ – Gryphon - Reinstate Monica Jun 18 '17 at 14:30
  • 1
    \$\begingroup\$ Pre-XORing eax would allow you to eliminate the movzbl, saving 1 byte. You'd need to do the XOR before the cmpl so it doesn't clobber the flags, of course, but that's totally fine because nothing after that depends on eax. Or, you could just decide that the method returns a Boolean in only the lower 8 bits, saving all 3 bytes! \$\endgroup\$ – Cody Gray Jun 19 '17 at 11:41
  • \$\begingroup\$ @CodyGray Indeed, thanks a lot :) \$\endgroup\$ – yoann Jun 19 '17 at 14:46
7
\$\begingroup\$

Jelly, 7 6 bytes

Ḷæ«`i’

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.

\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Does x<n?f(n,k+1):x==n work? \$\endgroup\$ – Neil Jun 17 '17 at 20:57
  • \$\begingroup\$ @Neil It sure does. :-) \$\endgroup\$ – Arnauld Jun 17 '17 at 21:13
  • \$\begingroup\$ Why does `~k work, while k+1 overloads the callstack? \$\endgroup\$ – trlkly Jun 18 '17 at 20:17
  • \$\begingroup\$ @trlkly Basically, undefined+1===NaN but -~undefined===1. You can read more about this here. \$\endgroup\$ – Arnauld Jun 18 '17 at 21:13
5
\$\begingroup\$

Haskell, 28 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Ohm, 8 bytes

@Dº*≥Dlε

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?
\$\endgroup\$
3
\$\begingroup\$

PHP, 43 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Is $argn a special variable? Changing it to $a would save 6 bytes: tio.run/##K8go@G9jX5BRwKWSaKtkaGaoZP0/… \$\endgroup\$ – topher Jun 19 '17 at 15:39
  • \$\begingroup\$ @topher Yes $argn is available if you run PHP from the command line with the -R option \$\endgroup\$ – Jörg Hülsermann Jun 19 '17 at 16:26
3
\$\begingroup\$

05AB1E, 7 bytes

ÝDo*¹<å

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.
\$\endgroup\$
3
\$\begingroup\$

R, 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!

\$\endgroup\$
  • \$\begingroup\$ use x%in%... instead of any(x==...); that'll drop you 4 bytes \$\endgroup\$ – Giuseppe Jun 17 '17 at 21:56
  • \$\begingroup\$ So if I golf this by changing the lapply to simply checking the vector, and use scan instead of taking function arguments - I get @giuseppe 's answer. Thanks for posting it separately so I can see what I'm missing - I learn more by trying something on my own, even though I usually lose. \$\endgroup\$ – BLT Jun 18 '17 at 1:09
3
\$\begingroup\$

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;}
\$\endgroup\$
  • \$\begingroup\$ I'll post the optimized D version this time, some pretty D-specific tricks can be used. \$\endgroup\$ – Zacharý Aug 3 '17 at 21:55
  • \$\begingroup\$ Suggest i=30;i--;)if(i<<i==n-1) instead of i=0;i<30;++i)if((1<<i)*i+1==n) \$\endgroup\$ – ceilingcat Nov 28 '18 at 4:24
2
\$\begingroup\$

Python, 40 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 2, 36 bytes

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

Try it online!

Outputs by not crashing / crashing, as currently allowed by this meta concensus.


Python 2, 42 bytes

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

Try it online!

Outputs via exit code

\$\endgroup\$
2
\$\begingroup\$

R, 26 bytes

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

Try it online!

A slightly different approach than the other R answer; 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.

\$\endgroup\$
  • \$\begingroup\$ I never remember scan(). Good work. \$\endgroup\$ – BLT Jun 17 '17 at 22:10
2
\$\begingroup\$

APL (Dyalog), 9 bytes

To cover the case of n = 1, it requires ⎕IO←0 which is default on many systems.

⊢∊1+⍳×2*⍳

Try it online!

 [is] n (the argument)

 a member of

1 one

+ plus

 the integers 0 … (n-1)

× times

2 two

* to the power of

 the integers 0 … (n-1)

\$\endgroup\$
  • \$\begingroup\$ So, "default on many systems" means that it just exists? \$\endgroup\$ – Zacharý Aug 3 '17 at 22:03
  • \$\begingroup\$ @Zacharý Yes, it would be wrong to call ⎕IO←0 non-standard, as many indeed always have it set like that, with no specification necessary each time. \$\endgroup\$ – Adám Aug 4 '17 at 4:10
  • \$\begingroup\$ Well. I'm going to use that trick in MY for sure (and MY can have non-0 and non-1 Index Origins) if I ever get the chance to. \$\endgroup\$ – Zacharý Aug 4 '17 at 20:37
  • \$\begingroup\$ @Zacharý Wouldn't that require an actual install base/versions where those values are default? E.g. in SAX and ngn, ⎕IO←0. \$\endgroup\$ – Adám Aug 5 '17 at 22:04
  • \$\begingroup\$ Yeah, I guess it would. And MY does have three iotas, so I think that wouldn't be used anyways. \$\endgroup\$ – Zacharý Aug 5 '17 at 22:12
2
\$\begingroup\$

Python 2, 32 bytes

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

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.

\$\endgroup\$
  • \$\begingroup\$ You can save two bytes using n<<n|1 (n<<n being even) ;) \$\endgroup\$ – Vincent Jun 18 '17 at 9:41
  • \$\begingroup\$ This fails for 838860801. You need range(26), because the range isn't inclusive. \$\endgroup\$ – mbomb007 Jun 19 '17 at 16:52
  • \$\begingroup\$ @mbomb007 Thanks. I've done this for a while and still sometimes forget ranges are right-exclusive. \$\endgroup\$ – xnor Jun 19 '17 at 16:55
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Mathematica, 32 bytes

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

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 
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

cQuents, 9 bytes

$0?1+$2^$

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`
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You might want to add an explanation to this. \$\endgroup\$ – Gryphon - Reinstate Monica Aug 1 '17 at 23:58
  • \$\begingroup\$ Done, thanks for the tip. \$\endgroup\$ – calc84maniac Aug 2 '17 at 0:12
  • \$\begingroup\$ That works, but a command-by-command explanation usually helps garner most upvotes. I would reccomend doing something like the explanation on this answer. I don't know why somebody downvoted your post though. It's usually common courtesy to leave a comment when you do so, although that idea is often ignored. \$\endgroup\$ – Gryphon - Reinstate Monica Aug 2 '17 at 0:24
  • \$\begingroup\$ Your welcome. I remember when I first joined the site, people told these types of things to me. Just passing on the favour. \$\endgroup\$ – Gryphon - Reinstate Monica Aug 2 '17 at 0:32
0
\$\begingroup\$

QBIC, 24 bytes

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

Explanation

[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.
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 25 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.