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

62 Answers 62

24
\$\begingroup\$

Python 2, 30 bytes

lambda n:(2*n^2*n+3)**2==8*n+9

Try it online!

Note that 2*n^2*n+3 is the bitwise xor of 2*n and 2*n+3, because that's Python's operator precedence.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Would it be acceptable to return lambda n:(2*n^2*n+3)**2-8*n-9, with a return value of 0 for cyclops numbers? \$\endgroup\$ Mar 8, 2019 at 9:14
  • 2
    \$\begingroup\$ This yields TRUE for n = -1 \$\endgroup\$ Mar 8, 2019 at 11:28
  • 3
    \$\begingroup\$ @user2390246 this problem is clearly not intended for negatives- if it was, all accepting solutions would need to be negatives (and the way that python implements integers would mean that no solutions should accept in python) \$\endgroup\$ Mar 8, 2019 at 20:13
  • 3
    \$\begingroup\$ @SolomonUcko negative numbers are typically stored in twos complement representation. Consider first fixed size integers (32 bit for example). Among other properties, TCR requires that the MSB is 1 in negative numbers, and 0 in positive. This would immediately require that all positive outputs are false. In python we have even more of a problem though. Negative numbers implicitly have an infinite sequence of 1s in the most significant direction. Good luck trying to find the middle of that \$\endgroup\$ Mar 8, 2019 at 21:01
  • 2
    \$\begingroup\$ @user2390246 The problem was since edited to clarify that our code doesn't need to work for negatives. It could be handled for 2 bytes by appending >1. \$\endgroup\$
    – xnor
    Mar 9, 2019 at 3:36
19
\$\begingroup\$

x86 Machine Code, 17 bytes

8D 47 01 31 F8 89 C2 F7 D2 0F AF C2 8D 44 78 02 C3

The above bytes define a function that accepts a 32-bit integer input value (in the EDI register for this example, following a common System V calling convention, but you could actually pick pretty much any input register you wanted without affecting the size of the resulting code), and returns a result (in the EAX register) indicating whether the input value is a Cyclops number.

The input is assumed to be an unsigned integer, since the challenge rules state that we can ignore negative values.

The decision logic is borrowed from Neil's answer: since a Cyclops number has the form \$ n = (2 ^ k + 1) (2 ^ { k - 1 } - 1) \$, we can use a series of bit-twiddling operations to check the input.

Note: The return value is truthy/falsy, but the semantics are reversed, such that the function will return falsy for a Cyclops number. I claim this is legal because machine code doesn't have "specifications for truthy/falsy", which is the requirement in the question. (See below for an alternative version if you think this is cheating.)

In assembly language mnemonics, this is:

; EDI = input value
; EAX = output value (0 == Cyclops number)
8D 47 01           lea    eax, [edi + 1]          ; \ EAX = ((EDI + 1) ^ EDI)
31 F8              xor    eax, edi                ; /
89 C2              mov    edx, eax                ; \ EDX = ~EAX
F7 D2              not    edx                     ; /
0F AF C2           imul   eax, edx                ; EAX *= EDX
8D 44 78 02        lea    eax, [eax + edi*2 + 2]  ; EAX  = (EAX + (EDI * 2) + 2)
C3                 ret                            ; return, with EAX == 0 for Cyclops number

Try it online!


As promised, if you think it's cheating to invert the semantics of truthy/falsy even in machine code where there are no real standards or conventions, then add three more bytes, for a total of 21 bytes:

; EDI = input value
; AL  = output value (1 == Cyclops number)
8D 47 01           lea    eax, [edi + 1]          ; \ EAX = ((EDI + 1) ^ EDI)
31 F8              xor    eax, edi                ; /
89 C2              mov    edx, eax                ; \ EDX = ~EAX
F7 D2              not    edx                     ; /
0F AF C2           imul   eax, edx                ; EAX *= EDX
8D 44 78 01        lea    eax, [eax + edi*2 + 1]  ; EAX  = (EAX + (EDI * 2) + 1)
40                 inc    eax                     ; EAX += 1
0F 94 C0           setz   al                      ; AL = ((EAX == 0) ? 1 : 0)
C3                 ret                            ; return, with AL == 1 for Cyclops number

The first half of this code is the same as the original (down through the imul instruction). The lea is almost the same, but instead of adding a constant 2, it only adds a constant 1. That's because the following inc instruction increments the value in the EAX register by 1 in order to set the flags. If the "zero" flag is set, the setz instruction will set AL to 1; otherwise, AL will be set to 0. This is the standard way that a C compiler will generate machine code to return a bool.

Changing the constant added in the lea instruction obviously doesn't change the code size, and the inc instruction is very small (only 1 byte), but the setz instruction is a rather whopping 3 bytes. Unfortunately, I can't think of any shorter way of writing it.

\$\endgroup\$
7
  • 4
    \$\begingroup\$ This is so fast, I think it deserves to be shown off by testing all numbers up to a large value: Try it online! \$\endgroup\$
    – Deadcode
    Mar 9, 2019 at 5:24
  • 2
    \$\begingroup\$ It should actually be even faster, @Deadcode. :-) Demonstrating it with inline assembly adds some overhead, but my old trick of jumping to a string of bytes (see e.g., this answer) has stopped working with TIO's compiler, and writing code to print the results directly in assembly is too much work to bother with. This is one of those unusual cases, though, where optimizing for size is not at odds with optimizing for speed. This is pretty much the way you'd write the code in asm if you were going for speed over size. \$\endgroup\$ Mar 9, 2019 at 5:36
  • 2
    \$\begingroup\$ By consensus, it not unacceptable to return a status flag in an asm submission codegolf.stackexchange.com/a/165020/84624 and stackoverflow.com/questions/48381234/…. If so, you could - 3 from your second answer. \$\endgroup\$
    – 640KB
    Mar 10, 2019 at 22:01
  • \$\begingroup\$ Here's a clean way to return boolean results efficiently from inline asm - and the result \$\endgroup\$
    – Deadcode
    Mar 11, 2021 at 18:31
  • \$\begingroup\$ mul edx or imul edx saves 1 byte over imul eax, edx, and produces the same result in EAX. (It clobbers EDX but we're done with it at that point.) This is a size vs. speed tradeoff: one-operand mul/imul is 3 uops for 32-bit operand-size on Intel. \$\endgroup\$ Feb 24, 2022 at 2:05
12
\$\begingroup\$

Regex (ECMAScript), 60 58 57 60 58 bytes

The input \$n\$ is in unary, as the length of a string of xs.

SPOILER WARNING: For the square root, this regex uses a variant of the generalized multiplication algorithm, which is non-obvious and could be a rewarding puzzle to work out on your own. For more information, see an explanation for this form of the algorithm in Find a Rocco number.

-2 bytes by allowing backtracking in the search for \$z\$
-1 byte thanks to Grimmy, by searching for \$z\$ from smallest to largest instead of vice versa
+3 bytes to handle zero
-2 bytes by moving the square root capture outside the lookahead

This works by finding \$z\$, a perfect square power of 2 for which \$n=2(n-z)+\sqrt{z}+1\$. Only the largest perfect square power of 2 not exceeding \$n\$ can satisfy this, but due to a golf optimization, the regex tries all of them starting with the smallest. Since each one corresponds to a cyclops number, only the largest one can result in a match.

^(x*)(?!(x(xx)+)\2*$)(x(x*))(?=(?=(\4*)\5+$)\4*$\6)x\1$|^$

Try it online!

^                 # N = tail
(x*)              # tail = Z, with the smallest value that satisfies the following
                  # assertions (which is no different from the largest value that
                  # would satisfy them, since no more than one value can do so);
                  # \1 = N - Z
                   
(?!(x(xx)+)\2*$)  # Assert Z is a power of 2

# Assert Z is a perfect square, and take its square root
(x(x*))           # \4 = square root of Z; \5 = \4 - 1; tail = N - \1 - \4
(?=(\4*)\5+$)     # iff \4*\4 == Z, then the first match here must result in \6==0
(?=\4*$\6)        # test for divisibility by \4 and for \6==0 simultaneously

# Assert that N == \1*2 + \4 + 1. If this fails, then due to a golf optimization,
# the regex engine will backtrack into the capturing of \4, and try all smaller
# values to see if they are the square root of Z; all of these smaller values will
# fail, because the \4*\4==Z multiplication test only matches for one unique value
# of \4.
x\1$

|^$               # Match N==0, because the above algorithm does not
\$\endgroup\$
3
  • \$\begingroup\$ OP clarified that 0 should be truthy, so this currently doesn't solve the challenge. \$\endgroup\$
    – Grimmy
    Mar 8, 2019 at 16:17
  • 1
    \$\begingroup\$ Isn't a simple ^(1*)0\1$ enough? \$\endgroup\$
    – Gymhgy
    Mar 8, 2019 at 16:32
  • 6
    \$\begingroup\$ @EmbodimentofIgnorance Only if the input were in binary. That would trivialize a lot of challenges; consistently using unary input where applicable is much more interesting. \$\endgroup\$
    – Deadcode
    Mar 8, 2019 at 16:58
11
\$\begingroup\$

Japt, 8 bytes

1¥¢q0 äè

Run it online

Explanation:

1¥¢q0 äè   
                                                              119
  ¢          // Convert the input into a binary string        "1110111"
   q0        // Split the string on "0"                       ["111","111"]
      ä      // Reduce each item by:                            a     b
       è     //   Seeing how many times a is found in b       [1]
 1¥          // == 1; See if the result equals 1              True                                         

The idea is to split the binary string at 0, which would yield two items if there is only one 0. Then we see if the first item matches the second to ensure it is palindromic. If the binary string contains multiple 0s, then the reduce would return a multi-item array and that would fail the ==1 condition. If the binary string does contain one 0, but is not palindromic, äè will return 0 because b contains 0 matches of a.

\$\endgroup\$
10
  • 1
    \$\begingroup\$ Took my pre-caffeinated brain a couple of seconds to see what was happening here! Nicely done. should also work. \$\endgroup\$
    – Shaggy
    Mar 8, 2019 at 9:55
  • 1
    \$\begingroup\$ I don't know Japt, but if I understand correctly it does the following: ¤ = convert to binary; q0 = split on 0s; äè I'm not entirely sure..; and the flag -N converts lists to NaN, but leaves 0 and 1 the same. For the äè part I can see that 119 is [111,111] after the split, which äè changes to 1; and 85 is [1,1,1,1] after the split, which äè changes to [1,1,1]. Could you explain how .ä("è") works? \$\endgroup\$ Mar 8, 2019 at 14:36
  • 2
    \$\begingroup\$ @KevinCruijssen I added an explanation. I hope that helps. \$\endgroup\$
    – Oliver
    Mar 8, 2019 at 15:04
  • 1
    \$\begingroup\$ Is NaN falsey in Japt? (i.e. if you perform an if-else with that as the condition does the if get executed? "Truthy/falsy output must meet the used language's specifications for truthy/falsy") Also 2 yields 2 which I doubt is falsey (but might be if Japt is like 05AB1E). \$\endgroup\$ Mar 8, 2019 at 18:16
  • 1
    \$\begingroup\$ JS assumes that any integer other than 0 is considered truthy... however, if 2 is returning 2 as truthy, then this submission may need to be reworked. \$\endgroup\$ Mar 9, 2019 at 17:26
9
\$\begingroup\$

JavaScript (Node.js), 20 bytes

p=>~p==(p^=p+1)*~p/2

Try it online!

Maybe this is correct, maybe.

Thanks Grimy, 1 byte saved.


JavaScript (Node.js), 32 bytes

f=(p,q)=>p&1?f(p/2,q+q|2):!(p^q)

Try it online!


JavaScript (Node.js), 34 bytes

p=>/^(1*)0\1$/.test(p.toString(2))

Try it online!

\$\endgroup\$
6
  • \$\begingroup\$ 20 \$\endgroup\$
    – Grimmy
    Mar 8, 2019 at 15:26
  • \$\begingroup\$ Test, not match \$\endgroup\$
    – edc65
    Mar 9, 2019 at 17:11
  • 1
    \$\begingroup\$ @edc65 Did you find out any failed testcase? \$\endgroup\$
    – tsh
    Mar 11, 2019 at 1:53
  • 2
    \$\begingroup\$ @tsh .test not .match \$\endgroup\$
    – ASCII-only
    Mar 11, 2019 at 6:50
  • \$\begingroup\$ @ASCII-only Wow, sound reasonable... How can you read this? \$\endgroup\$
    – tsh
    Mar 11, 2019 at 7:22
7
\$\begingroup\$

Perl 6, 23 bytes

{.base(2)~~/^(1*)0$0$/}

Try it online!

Regex based solution

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

Japt, 25 19 10 9 bytes

¢êÅ©1¶¢èT

Thanks to @Shaggy for -1 byte

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 9 bytes \$\endgroup\$
    – Shaggy
    Mar 8, 2019 at 7:54
  • \$\begingroup\$ 8 bytes \$\endgroup\$
    – Shaggy
    Nov 14, 2023 at 10:27
7
\$\begingroup\$

Mathematica (Wolfram language), 32 31 bytes

1 byte saved thanks to J42161217!

OddQ@Log2[#+Floor@Sqrt[#/2]+2]&

Try it online!

Pure function taking an integer as input and returning True or False. Based on the fact (fun to prove!) that a number n is Cyclops if and only if n plus the square root of n/2 plus 2 rounds down to an odd power of 2. (One can replace Floor by either Ceiling or Round as long as one also replaces +2 by +1.) Returns True on input 0.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ you can save 1 byte by using Log2[#+Floor@Sqrt... \$\endgroup\$
    – ZaMoC
    Mar 8, 2019 at 20:09
  • \$\begingroup\$ and 1 more using √() instead of Sqrt[] \$\endgroup\$
    – att
    Apr 20, 2019 at 20:16
  • \$\begingroup\$ Is the byte count correct? TIO gives 32 bytes for the current program. \$\endgroup\$
    – mbomb007
    Aug 2, 2019 at 21:51
  • \$\begingroup\$ @mbomb007 aha, the TIO didn't incorporate J42161217's 1-byte savings. Fixed. \$\endgroup\$ Aug 3, 2019 at 1:45
  • \$\begingroup\$ Was there a reason you didn't use what attinat suggested? \$\endgroup\$
    – mbomb007
    Aug 3, 2019 at 3:03
6
\$\begingroup\$

Ruby, 24 bytes

->x{x+x+2==(1+x^=x+1)*x}

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Nice. There might be a shorter version with different assignments and precedence, but I couldn't find any. \$\endgroup\$ Mar 8, 2019 at 16:49
5
+200
\$\begingroup\$

Japt, 8 bytes

¢ðT ¥¢Êz

Thanks to Luis felipe de Jesus Munoz for fixing my submission!

Try it Online!

Old regex-based solution, 15 bytes

¤f/^(1*)0\1$/ l

Returns 1 for true, 0 for false.

Try it Online!

\$\endgroup\$
7
  • \$\begingroup\$ Well played, I should really learn regular expressions sometime. :) +1 \$\endgroup\$
    – Quintec
    Mar 8, 2019 at 3:01
  • 1
    \$\begingroup\$ @Quintec Regex is awesome :) \$\endgroup\$
    – Gymhgy
    Mar 8, 2019 at 3:02
  • \$\begingroup\$ Update: found shorter way :) \$\endgroup\$
    – Quintec
    Mar 8, 2019 at 3:11
  • 1
    \$\begingroup\$ 8 bytes \$\endgroup\$ Mar 8, 2019 at 11:54
  • 1
    \$\begingroup\$ @LuisfelipeDejesusMunoz Thanks, that's a really nice use of the == operator! \$\endgroup\$
    – Gymhgy
    Mar 8, 2019 at 16:35
5
\$\begingroup\$

C (gcc), 26 bytes

f(n){n=~n==(n^=-~n)*~n/2;}

Try it online!

Port of Neil's answer. Relies on implementation-defined ordering of operations.

C++ (clang), 38 bytes

int f(int n){return~n==(n^=-~n)*~n/2;}

Try it online!

Can't omit the types in C++, can’t omit the return in clang, otherwise identical.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I would prefer that C++ answers be differentiated from C answers by using return instead of the fragile and platform-dependent implicit accumulator return value exploit. \$\endgroup\$
    – Deadcode
    Mar 8, 2019 at 17:20
  • 3
    \$\begingroup\$ I would also like the rules to require standard-compliance, but they don’t, so not making use of this would just be bad golf. C++ (clang) requires the return, making this 38 bytes. \$\endgroup\$
    – Grimmy
    Mar 8, 2019 at 17:27
  • \$\begingroup\$ Then you can get around this by having C (gcc) and C++ (clang) in your answer instead of C (gcc) and C++ (gcc). I've now done that. \$\endgroup\$
    – Deadcode
    Mar 8, 2019 at 17:33
5
\$\begingroup\$

Jelly,  8  7 bytes

-1 thanks to Erik the Outgolfer (use isPalindrome built-in, ŒḂ, instead of ⁼Ṛ$)

B¬ŒḂ⁼SƊ

A monadic Link accepting an integer which yields 1 (truthy) or 0 (falsey).

Try it online!

How?

B¬ŒḂ⁼SƊ - Link: integer             e.g. 1    9          13         119
B       - to base 2                      [1]  [1,0,0,1]  [1,1,0,1]  [1,1,1,0,1,1,1]
 ¬      - logical NOT (vectorises)       [0]  [0,1,1,0]  [0,0,1,0]  [0,0,0,1,0,0,0]
      Ɗ - last three links as a monad:
  ŒḂ    -   is a palindrome?             1    1          0          1
     S  -   sum                          0    2          1          1
    ⁼   -   equal?                       0    0          0          1
\$\endgroup\$
3
  • \$\begingroup\$ Looks like you actually had the clever idea before me, but its cleverness isn't obvious (Bċ0⁼1ȧŒḂ is also 8 bytes), ⁼Ṛ$ is the same as ŒḂ for -1. Also, you don't need to handle negative numbers. \$\endgroup\$ Mar 8, 2019 at 17:35
  • \$\begingroup\$ Thanks Erik, the is palindrome built-in slipped my mind for some reason! \$\endgroup\$ Mar 8, 2019 at 18:11
  • \$\begingroup\$ Actually, you can also use ṚƑ in its place nowadays, so you might want to remember it like that (the most important Ƒs). \$\endgroup\$ Mar 8, 2019 at 20:23
5
\$\begingroup\$

Brachylog, 8 bytes

ḃD↔Dḍ×ᵐ≠

This is a predicate that succeeds if its input is a Cyclops number and fails if its input is not a Cyclops number. Success/failure is the most fundamental truthy/falsey concept in Brachylog.

Try it online! Or, find all truthy outputs up to 10000.

Explanation

          Input is an integer
ḃ         Get its binary representation, a list of 1's and 0's
 D        Call that list D
  ↔       When reversed...
   D      It's the same value D
    ḍ     Dichotomize: break the list into two halves
          One of these halves should be all 1's; the other should contain the 0
     ×ᵐ   Get the product of each half
       ≠  Verify that the two products are not equal

This succeeds only when given a Cyclops number, because:

  • If the binary representation isn't a palindrome, D↔D will fail; in what follows, we can assume it's a palindrome.
  • If there is more than one zero, both halves will contain at least one zero. So the products will both be zero, and ×ᵐ≠ will fail.
  • If there is no zero, both halves will contain only ones. So the products will both be one, and ×ᵐ≠ will fail.
  • That leaves the case where there is exactly one zero; since we already know we have a palindrome, this must be the central bit. It will appear in one half, causing that half's product to be zero; the other half will contain all ones, so its product will be one. Then we have 1 ≠ 0, ×ᵐ≠ succeeds, and the whole predicate succeeds.
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 8 (or 9) bytes

bD0¢sÂQ*

Try it online or verify all test cases.

Returns 1 if truthy; 0 or any positive integer other than 1 as falsey. In 05AB1E only 1 is truthy and everything else is falsey, but I'm not sure if this is an allowed output, or if the output should be two consistent and unique values. If the second, a trailing Θ can be added so all outputs other than 1 become 0:

Try it online or verify all test cases.

Explanation:

b     # Convert the (implicit) input-integer to a binary-string
 D    # Duplicate it
  0¢  # Count the amount of 0s
 s    # Swap to get the binary again
  ÂQ  # Check if it's a palindrome
 *    # Multiply both (and output implicitly)

  Θ   # Optionally: check if this is truthy (==1),
      # resulting in truthy (1) or falsey (0)

An arithmetic approach would be 10 bytes:

LoD<s·>*Iå

Try it online or verify all test cases.

Explanation:

Creates a sequences using the algorithm \$a(n) = (2^n-1)*(2*2^n+1)\$, and then checks if the input-integer is in this sequence.

L        # Create a list in the range [1, (implicit) input-integer]
 o       # For each integer in the list, take 2 to the power this integer
  D<     # Create a copy, and decrease each value by 1
  s·     # Get the copied list again, and double each value
    >    # Then increase each value by 1
  *      # Multiply the numbers at the same indices in both lists
     Iå  # Check if the input-integer is in this list
         # (and output the result implicitly)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Having 1 as truthy and all other numbers as falsy is acceptable for this challenge, since other languages (e.g. C and TI-BASIC) have similar truthy/falsy definitions (0/non-zero for both). As long as what's considered truthy or falsy matches with the language's specifcations, then it's fair game. \$\endgroup\$ Mar 8, 2019 at 14:13
4
\$\begingroup\$

Haskell, 32 bytes

f n=or[2*4^k-2^k-1==n|k<-[0..n]]

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Regex (ECMAScript), 53 47 bytes

-6 bytes thanks to both Deadcode and Grimy

^((?=(x*?)(\2((x+)x(?=\5$))+x$))(?!\2{6})\3x)*$

Try it online!

explanation by Deadcode

This regex takes its input in unary, as a sequence of x characters in which the length represents the number. Properties of its binary representation are handled indirectly, by doing math on its unary representation.

It works by looping the following operation, which is a subtraction at every step:

  • Trim the leftmost and rightmost 1 from the number's binary representation, if the 1 being trimmed from the left is immediately followed by another 1 or the full number is 101

If and only if the initial input was a cyclops number, it will be the next smallest cyclops number at every step of the loop, e.g. 1110111110111010. The regex matches if and only if the value is 0 at the end.

^                              # tail = N, the input number
(                              # While tail is odd and is >= 3, and has a leftmost "11"
                               # in its binary representation, trim off the leftmost and
                               # rightmost 1 from its binary representation. If it is a
                               # cyclops number, it will be the next smaller cyclops
                               # number on the next iteration.
    (?=
        (x*?)                  # Find the smallest \2 such that tail - 2*\2 satisfies the
                               # following assertion, i.e. that tail - 2*\2 = 2^k-1
                               # where k >= 2. In other words, assert tail is odd, and
                               # let \2 = (tail - 2^k + 1) / 2, where 2^k-1 has the
                               # largest value of k such that 2^k-1 <= tail. If tail is
                               # a cyclops number, then \2-1 will be the next smallest
                               # cyclops number;
                               # tail -= \2
        (                      # \3 = tool to make tail-1 = \2-1 (will be used later)
            \2                 # tail -= \2
            ((x+)x(?=\5$))+x$  # Assert tail = 2^k-1 where k >= 2
        )
    )
    (?!\2{6})                  # Assert that tail < 6*\2, which is a way of asserting
                               # that in tail's binary representation, the next 1 to the
                               # right of the one we'll be trimming is also 1. This
                               # prevents for example, trimming 10110111 -> 11011, which
                               # would give us a false positive. As a worst case example,
                               # let's say tail = 0b101111111111111111111111111111111111
                               # this would give us:
                               #             \2 = 0b001000000000000000000000000000000000
                               #           6*\2 = 0b110000000000000000000000000000000000
                               # So it's not quite exactly asserting that tail begins
                               # with "11" in its binary representation, and would
                               # continue looping in that case, but that doesn't matter
                               # because that number could never be trimmed into a
                               # cyclops number anyway. With any smaller value of tail
                               # that passes the other tests, we'd have:
                               #           tail = 0b101111111111111111111111111111111101
                               #             \2 = 0b000111111111111111111111111111111111
                               #           6*\2 = 0b101111111111111111111111111111111010
                               # and in this case tail >= 6*\2, so it stops the loop.
                               # On the other end of the scale is 0b101, which needs to
                               # be trimmed even though it doesn't have two leftmost 1
                               # bits in a row. And indeed, that works:
                               #           tail = 0b101
                               #             \2 = 0b001
                               #           6*\2 = 0b110
                               # In this case, it is just barely true that tail < 6*\2
                               # and the loop is allowed to continue one more step.
    \3x                        # tail = \2-1
)*
$                              # Assert that tail = 0 after the loop finished. This will
                               # be true iff N is a cyclops number. If it fails to match,
                               # backtracking cannot make it match, because everything in
                               # the loop is atomic.
\$\endgroup\$
1
  • \$\begingroup\$ In the course of fully commenting and proving your regex (not quite finished yet), I got it down to 50 bytes: ^((?=(x(x*?))(\3((x+)(?=\6$))+xx$))(?!\2{6})x\4)*$ (Try it online!) \$\endgroup\$
    – Deadcode
    Mar 9, 2019 at 5:19
3
\$\begingroup\$

Batch, 39 37 bytes

@cmd/cset/a"m=%1^-~%1,!(m/2*(m+2)-%1)

Explanation: A Cyclops number has the form \$ n = (2 ^ k + 1) (2 ^ { k - 1 } - 1) \$. The bitwise XOR then results in \$ m = 2 ^ k - 1 \$ from which we can recalculate \$ n = \lfloor \frac m 2 \rfloor ( m + 2 ) \$. This can then be used to test whether \$ n \$ was a Cyclops number.

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

Ruby, 27 24 bytes

Convert to binary and check with a regex. Returns 0 if true, nil if false.

-3 bytes thanks to GB.

->n{"%b"%n=~/^(1*)0\1$/}

Try it online!

For two bytes more, there's a direct port of the Python solution:

->n{(2*n^2*n+3)**2==8*n+9}
\$\endgroup\$
0
3
\$\begingroup\$

Excel, 97 63 Bytes

=A1=2*4^(ROUND(LOG(A1,4),0))-2^(ROUND(LOG(A1,4),0))-1

Calculates 2 numbers:

Twice the nearest Power of 4
>Num|Binary|2*Power4|Binary
> 1| 1| 2* 1= 2| 10
> 2| 10| 2* 4= 8| 1000
> 4| 100| 2* 4= 8| 1000
> 20| 10100| 2*16=32|100000

 

1 Plus the square root of the nearest Power of 4
>Num|Binary|1+√Power4|Binary
> 1| 1|1+ √1= 2| 10
> 2| 10|1+ √4= 3| 11
> 4| 100|1+ √4= 3| 11
> 20| 10100|1+ √16= 5| 101

Then subtract the second number from the first:

>Num|Binary|2*Power4|Binary|1+√Power4|Binary|a-b|Binary
> 1| 1| 2* 1= 2| 10|1+ √1= 2| 10| 0| 0
> 2| 10| 2* 4= 8| 1000|1+ √4= 3| 11| 5| 101
> 4| 100| 2* 4= 8| 1000|1+ √4= 3| 11| 5| 101
> 20| 10100| 2*16=32|100000|1+ √16= 5| 101| 27| 11011

And compare this result with the original number

Old Method

=DEC2BIN(A1)=REPLACE(REPT("1",1+2*INT(IFERROR(LOG(A1,2),0)/2)),1+IFERROR(LOG(A1,2),0)/2,1,"0")

Start with the Log-base-2 of A1 and round it down the nearest even number, then add 1.

Next create a string of that many "1"s, and replace the middle character with a "0" to create a Cyclops number with a binary length that is always odd, and the same as or 1 less than the binary length of A1

Then, compare it with the Binary representation of A1

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

R, 37 33 bytes

(x=scan())%in%(2*4^(n=0:x)-2^n-1)

Try it online!

R doesn't have a built-in for converting to binary, so I simply used one of the formulae from OEIS to calculate a list of terms from the sequence.

n<-0:x generates a generous list of starting values. 2*4^(n<-0:x^2)-2^n-1) is the formula from OEIS, and then it checks whether the input appears in that sequence using %in%.

-2 bytes by not having to handle negative inputs. -2 bytes by remembering I can change <- to =.

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

C (gcc),  29 28  27 bytes

Saved 1 byte thanks to @ceilingcat

A port of the 21-byte JS answer by @tsh.

f(p){p=2*~p==~(p=-~p^p)*p;}

Try it online!

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

J, 22 19 17 15 14 bytes

-3 bytes thanks to BolceBussiere !

-4 bytes thanks to ngn!

-1 byte thanks to Traws!

J, 14 bytes

1=1#.(*:|.)@#:

Try it online!

\$\endgroup\$
10
  • 1
    \$\begingroup\$ #=1++/­­­­­­­ \$\endgroup\$
    – ngn
    Apr 12, 2019 at 0:48
  • 1
    \$\begingroup\$ (#=1++/)@(*|.)@#: \$\endgroup\$
    – ngn
    Apr 12, 2019 at 1:01
  • 1
    \$\begingroup\$ 1=1#.1-(*|.)@#: \$\endgroup\$
    – ngn
    Apr 12, 2019 at 14:25
  • 1
    \$\begingroup\$ i don't know enough j to use it but it's fun to learn from other people's code by trying to shorten it \$\endgroup\$
    – ngn
    Apr 12, 2019 at 17:49
  • 1
    \$\begingroup\$ -1 byte 1=1#.(*:|.)@#: \$\endgroup\$
    – Traws
    May 25, 2019 at 15:03
2
\$\begingroup\$

Jelly, 9 bytes

BŒḂaB¬S=1

Try it online!

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

Attache, 22 bytes

{Flip@_=_∧1=0~_}@Bin

Try it online!

Alternatives

27 bytes: {BitXor[2*_,2*_+3]^2=8*_+9}

27 bytes: {BitXor@@(2*_+0'3)^2=8*_+9}

27 bytes: {Palindromic@_∧1=0~_}@Bin

28 bytes: {BitXor[...2*_+0'3]^2=8*_+9}

28 bytes: {BitXor[…2*_+0'3]^2=8*_+9}

28 bytes: {Same@@Bisect@_∧1=0~_}@Bin

29 bytes: {_[#_/2|Floor]=0∧1=0~_}@Bin

30 bytes: Same@Bin@{_+2^Floor[Log2@_/2]}

30 bytes: {_[#_/2|Floor]=0and 1=0~_}@Bin

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

Retina 0.8.2, 38 37 bytes

.+
$*
+`^(1+)\1
$+0
10
1
^((1+)0\2)?$

Try it online! Link includes test cases. Edit: After clarification, previous solution didn't handle zero correctly. Explanation:

.+
$*

Convert from decimal to unary.

+`^(1+)\1
$+0
10
1

Convert from unary to binary, using the method from the Retina wiki.

^((1+)0\2)?$

Check for the same number of 1s before and after the 0, or an empty string (which is how the above conversion handles zero).

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

PHP, 74 bytes

function($x){return($c=strlen($a=decbin($x)))&1&&trim($a,1)===$a[$c/2|0];}

Try it online!

Or 61 bytes using Arrow syntax:

fn($x)=>($c=strlen($a=decbin($x)))&1&trim($a,1)===$a[$c/2|0];

Try it online!

Totally naïve non-mathematical approach, just strings.

function cyclops( $x ) {
    $b = decbin( $x );     // convert to binary string (non-zero left padded)
    $l = strlen( $b );     // length of binary string
    $t = trim( $b, 1 );    // remove all 1's on either side
    $m = $b[ $l / 2 |0 ];  // get the middle "bit" of the binary string
    return 
        $l & 1 &&          // is binary string an odd length?
        $t === $m;         // is the middle char of the binary string the same as
                           // string with left and right 1's removed? (can only be '0')
}

Or 60 bytes based on @Chronocidal's algorithm above.

function($x){return decbin($x)==str_pad(0,log($x,2)|1,1,2);}

Try it online!

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

Pyt, 17 bytes

ĐļƖĐ⁺2⇹^⇹ᵮ₂2⇹^-⁻=

Try it online!

No string manipulation required

ĐļƖĐ⁺2⇹^⇹₂2⇹^-⁻=
Instruction Stack Note
Đ n,n implicit input (n); duplicate onto stack
ļƖ n,k take base-2 log of n and cast to integer (k)
Đ n,k,k duplicate k on stack
n,k,k+1 increment top of stack
2⇹^ n,k,2^(k+1) raise 2 to the k+1 power
n,2^(k+1),k swap the top two items on the stack
ᵮ₂ n,2^(k+1),k/2 cast top of stack to float, then divide by 2
2⇹^ n,2^(k+1),2^(k/2) raise 2 to the k/2 power
-⁻ n,2^(k+1)-2^(k/2)-1 subtract and decrement
= True/False check for equality; implicit print
\$\endgroup\$
2
\$\begingroup\$

GolfScript, 31 35 26 bytes

-5 thanks to @DLosc

.!5*+2base..-1%=\{0=},,1=&

Link includes test cases.

Try it online!

Explanation

.!5*+2base..-1%=\{0=},,1=& | whole program
.!5*+                      | if the input is 0, make it 5 (smallest non-zero cyclops number)
     2base..               | push the binary version of the input
            -1%            | push the reversed version of the binary
               =           | is it equal to the non-reversed version?
                \{0=},,    | count the number of zeros 
                       1=  | is it equal to 1?
                         & | are both of the above checks true?
\$\endgroup\$
0
2
\$\begingroup\$

Thunno, \$ 8 \log_{256}(96) \approx \$ 6.58 bytes

bDZqs0c=

Attempt This Online!

Port of emirps's Vyxal answer.

Thunno P, \$ 9 \log_{256}(96) \approx \$ 7.41 bytes

bD0c1=sZq

Attempt This Online!

Port of Kevin Cruijssen's 05AB1E answer.

Explanation

bDZqs0c=  # Implicit input
bD        # Convert to binary and duplicate
  Zqs     # Check if it's a palindrome and swap
     0c=  # Is this equal to the count of 0s?
          # Implicit output
bD0c1=sZq  # Implicit input
bD         # Convert to binary and duplicate
  0c       # Count the number of "0"s in the string
    1=     # Is it equal to 1?
      sZq  # Swap and check if it's a palindrome
           # P flag multiplies them together
           # Implicit output
\$\endgroup\$
2
\$\begingroup\$

Vyxal, 8 bytes

Π:Ḃ=$0O=

Try it Online!

Different approach from the other Vyxal answer.

Π        # binary of input
  Ḃ=     # the equality of the reversed version of it to itself (0 for non palindrome, 1 for palindrome)
       = # is equal to
 :  $0O  # the count of 0s in itself

Could potentially be golfed

\$\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.