# CGAC2022 Day 16: Playing with bits, Part 2

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.

# 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?


# 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?  # 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. # 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. # 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 • Full programs are fine! Dec 16, 2022 at 2:08 # 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  # JavaScript (V8), 5451 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 # 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!

# 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


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

# 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


# 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.

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

# 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

• 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. Dec 19, 2022 at 20:55 • @DLosc really good tip about using y, I can see that being useful a lot Dec 19, 2022 at 22:59 # 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  # 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



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


# 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?

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


# 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


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

• Why not just use filter instead of map and if? Dec 16, 2022 at 15:48
• @Steffan thanks! I forgot about that. Dec 16, 2022 at 15:50
• 10 bytes: Try it online! Dec 16, 2022 at 15:58
• 9 bytes by using øøË without dumping the two parts to the stack (b will need to be bS or 2в in that case, though). (@Steffan) Dec 27, 2022 at 10:01
• @KevinCruijssen thanks, updated Dec 27, 2022 at 10:19

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


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

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