Am I a Cullen Number?

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

Fair enough. Just needed to know whether my Jelly answer should have an Ḷ or R in it :-) — user62131
– user62131, Commented Jun 17, 2017 at 20:25

yoann · Accepted Answer · 2017-06-19 14:44:54Z

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⁽¹⁾.

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

⁽¹⁾In fact, this equality seems to hold for values of y up to 50000.

Well, I'm pretty sure this qualifies as the most interesting code for this challenge so far. +1 — Gryphon
– Gryphon, Commented Jun 18, 2017 at 14:30
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! — Cody Gray
– Cody Gray, Commented Jun 19, 2017 at 11:41

score 8 · Accepted Answer · 2017-06-17 20:38:55Z

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.

jacoblaw · Accepted Answer · 2017-06-18 02:03:32Z

7

Pyth, 6 5 bytes

/mh.<

try it online

edited Jun 18, 2017 at 2:03

answered Jun 17, 2017 at 23:49

jacoblaw

2661 silver badge4 bronze badges

Add a comment |

Arnauld · Accepted Answer · 2017-06-17 21:13:22Z

7

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

edited Jun 17, 2017 at 21:13

answered Jun 17, 2017 at 20:19

Arnauld

206k21 gold badges187 silver badges670 bronze badges

\$\begingroup\$ Does x<n?f(n,k+1):x==n work? \$\endgroup\$

Neil
– Neil

2017-06-17 20:57:40 +00:00
Commented Jun 17, 2017 at 20:57
\$\begingroup\$ @Neil It sure does. :-) \$\endgroup\$

Arnauld
– Arnauld

2017-06-17 21:13:32 +00:00
Commented Jun 17, 2017 at 21:13
\$\begingroup\$ Why does `~k work, while k+1 overloads the callstack? \$\endgroup\$

trlkly
– trlkly

2017-06-18 20:17:14 +00:00
Commented Jun 18, 2017 at 20:17
\$\begingroup\$ @trlkly Basically, undefined+1===NaN but -~undefined===1. You can read more about this here. \$\endgroup\$

Arnauld
– Arnauld

2017-06-18 21:13:25 +00:00
Commented Jun 18, 2017 at 21:13

Add a comment |

nimi · Accepted Answer · 2017-06-17 20:27:17Z

5

Haskell, 28 bytes

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

Try it online!

answered Jun 17, 2017 at 20:27

nimi

36k4 gold badges35 silver badges100 bronze badges

Add a comment |

FrodCube · Accepted Answer · 2017-06-17 20:40:12Z

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?

Jörg Hülsermann · Accepted Answer · 2017-06-17 20:54:56Z

3

PHP, 43 bytes

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

Try it online!

edited Jun 17, 2017 at 20:54

answered Jun 17, 2017 at 20:42

Jörg Hülsermann

13.4k3 gold badges16 silver badges36 bronze badges

\$\begingroup\$ Is $argn a special variable? Changing it to $a would save 6 bytes: tio.run/##K8go@G9jX5BRwKWSaKtkaGaoZP0/… \$\endgroup\$

topher
– topher

2017-06-19 15:39:39 +00:00
Commented Jun 19, 2017 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
– Jörg Hülsermann

2017-06-19 16:26:36 +00:00
Commented Jun 19, 2017 at 16:26

Add a comment |

sporkl · Accepted Answer · 2017-06-17 21:30:28Z

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.

BLT · Accepted Answer · 2017-06-17 22:09:20Z

3

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!

edited Jun 17, 2017 at 22:09

answered Jun 17, 2017 at 20:28

BLT

1,0019 silver badges13 bronze badges

\$\begingroup\$ use x%in%... instead of any(x==...); that'll drop you 4 bytes \$\endgroup\$

Giuseppe
– Giuseppe

2017-06-17 21:56:52 +00:00
Commented Jun 17, 2017 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
– BLT

2017-06-18 01:09:25 +00:00
Commented Jun 18, 2017 at 1:09

Add a comment |

HatsuPointerKun · Accepted Answer · 2017-08-01 23:41:50Z

3

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

answered Aug 1, 2017 at 23:41

HatsuPointerKun

2,2111 gold badge9 silver badges13 bronze badges

\$\begingroup\$ I'll post the optimized D version this time, some pretty D-specific tricks can be used. \$\endgroup\$

Adalynn
– Adalynn

2017-08-03 21:55:41 +00:00
Commented Aug 3, 2017 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
– ceilingcat

2018-11-28 04:24:02 +00:00
Commented Nov 28, 2018 at 4:24

Add a comment |

Dominic van Essen · Accepted Answer · 2023-03-07 13:27:37Z

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

Ginger · Accepted Answer · 2024-09-21 16:44:33Z

Vyxal 3, 6 bytes

ʀ:E×ꜝc

Vyxal It Online!

Port of lyxal's v2 answer. Explanation:

ʀ # ‎⁡For x in [0..n): :E× # ‎⁢ Multiply x by 2**x ꜝ # ‎⁣ Increment x c # ‎⁤Is the input in this sequence? 💎

Created with the help of Luminespire.

Uriel · Accepted Answer · 2017-06-17 20:26:18Z

2

Python, 40 bytes

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

Try it online!

edited Jun 17, 2017 at 20:26

answered Jun 17, 2017 at 20:21

Uriel

13.3k4 gold badges18 silver badges45 bronze badges

Add a comment |

ovs · Accepted Answer · 2017-06-17 20:54:22Z

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

Giuseppe · Accepted Answer · 2017-06-17 21:53:46Z

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.

\$\begingroup\$ I never remember scan(). Good work. \$\endgroup\$

BLT
– BLT

2017-06-17 22:10:17 +00:00
Commented Jun 17, 2017 at 22:10 — BLT
– BLT, Commented Jun 17, 2017 at 22:10

Adám · Accepted Answer · 2017-06-18 00:16:38Z

2

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)

edited Jun 18, 2017 at 0:16

answered Jun 17, 2017 at 23:10

Adám

31.8k4 gold badges131 silver badges293 bronze badges

\$\begingroup\$ So, "default on many systems" means that it just exists? \$\endgroup\$

Adalynn
– Adalynn

2017-08-03 22:03:14 +00:00
Commented Aug 3, 2017 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
– Adám

2017-08-04 04:10:03 +00:00
Commented Aug 4, 2017 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\$

Adalynn
– Adalynn

2017-08-04 20:37:10 +00:00
Commented Aug 4, 2017 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
– Adám

2017-08-05 22:04:33 +00:00
Commented Aug 5, 2017 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\$

Adalynn
– Adalynn

2017-08-05 22:12:15 +00:00
Commented Aug 5, 2017 at 22:12

Add a comment |

Taylor Raine · Accepted Answer · 2017-06-18 15:38:23Z

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

xnor · Accepted Answer · 2017-06-19 16:54:56Z

2

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.

edited Jun 19, 2017 at 16:54

answered Jun 18, 2017 at 4:54

xnor

150k26 gold badges287 silver badges676 bronze badges

\$\begingroup\$ You can save two bytes using n<<n|1 (n<<n being even) ;) \$\endgroup\$

Vincent
– Vincent

2017-06-18 09:41:19 +00:00
Commented Jun 18, 2017 at 9:41
\$\begingroup\$ This fails for 838860801. You need range(26), because the range isn't inclusive. \$\endgroup\$

mbomb007
– mbomb007

2017-06-19 16:52:17 +00:00
Commented Jun 19, 2017 at 16:52
\$\begingroup\$ @mbomb007 Thanks. I've done this for a while and still sometimes forget ranges are right-exclusive. \$\endgroup\$

xnor
– xnor

2017-06-19 16:55:55 +00:00
Commented Jun 19, 2017 at 16:55

Add a comment |

calc84maniac · Accepted Answer · 2017-08-02 00:30:49Z

2

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

edited Aug 2, 2017 at 0:30

answered Aug 1, 2017 at 23:15

calc84maniac

1754 bronze badges

\$\begingroup\$ You might want to add an explanation to this. \$\endgroup\$

Gryphon
– Gryphon

2017-08-01 23:58:07 +00:00
Commented Aug 1, 2017 at 23:58
\$\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
– Gryphon

2017-08-02 00:24:42 +00:00
Commented Aug 2, 2017 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
– Gryphon

2017-08-02 00:32:51 +00:00
Commented Aug 2, 2017 at 0:32

Add a comment |

Adalynn · Accepted Answer · 2017-08-03 22:01:27Z

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.

chunes · Accepted Answer · 2023-03-06 18:43:46Z

2

Arturo, 29 bytes

$=>[in?&map 0..25'n->1+n*2^n]

Try it

answered Mar 6, 2023 at 18:43

chunes

27.8k3 gold badges32 silver badges55 bronze badges

Add a comment |

Ashlin Harris · Accepted Answer · 2023-08-18 22:48:18Z

2

Julia 1.0, 23 bytes

~n=n∈0:n.|>x->x*2^x+1

Try it online!

answered Aug 18, 2023 at 22:48

Ashlin Harris

2,1414 silver badges8 bronze badges

Add a comment |

Glory2Ukraine · Accepted Answer · 2024-09-21 13:00:32Z

Husk, 11 bytes

€¹mλ→*^¹2)ŀ

Try it online!

Outputs 0 if the input number is NOT a Cullen Number. Otherwise the output is an integer value (the number's index in the sequence).

 ŀ # Make a range: 0 to input number m # Map over the range λ ) # Apply the following function: ^¹2 # - calculate 2^n * # - multiply by n → # - increment by 1 €¹ # Check whether the input value is in the list

Greg Martin · Accepted Answer · 2017-06-18 01:08:58Z

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.

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Mathematica, 32 bytes

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jun 18, 2017 at 12:22

ZaMoC

25.5k2 gold badges32 silver badges87 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

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`

Sean · Accepted Answer · 2023-03-06 20:30:16Z

Raku, 30 bytes

{$_∈({1+$++*2**$++}...*>$_)}

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 (∈).

Shaggy · Accepted Answer · 2023-03-07 12:06:21Z

Japt `-d`, 7 bytes

ÑpU ¶NÉ

Try it

Ñ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

lyxal · Accepted Answer · 2023-03-07 12:19:00Z

Vyxal, 6 bytes

ʀ:E*›c

Try it Online!

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?

Am I a Cullen Number?

Your Task:

Input:

Output:

Test Cases:

Scoring:

40 Answers 40

x86_64 machine code (System V ABI), 28 27 bytes

Jelly, 7 6 bytes

Explanation

Pyth, 6 5 bytes

JavaScript (ES6), 37 35 bytes

Demo

Haskell, 28 bytes

Ohm, 8 bytes

PHP, 43 bytes

05AB1E, 7 bytes

R, 53 51 46 bytes

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

Nibbles, 5.5 bytes (11 nibbles)

Vyxal 3, 6 bytes

Python, 40 bytes

Python 2, 36 bytes

Python 2, 42 bytes

R, 26 bytes

APL (Dyalog), 9 bytes

Excel VBA, 45 Bytes

Input / Output

Python 2, 32 bytes

TI-BASIC, 17 bytes

D, 65 bytes

How? (D specific tricks)

Arturo, 29 bytes

Julia 1.0, 23 bytes

Husk, 11 bytes

Mathematica, 30 bytes

Mathematica, 32 bytes

Swi-Prolog, 69 bytes

cQuents, 9 bytes

Explanation

Raku, 30 bytes

Japt -d, 7 bytes

Vyxal, 6 bytes

Explained

Linked

Related

Hot Network Questions

Japt `-d`, 7 bytes