77
\$\begingroup\$

Task:

Given an integer input, figure out whether or not it is a Cyclops Number.

What is a Cyclops number, you may ask? Well, it's a number whose binary representation only has one 0 in the center!

Test Cases:

Input | Output | Binary  | Explanation
--------------------------------------
0     | truthy | 0       | only one zero at "center"
1     | falsy  | 1       | contains no zeroes
5     | truthy | 101     | only one zero at center
9     | falsy  | 1001    | contains two zeroes (even though both are at the center)
10    | falsy  | 1010    | contains two zeroes
27    | truthy | 11011   | only one zero at center
85    | falsy  | 1010101 | contains three zeroes
101   | falsy  | 1100101 | contains three zeroes
111   | falsy  | 1101111 | only one zero, not at center
119   | truthy | 1110111 | only one zero at center

Input:

  • An integer or equivalent types. (int, long, decimal, etc.)

  • Assume that if evaluating the input results in an integer overflow or other undesirable problems, then that input doesn't have to be evaluated.

Output:

  • Truthy or falsy.

  • Truthy/falsy output must meet the used language's specifications for truthy/falsy. (e.g. C has 0 as false, non-zero as true)

Challenge Rules:

  • Input that is less than 0 is assumed to be falsy and thus does not have to be evaluated.

  • If the length of the binary representation of the number is even, then the number cannot be a Cyclops number.

General Rules:


This is my first Programming Puzzles & Code Golf challenge, so any feedback on how I should improve would be much appreciated!

\$\endgroup\$
6
  • 28
    \$\begingroup\$ Note: This is A129868 \$\endgroup\$
    – tsh
    Commented Mar 8, 2019 at 2:40
  • 40
    \$\begingroup\$ +1 for the 2800 year late pop culture reference in the title \$\endgroup\$
    – Sanchises
    Commented Mar 8, 2019 at 9:21
  • \$\begingroup\$ what is the maximum number that is be tested? \$\endgroup\$
    – Serverfrog
    Commented Mar 8, 2019 at 13:06
  • \$\begingroup\$ @Serverfrog since I did not specify a limit, assume that any positive integer can be tested. \$\endgroup\$ Commented Mar 8, 2019 at 14:09
  • \$\begingroup\$ Is binary input allowed? \$\endgroup\$
    – Qwertiy
    Commented May 25, 2019 at 8:22

62 Answers 62

1
\$\begingroup\$

Excel, 101 107 bytes

-6 bytes thanks to @Chronocidal.

=AND(ISEVEN(LOG(A1,2)),MID(DEC2BIN(A1),LEN(DEC2BIN(A1))/2+1,1)="0",LEN(SUBSTITUTE(DEC2BIN(A1),1,))=1)

Performs 3 checks:

  • Odd length
ISEVEN(LOG(A1,2))
  • Middle character is 0
MID(DEC2BIN(A1),LEN(DEC2BIN(A1))/2+1,1)="0"
  • There is a single 0
LEN(SUBSTITUTE(DEC2BIN(A1),1,))=1
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Save 6 bytes by changing ISODD(LEN(DEC2BIN(A1))) to ISEVEN(LOG(A1,2)) \$\endgroup\$ Commented Mar 8, 2019 at 13:11
1
\$\begingroup\$

Regex (ECMAScript), 65 59 57 58 bytes

+1 byte to handle 0 correctly

^((((x*)xx)\3)x)?(?=(\1*)\2*(?=\4$)((x*)(?=\7$)x)*$)\1*$\5

Try it online!

Works by asserting the input is of the form \$ (2^k - 1) (2^{k+1} + 1) \$. Ties Deadcode's answer but with a completely different algorithm.

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

VBA, 41 36 Bytes

x=2^Int([Log(A1,4)]):?[A1]=2*x^2-x-1

Run in the Immediate window, with Explicit Declaration turned off. Input is cell A1 of the active sheet. Outputs True/False to the immediate window.

Uses the same logic as my Excel Answer to find the Cyclops number of the same number of bits (or 1 bit shorter if there are an even number!) and then compares that with the input.

Saves some bytes when calculating Cyclops numbers by reducing them to the form y = 2x^2 - x - 1 (where x = n-1 for the nth Cyclops number, or x = 2^Int(Log([A1])/Log(4)) to find the largest Cyclops number with a lesser-or-equal number of bits) and storing x in a variable

(-5 Bytes thanks to Taylor Scott!)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Instead of converting the log's base using log division, you can change it directly using [...] notation as [(Log(A1,4)] \$\endgroup\$ Commented Mar 8, 2019 at 18:40
1
\$\begingroup\$

Haskell, 82 bytes

import Text.Printf
(`all`[(==)<*>reverse,("0"==).filter(<'1')]).flip($).printf"%b"

And a port of xnor's Python solution:

Haskell, 47 bytes

import Data.Bits
\n->(2*n`xor`(2*n+3))^2==8*n+9
\$\endgroup\$
1
\$\begingroup\$

APL(NARS), 57 char, 114 bytes

{⍵≤0:1⋄k=m←⌈k←2÷⍨≢v←{(2⍴⍨⌊1+2⍟⍵)⊤⍵}⍵:0⋄((,1)≡∪v∼⍦0)∧∼m⊃v}

test:

  f←{⍵≤0:1⋄k=m←⌈k←2÷⍨≢v←{(2⍴⍨⌊1+2⍟⍵)⊤⍵}⍵:0⋄((,1)≡∪v∼⍦0)∧∼m⊃v}
  ⎕fmt f¨0 1 5 12 27 85 101 119
┌8───────────────┐
│ 1 0 1 0 1 0 0 1│
└~───────────────┘

This below would be (modulus bugs) the function that would convert a positive integer number omega in one array of digits in base alpha:

{(⍺⍴⍨⌊1+⍺⍟⍵)⊤⍵}
\$\endgroup\$
1
\$\begingroup\$

Stax, 9 7 bytes

ç8┤-½Θ■

Run and debug it

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

K (ngn/k), 19 bytes

{1=(~x)+/~a&|a:2\x}

Try it online!

{ } function with argument x

2\x the bits of x

a: assign to a

a&|a and between a and its reverse (|a)

~ not

+/ sum

(~x) use "not x" as the initial value for the sum. this is to correct for 2\x returning an empty list of bits when x is 0

1= compare with 1

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

dc, 62 60 bytes

[2~rd0<B]dsBx1kz2/szsi[1r-si]sC[zlz=Cli*siz0<M]sMz1=Cz1<Mlip

Try it online!

dc has no native truthy/falsy values (conditionals either execute a macro or they don't); using 1 for truthy and 0 for falsy, I hope that's ok.

[2~rd0<B]dsBx          # Basic breakdown into binary. Every digit is a stack entry. Luckily this
                       # also leaves an extra 0 on the stack.
1k                     # Set precision to one - needed it at 0 for the binary-ifier.
z2/sz                  # Divide the stack depth by 2 and store it in 'z'. This is why we're lucky
                       # that the binary-ifier leaves an extra bit on the stack! Numbers with even 
                       # numbers of binary digits will now have an odd number & this value will be
                       # (whatever).5 which... isn't a valid stack depth.
si                     # Seed 'i' which is our truthiness register w/ that extra 0
[1r-si]sC              # Macro 'C' toggles the top of stack between 0 and 1 by subtracting it from 1.
                       # It stores this in 'i'. This is the only way 'i' ever becomes 1.
[zlz=Cli*siz0<M]sM     # First we test if we're at the position of the stack that matches up with 
                       # 'z', and run 'C' if so. Thus, if we're in the 'Cyclops' position (the
                       # middle), we'll flip that from a 0 to a 1 or vice versa. Next we load 'i'
                       # and multiply it by top of stack, putting that back in 'i'. For the first half
                       # this whole thing does nothing but multiply stuff by zero. In the middle
                       # position (if there is one) it sets 'i' to 1 if it's a zero. For the rest of
                       # the digits, it multiplies by '1' if things are ok, and '0' if there's another
                       # (Cyclops-invalidating) zero.
z1=Cz1<M               # 1 and 0 don't work w/o special treatment. Run 'C' if it's one of these, 
                       # otherwise start 'M'
lip                    # Print 'i'

Golfed off two bytes because my brain was fried and I was using a wasteful, convoluted method of toggling between 1 and 0.

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

Gaia, 10 9 bytes

b:ṭ¤0C1=∧

Try it online!

Verify All Test Cases

b:		% convert to binary and dup
  ṭ		% is it a palindrome?
        ∧	% and
   ¤0C		% is the count of zeros
      1=	% equal to 1?
		% implicit print top of stack
\$\endgroup\$
1
\$\begingroup\$

C++ (gcc), 142 \$\cdots\$ 59 55 bytes

Saved 10 a whopping 21 23 bytes thanks to ceilingcat!!!

int f(int n){int c=__builtin_ctz(~n);n=(n>>c)+2==2<<c;}

Try it online!

Ungolfed:

bool is_cyclops(int n)
{
    int ones = 1;
    while ((n & 1) == 1)
    {
        ++ones;
        n /= 2;
    }
    while (--ones, n /= 2, (n & 1) == 1)
    {
        // nothing to do
    }
    return n == 0 && ones == 0;
}
\$\endgroup\$
0
1
\$\begingroup\$

C++ (clang), 72 68 67 60 bytes

As with Neil's and Grimmy's solutions, this works by asserting that the input is of the form \$(2^k-1)(2^{k+1}+1)\$.

5 bytes were dropped thanks to Arnauld, by changing ((x)+1) to -~(x) and ((x)-1) to ~-(x), and then changing n-a*-b to n+a*b. An additional 7 bytes were dropped thanks to ceilingcat.

int f(int n){int z,k=1;while((z=n+~-k*~(k*=2))>0);return!z;}

Try it online!

Alternative 60 byter:

int f(int n){for(int o=n,k=1;n>0;)n=o+~-k*~(k*=2);return!n;}

Try it online!

Ungolfed:

bool is_cyclops_number(int n)
{
    for (int k=1;; k*=2)
    {
        int z = n - (k - 1) * (k*2 + 1);
        if (z == 0)
            return true;
        if (z < 0)
            return false;
    }
}

C (gcc) - x86 & most others, 41 34 bytes

Returns zero for true and nonzero for false.

k;f(n){for(k=1;n+~-k*~(k*=2)>0;);}

Try it online!

This demonstrates why I hate the implicit accumulator return value exploit that is commonly used in C submissions and less often in C++ submissions. It's fragile and very much architecture dependent. Here, it depends upon the comparison operator > not changing the value of the accumulator.

I did notice something quite curious regarding the ARM gcc assembly code. It appears that the return value hack is being explicitly supported, by copying the intermediate result r3, which wasn't stored into any variable, into the accumulator r0 once the loop is done:

        cmp     r3, #0
        bgt     .L2
        nop
        mov     r0, r3

Similarly on PowerPC gcc, where register 3 carries the return value:

        cmpwi 7,9,0
        bgt 7,.L2
        mr 3,9

Similarly on RISC-V gcc, where a0 carries the return value:

       add   a5,a5,a4
       bgtz  a5,10144 <f+0x12>
       nop
       mv    a0,a5

In fact, it appears the trick works on all but one of the architectures on godbolt. On MSP430 gcc 6.2.1, it yields the code with the equivalent of return 0 (as the return value is passed through R12):

        MOV.B   #0, R12
        CMP.W   R13, R12 { JL .L2
        NOP
\$\endgroup\$
0
1
\$\begingroup\$

Zsh --extendedglob, 30 bytes

>$[[##2]$1]
<`ls|rev`~*0*0*~1#

Attempt This Online!

Outputs via exit code (0 = is a cyclops number, 1 = not a cyclops number).

  • > - create the file
    • $[[##2]$1] - the input in base 2
  • <`ls|rev`~00*~1# - try to find a file that matches this pattern:
    • `ls|rev` - the file in reverse (i.e. palindromic)
    • ~ - but not this pattern
      • *0*0* - more than one 0
    • ~ - and not this pattern either
      • 1# - one or more 1s

The exit code depends on whether or not the pattern matched and the file could be found.

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

Burlesque, 21 bytes

b2JXXRA'0==j'0CN1==&&

Try it online!

b2   # As binary
J    # Duplicate
XX   # Split into chars (RA is supposed to work with strings but doesn't)
RA   # Get middle
'0== # Is 0
j    # Reorder stack
'0CN # Count of 0s
1==  # ==1
&&   # And

Shorter, but sadly doesn't work for zero case because 2dg returns empty list

Burlesque, 16 bytes

2dgJRAj0CN-.||n!

Try it online!

2dg # Base 2 as list of digits
J   # Duplicate
RA  # Get middle
j   # Reorder stack
0CN # Count 0s
-.  # Decrement (i.e 1 -> truthy, else falsy)
||n!# not or (Check both zero) 
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 9 bytes

b0₌O€vL≈=

Try it Online!

Output 0 → False, 1 → True

b         # To binary array
 0        # Push 0
  ₌       # Parallel apply next two operators:
   O      #   Count how many "0" and
    €     #   Split at "0"
     vL   # Lengths of parts
       ≈  # If its equal return 1
        = # If its equal number of zeroes, return 1, else 0
\$\endgroup\$
0
1
\$\begingroup\$

Swift 5.7, 60 bytes

{nil != (try?#/(1+)0\1/#.wholeMatch(in:String($0,radix:2)))}

SwiftFiddle link

Swift 5.7 introduced Regex literals, delimited by #/.../#. This code attempts to match the regex (1+)0\1 against the string, and returns whether or not it succeeded. Input may be any BinaryInteger.

I'm not certain that this is shorter than bit manipulation, but this is shorter than the existing answer.

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

Erlang 37 bytes

f(x)->Y=2*X bxor (2*X+3),Y*Y==8*X+9.
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 55 bitsv2, 6.875 bytes

b†Ḃ₍⁼∑≈

Try it Online!

Bitstring:

0111000000100000010011101011101001010010110100100111000
b†Ḃ₍⁼∑≈­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏⁠⁠⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁡‏⁠⁠‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁢​‎‏​⁢⁠⁢‌⁢⁣​‎‏​⁢⁠⁢‌­
b†       # ‎⁡Convert to binary, then invert each bit
  Ḃ      # ‎⁢Push the list of inverted bits and its reverse
   ₍  ≈  # ‎⁣is each item in the list equal?
    ⁼    # ‎⁤does the reverse of the inverted bits equal the inverted bits
     ∑   # ‎⁢⁡sum of the bits
‎
💎

Created with the help of Luminespire.

7 byter (before encoding) with a completely different method.

Edit: Apparently this is a port of Jelly but I didn't realize

‎⁢⁣Since the equality check can only be 0 or 1, and the sum of the inverted bits is always at least 1 for any nonzero number, the values can only be equal if there is exactly one "1" in the inverted binary representation and that "1" is directly in the middle

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

Java (OpenJDK 8), 135 130 bytes

Uses the Formula described here: A129868

(n)->java.util.stream.IntStream.range(0,16).map(r->((Double)(Math.pow(2,2*r+1)-(Math.pow(2,r)-1)-2)).intValue()).anyMatch(c->c==n)

Try it online!

\$\endgroup\$
7
  • \$\begingroup\$ Why do you say it doesn't work with all positive integers? It works fine up to a million, and I see no reason why it'd stop working. \$\endgroup\$
    – Grimmy
    Commented Mar 8, 2019 at 16:02
  • \$\begingroup\$ codegolf.stackexchange.com/questions/181128/… "...any positive integer can be tested". Example where it wont work anymore: 2096127. This is due to that i only test the first 11 of the OEIS A129868 Numbers. could do more maybe, but it will not work vor ANY positive integer i think \$\endgroup\$
    – Serverfrog
    Commented Mar 8, 2019 at 16:09
  • 2
    \$\begingroup\$ Okay, so this doesn't actually answer the problem, you should edit it to make it work or delete it. Marking an answer as non-competing isn't a free pass, it should still be valid. \$\endgroup\$
    – Grimmy
    Commented Mar 8, 2019 at 16:13
  • \$\begingroup\$ It's funny how you first say everything is fine, and after i point you where the OP post that limit (that wasn't really defined before this answer was posted) you aggressively force to make it work now or deleting it without seemingly to know the timeline between answer and the point it was invalid :P \$\endgroup\$
    – Serverfrog
    Commented Mar 8, 2019 at 16:21
  • 1
    \$\begingroup\$ Currently it is unkown if this or any other answer is valid because OP don't really defined what he meant with any positive integer as a integer could be 2 things, one has a maximum value the other not. And after my last change it is working with the 32-bit signed Integer \$\endgroup\$
    – Serverfrog
    Commented Mar 8, 2019 at 16:41
0
\$\begingroup\$

Swift, 161 bytes

func c(a:Int)->Int{
    let b=String(a,radix:2)
    let f=b.firstIndex(of:"0")
    return a>=0 && f==b.lastIndex(of:"0") && f?.encodedOffset==b.count/2 ? 1 : 0
}

Try it online!

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

Perl 5 -p, 32 bytes

$_=(sprintf'%b',$_)=~/^(1*)0\1$/

Try it online!

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

Java, 201 bytes (compilable)

Hmm, a different approach in java, runnable on commandline (so there is much to cut out).

class Z{public static void main(String[]a{a=Integer.toBinaryString(Integer.valueOf(a[0])).split("0");System.out.println(a.length==0?1:(a.length!=2?1:a[0].length()-a[1].length()+a.length-2)==0?1:0);}}

prints 0 for non cyclops and 1 for cyclops numbers.

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to PPCG! I think you can remove public . Is there a ) missing after String[]a? a.length==0 -> a.length < 1, again later (maybe?). \$\endgroup\$
    – Stephen
    Commented Mar 11, 2019 at 18:54
0
\$\begingroup\$

Factor, 69 bytes

: f ( n -- ? ) >bin [ dup reverse = ] [ [ 48 = ] count 1 = ] bi and ;

Try it online!

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

PHP

The shortest code should be this:

preg_match('`^(?<l>1*)0\k{l}$`', decbin($n));

Here the script to test it:

$inputs = [
    0,
    1,
    5,
    9,
    10,
    27,
    85,
    101,
    111,
    119,
];


function isCyclop($n) {
    return preg_match('`^(?<l>1*)0\k{l}$`', decbin($n));
}

foreach ($inputs as $input) {
    echo "$input : ".(isCyclop($input)?'truthy':'falsy').PHP_EOL;
}
\$\endgroup\$
0
\$\begingroup\$

Java, 96 bytes

n->{String[]a=Integer.toBinaryString(n).split("0");return n==0||a.length==2&&a[0].equals(a[1]);}

Try it online!

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

Perl 6 (26 bytes)

{so .base(2)~~/^(1*)0$0$/}
\$\endgroup\$
1
  • \$\begingroup\$ You can remove the so, since the output can just be truthy/falsey, but it ends up the same as my answer \$\endgroup\$
    – Jo King
    Commented Mar 19, 2019 at 2:17
0
\$\begingroup\$

Pip, 87 bytes

a:qTa<=1{((a%2)=0)?(x:"0".x)(x:"1".x)a//:2}1=a?x:"1".xsc:x^"0"x=0|#x%2=1&(c0)=(c1)&#c=2

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Try a simpler approach next time. \$\endgroup\$
    – Razetime
    Commented Sep 12, 2020 at 10:48
0
\$\begingroup\$

Pip, 15 bytes

YTBa^0 2=#y&$=y

Try it online!

A much shorter pip solution.

Explanation

YTBa^0 2=#y&$=y a → input integer
YTBa^0         Yank binary representation of a into var y, split on 0's
       2=#y     Length of y = 2?
           &$=y and all items of y are equal?
                Implicit output of boolean
\$\endgroup\$
0
\$\begingroup\$

><>, 45 bytes

!v:2%$2,:1%-:1(?!
1\~
*>l2=?vl3=?0${*
$0=*n;>

Try it online!

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

Java 8, 66 69 bytes

-3 bytes thanks to @ceilingcat !

n->{int r=0,i=0;for(;i<16;)r+=n-~(1<<i)==1<<i+++i?1:0;return r>0;}

Try it online!

Don't hesitate to ask if this needs any explanation!


Alternative solution really close using Streams (70 bytes) :

n->"0123456789:;<=>?".chars().anyMatch(e->n-~(1<<e-48)==1<<2*(e-48)+1)
\$\endgroup\$
0
0
\$\begingroup\$

Thunno 2, 8 bytes

ḃDḲ=s0c=

Attempt This Online!

Port of emirps's Vyxal answer.

Explanation

ḃDḲ=s0c=  # Implicit input
ḃD        # Convert to binary; duplicate
  Ḳ=s     # Check if palindrome; swap
     0c=  # Equals the count of 0s?
          # Implicit output
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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