15
\$\begingroup\$

Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.


As soon as the Elves get bored with the last week's game, Bin comes up with a new game. The rules are similar, except the Elves are supposed to say the numbers that have its "left side" equal to its "right side" when written in binary. The "left" and "right" sides are defined as the first and last floor(k/2) bits, where k is the total number of bits.

Some examples:

  • The numbers that are just two copies joined together, such as 3 (11), 10 (1010), 15 (1111), ... are valid. This sequence is A020330.
  • 1 (1) is valid because its left and right parts are both empty, and as are 18 (10010) and 22 (10110) because their left and right are both 10.
  • 17 (10001) is not valid because 10 != 01.

You can use any of I/O methods:

  • Output the corresponding sequence infinitely
  • Given the index k (may be 1- or 0-indexed), output the kth number in the sequence
  • Given k, output the first k numbers of the sequence

Standard rules apply. The shortest code in bytes wins.

Test cases

1, 3, 5, 7, 10, 15, 18, 22, 27, 31, 36, 45, 54, 63, 68, 76, 85, 93, 102, 110,
119, 127, 136, 153, 170, 187, 204, 221, 238, 255, 264, 280, 297, 313, 330, 346,
363, 379, 396, 412, 429, 445, 462, 478, 495, 511, 528, 561, 594, 627, 660, 693,
726, 759, 792, 825, 858, 891, 924, 957, 990, 1023, 1040, 1072, 1105, 1137, 1170,
1202, 1235, 1267, 1300, 1332, 1365, 1397, 1430, 1462, 1495, 1527, 1560, 1592,
1625, 1657, 1690, 1722, 1755, 1787, 1820, 1852, 1885, 1917, 1950, 1982, 2015,
2047, ...

This sequence is not yet on OEIS.

\$\endgroup\$

21 Answers 21

5
\$\begingroup\$

Vyxal, 8 bytes

bI∩v≈A)ȯ

Try it Online!

       ȯ # First N integers
------)  # Where...
b        # Binary
 I       # Split into two halves
  ∩      # Transposed
     A   # Are all...
   v     # Pairs... 
    ≈    # Each all the same element?
\$\endgroup\$
5
\$\begingroup\$

Jelly, 10 bytes

1BŒHṛ"Ƒ/Ɗ#

Try it online!

Full program outputting the first k numbers in the sequence given k as a command-line argument. (It's worth noting that the less-fun 1BŒHZE€P$Ʋ# is shorter if 0 is included in the sequence.)

1       Ɗ#    Take the first k integers counting up from 1 which satisfy:
 B            Get the binary digits of the candidate
  ŒH          and split them in half, with the middle going to the left.
      Ƒ/      Is the left half unchanged by
    ṛ"        replacing its elements with corresponding elements of the right?
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 22 bytes

≔⍘⊕N²θI÷⍘ײΦθ⊖κ²⊕⁼§θ¹0

Try it online! Link is to verbose version of code. Outputs the nth value. Explanation:

≔⍘⊕N²θ

Convert n+1 to base 2 as a string.

I÷⍘ײΦθ⊖κ²⊕⁼§θ¹0

Delete the second character, duplicate the result, convert back from base 2, and halve the result if the second character was a 0.

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

Retina 0.8.2, 67 bytes

.+
$*11
+`(1+)\1
$+0
01
1
1(.)(.*)
1$+1$+$1
.0$|1$

1
01
+`10
011
1

Try it online! Link includes test cases. Explanation: Port of my Charcoal answer.

.+
$*11

Convert n to unary and add 1.

+`(1+)\1
$+0
01
1

Convert n+1 to binary.

1(.)(.*)
1$+1$+$1

Delete the second character of the binary string and duplicate the rest, then append the second character.

.0$|1$

If the original second character was a 0 then integer divide the binary number by 2. (Delete the original second character in any case.)

1
01
+`10
011
1

Convert from binary to decimal.

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

Python, 68 bytes

i=1
while[(k:=bin(i)[2:])[:(j:=len(k)//2)]==k[-j:]and print(i)]:i+=1

Attempt This Online!

Outputs the sequence indefinitely

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Full programs are fine! \$\endgroup\$ Dec 16, 2022 at 2:08
3
\$\begingroup\$

Jelly, 9 bytes

1BŒHw/ḂƲ#

A full program that accepts an integer, \$k\$, and prints a Jelly representation of the list of the first \$k\$ entries.

Try it online!

How?

1BŒHw/ḂƲ# - Main Link: integer, k
1       # - starting with j=1, count up and yield the first k integers for which:
       Ʋ  -   last four links as a monad - f(j):
 B        -     binary digits (j)
  ŒH      -     split into halves - e.g. [1,0,0,1,1] -> [[1,0,0],[1,1]]
     /    -     reduce by:
    w     -       first index of sublist (right) in (left)
                       0 : does not exist
                       1 : at the start -> a "left equals right" number
                       2 : exists but is the second sublist of that length
                       (other outputs not possible as only two sublists of that length exist)
      Ḃ   -     modulo two -> 1 if j is a "left equals right" number else 0
\$\endgroup\$
3
\$\begingroup\$

JavaScript (V8), 54 51 48 bytes

for(i=j=n=2;;i=i%~-n?i+2:n*=j^=3)print(i*n+i>>j)

Try it online!

Fast and shorter than RegEx solution and scan all

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

JavaScript (V8), 63 bytes (fast)

Prints the sequence infinitely.

for(i=k=n=1;k+=q=!(n&n+1);n+=2**(k-2*q>>1)+!(k*i++&!q))print(n)

Try it online!


JavaScript (V8), 56 bytes (slow)

Prints the sequence infinitely.

for(n=0;;)/^(.*).?\1$/.test((++n).toString(2))&&print(n)

Try it online!

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

Pyth, 22 bytes

.V1K.BbJ.:K/lK2IqhJeJb

Try it online!

Prints the sequence infinitely.

.V1                     # Run an infinite loop from 1 with b
   K.Bb                 # Initialize K as binary representation of b
       J.:K/lK2         # Get all substrings of len(K)/2 and set as J
                 hJ     # First value of J
                   eJ   # Last value of J
               Iq       # If equal
                     b  # Print b
\$\endgroup\$
2
\$\begingroup\$

><>, 72 bytes

1:&:1(?v:2%$2,:1%-20.
]l2%?~1\~l:2%+2,[r
=?v${=*>l1
?v\
&/v&oan:
0.>&1+0

Try it online!

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

Pip, 20 bytes

W UiI0=$@?R*RCHTBiPi

Try It Online! (Since DSO doesn't handle infinite loops well, this link outputs elements of the sequence less than 1000.)

Explanation

The fact that the CH builtin makes the first half shorter than the second half when chopping odd-length strings is a bit of a problem here.

W UiI0=$@?R*RCHTBiPi
                      i is 0 (implicit)
W                     Loop while
  Ui                  i incremented is truthy:
               TBi      Convert i to binary
             CH         Chop into two halves (if uneven, the second half is longer)
            R           Reverse (the potentially longer second element is now first)
          R*            Reverse each element
       $@?              Find index of first element in second element
    I0=                 If that index is zero:
                  Pi      Print i

Here are some worked examples to showcase the core logic. The @? operator gets the index of the first occurrence of its right argument as a substring of its left argument; if it is not a substring, the operator returns nil, here represented as ().

            i  10      13      18       21
          TB   1010    1101    10010    10101
        CH     [10;10] [11;01] [10;010] [10;101]
       R       [10;10] [01;11] [010;10] [101;10]
     R*        [01;01] [10;11] [010;01] [101;01]
  $@?          0       ()      0        1
0=             1       0       1        0
\$\endgroup\$
2
\$\begingroup\$

JavaScript (V8), 50 bytes

for(n=p=0;;n%(1<<p/2)^n>>-~p/2||print(n))p+=++n>>p

Try it online!

And this is 64 bytes in C.

Thanks jdt for -2 bytes on JS. Thanks l4m2, jdt for -3 bytes on C.

\$\endgroup\$
3
  • \$\begingroup\$ For C p can start at 1 and use argc save 1 byte \$\endgroup\$
    – l4m2
    Dec 18, 2022 at 16:00
  • \$\begingroup\$ 64 bytes \$\endgroup\$
    – jdt
    Dec 19, 2022 at 16:34
  • \$\begingroup\$ 50 bytes JavaScript \$\endgroup\$
    – jdt
    Dec 19, 2022 at 18:06
1
\$\begingroup\$

Pip, 43 bytes

W1{k:(l:TBo)^@#l//2I#l%2k@1PK0Ik@0=k@1PoUo}

Try It Online!

Outputs the sequence indefinitely. Won't run on the above link very well as DSO doesn't handle infinite loops well, use this to verify. Explanation:

k:(l:TBo)^@#l//2

Converts o to binary, splits into two.

I#l%2k@1PK0

If the length of the binary string is odd, remove the first element from the second half.

Ik@0=k@1PoUo

If both halves are the same, print o, then increment o

\$\endgroup\$
2
  • 1
    \$\begingroup\$ A few notes: 1) "Split in two" is a builtin, unary CH; 2) PK0 is equivalent to unary PO; 3) k@0=k@1 -> $=k, since k only has two elements. Also, don't forget you can use y as one of your variables to save a byte on assignment. \$\endgroup\$
    – DLosc
    Dec 19, 2022 at 20:55
  • \$\begingroup\$ @DLosc really good tip about using y, I can see that being useful a lot \$\endgroup\$
    – jezza_99
    Dec 19, 2022 at 22:59
1
\$\begingroup\$

Husk, 9 bytes

föΠFz=½ḋN

Try it online!

f           # filter
        N   # 1..infinity
 ö          # with composition of 4 functions:
       ḋ    #   get list of binary digits
      ½     #   split into list of two halves
   F        #   fold across this list
    z       #     zip the two halves together
     =      #       by equality
  Π         #   and get the product
\$\endgroup\$
1
\$\begingroup\$

Nibbles, 9.5 bytes (19 nibbles)

|,~~++!;``@$>>`\~@!
|                    # filter
 ,~                  # 1..infinity
   ~                 # for falsy results of:
    ++               #   sum of flattened list of
      !              #   zip together
                  !  #   getting abs differences
        ``@$         #     bits of input
       ;             #     (and save this)
                     #     with 
                 @   #     saved bits of input
              `\~    #     split into 2 chunks
            >>       #     discarding the first chunk    

enter image description here

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

Excel, 75 bytes

=LET(x,ROW(A:A),FILTER(x,LET(b,BASE(x,2),s,LEN(b)/2,LEFT(b,s)=RIGHT(b,s))))

enter image description here

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

Factor + lists.lazy, 46 bytes

[ 1 lfrom [ >bin halves swap tail? ] lfilter ]

Attempt This Online!

Returns an infinite lazy list of the sequence.

  • 1 lfrom the natural numbers
  • [ ... ] lfilter take the ones that...
  • >bin convert integer to binary string
  • halves split in half with the second half larger, e.g. "101" -> "1" "01"
  • swap tail? does the second half end with the first half?
\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 59 bytes

The basic idea is is(n)=my(v=binary(n)); v[1..#v\2]==v[(#v+3)\2..#v].

for(n=1,oo,v=binary(n);v[1..#v\2]==v[(#v+3)\2..#v]&&print(n))
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 9 bytes

∞ʒ2в2äøøË

Try it online!

Outputs the infinite sequence.

  • -6, -9 thanks to Steffan
  • -1 thanks to Kevin Cruijssen

Explanation:

∞ʒ2в2äøøË
∞            # Get all integers (>= 1)                    Example for n=19
 ʒ           # where the following evaluates to True:
  2в         # The binary representation of the number    10011
    2ä       # Sliced into two pieces                     [[1, 0, 0], [1, 1]]
      øø     # Zipped together twice                      [[1, 0], [1, 1]]
        Ë    # Are they equal?                            0

Previous 19-byte answer:

∞ʒbVYg2÷UXYs£XYs.£Q
∞ʒ                          # Get all integers (>= 1) where the following evaluates to True:
  bV                        # Convert to binary and save in Y
    Yg                      # Get the length of Y
      2÷                    # Integer-divide by 2
        UX                  # Save this in X for later
          Ys£               # And get that many elements from the front of Y
             XYs.£          # Do the same but from the back of Y
                  Q         # Check if they are equal
                            # (Implicit output)
\$\endgroup\$
5
  • \$\begingroup\$ Why not just use filter instead of map and if? \$\endgroup\$
    – naffetS
    Dec 16, 2022 at 15:48
  • \$\begingroup\$ @Steffan thanks! I forgot about that. \$\endgroup\$
    – The Thonnu
    Dec 16, 2022 at 15:50
  • 1
    \$\begingroup\$ 10 bytes: Try it online! \$\endgroup\$
    – naffetS
    Dec 16, 2022 at 15:58
  • \$\begingroup\$ 9 bytes by using øøË without dumping the two parts to the stack (b will need to be bS or in that case, though). (@Steffan) \$\endgroup\$ Dec 27, 2022 at 10:01
  • \$\begingroup\$ @KevinCruijssen thanks, updated \$\endgroup\$
    – The Thonnu
    Dec 27, 2022 at 10:19
1
\$\begingroup\$

x86 32-bit machine code, 21 bytes

40 0F BD C8 D3 D8 72 02 D1 C8 D3 C0 89 C2 D3 E0 09 D0 D1 E8 C3

Try it online!

Following the regparm(1) calling convention, this takes the 1-indexed k in EAX and returns the kth number in EAX.


If we look at the left halves inclusive of the middle bit (if it exists), they form a useful pattern: 1, 11, 101, 111, 1010, 1111, 10010, 10110, 11011, 11111, 100100, 101101, 110110, 111111, ...
They are the binary representations of the positive integers, grouped by length and then with each group repeated twice, first with the last bit omitted from the remainder of the number, then with the last bit kept.

Add 1 to the 1-indexed k, to get numbers starting with 2=102, then take out the second bit of each number and use it to determine whether it goes in the first or second repetition of its group:

n       k   k+1
1₂      1   10₂
11₂     2   11₂
101₂    3   100111₂    4   1011010₂   5   1101111₂   6   11110010₂  7   100010110₂  8   100111011₂  9   101011111₂  10  1011100100₂ 11  1100101101₂ 12  1101110110₂ 13  1110111111₂ 14  1111

In assembly:

f:  inc eax       # Add 1 to EAX.
    bsr ecx, eax  # Set ECX to the position of the first 1 bit in EAX.
    rcr eax, cl   # Rotate EAX and the carry flag (CF) together right by that many bits.
                  #  (CL is the low byte of ECX; here it always equals the full value.)
                  #  The value of CF after BSR is officially undefined, but it is
                  #  consistently 0 (what this program needs) on at least some CPUs.
                  #  (To not rely on this, add CLC before this for +1 byte.)
                  #  The top 1 bit goes to the bottom, the second bit goes into CF,
                  #  and the rest of the bits go to the top of the value;
                  #  the bits we want to keep are now contiguous for plain rotates.
    jc s          # Jump if CF=1, skipping an instruction. (It is shortest
                  #  to use CF immediately, before another instruction overwrites it.)
    ror eax, 1    # (If CF=0) Rotate EAX right by 1 bit.
s:  rol eax, cl   # Rotate EAX left by CL, moving the value of the inclusive left half
                  #  to the bottom (0 removed) or one bit above the bottom (1 removed).
    mov edx, eax  # Copy the value of EAX into EDX.
    shl eax, cl   # Shift EAX left by CL, moving it to just above the copy in EDX.
    or eax, edx   # Combine EAX and EDX by bitwise OR into EAX.
    shr eax, 1    # Shift EAX right by 1 bit.
    ret           # Return. (EAX is the return value.)
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 99 79 bytes

b[11];n;main(l){for(;++n;)l=sprintf(b,"%b",n)/2,bcmp(b,b+l,l)||printf("%d",n);}

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Erm, this does seem to work. You cannot use %b in printf in any compiler that I know of. See this \$\endgroup\$
    – jdt
    Dec 18, 2022 at 18:45
  • \$\begingroup\$ You could have golfed it down to 79 bytes if it worked :-) \$\endgroup\$
    – jdt
    Dec 18, 2022 at 18:48
  • \$\begingroup\$ @jdt on gcc (GCC) 12.2.1 20221121 (Red Hat 12.2.1-4) %b works \$\endgroup\$
    – matteo_c
    Dec 20, 2022 at 14:23

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.