CGAC2022 Day 16: Playing with bits, Part 2

Question

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 sequence 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 code-golf 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.

Answer 1

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?

Answer 2

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?

Answer 3

Charcoal, 22 bytes

≔⍘⊕Ｎ²θＩ÷⍘ײΦθ⊖κ²⊕⁼§θ¹0

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

≔⍘⊕Ｎ²θ

Convert n+1 to base 2 as a string.

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

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

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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!

Answer 9

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

Answer 10

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

Answer 11

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

Answer 12

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.

Answer 13

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

Answer 14

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

Answer 15

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    

Answer 16

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

Answer 17

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?

Answer 18

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

Answer 19

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)

Answer 20

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=10₂, 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   100₂
111₂    4   101₂
1010₂   5   110₂
1111₂   6   111₂
10010₂  7   1000₂
10110₂  8   1001₂
11011₂  9   1010₂
11111₂  10  1011₂
100100₂ 11  1100₂
101101₂ 12  1101₂
110110₂ 13  1110₂
111111₂ 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.)

Answer 21

C (gcc), 99 79 bytes

• -2 bytes thanks to @ceilingcat
• -18 bytes thanks to @jdt

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

Try it online!