# CGAC2022 Day 9: Playing with bits

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

The Elves like playing number games. One day, Bin (a friend of Fen) suggests a new game: given a positive integer n, each Elf says a number which has exactly n runs of ones in binary. The first Elf must say the smallest number, and the next ones must say the smallest number greater than the last one.

Given n, output the sequence.

You can use any of I/O methods:

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

Standard rules apply. The shortest code in bytes wins.

## Test cases

n = 1
1, 2, 3, 4, 6, 7, 8, 12, 14, 15, 16, 24, 28, 30, 31, 32, 48, 56, 60, 62, 63,
64, 96, 112, 120, 124, 126, 127, ...

n = 2
5, 9, 10, 11, 13, 17, 18, 19, 20, 22, 23, 25, 26, 27, 29, 33, 34, 35, 36, 38,
39, 40, 44, 46, 47, 49, 50, 51, 52, 54, 55, 57, 58, 59, 61, 65, 66, 67, 68, ...

n = 3
21, 37, 41, 42, 43, 45, 53, 69, 73, 74, 75, 77, 81, 82, 83, 84, 86, 87, 89,
90, 91, 93, 101, 105, 106, 107, 109, 117, ...

n = 4
85, 149, 165, 169, 170, 171, 173, 181, 213, 277, 293, 297, 298, 299, 301, 309,
325, 329, 330, 331, 333, 337, 338, 339, 340, 342, 343, 345, ...

n = 5
341, 597, 661, 677, 681, 682, 683, 685, 693, 725, 853, 1109, 1173, 1189, 1193,
1194, 1195, 1197, 1205, 1237, 1301, 1317, 1321, 1322, 1323, 1325, ...

n = 6
1365, 2389, 2645, 2709, 2725, 2729, 2730, 2731, 2733, 2741, 2773, 2901, 3413,
4437, 4693, 4757, 4773, 4777, 4778, 4779, 4781, 4789, 4821, 4949, 5205, ...


The corresponding OEIS sequences are A023758 (without leading 0), A043682, A043683, A043684, A043685, and A043686.

# PARI/GP, 55 bytes

n->for(i=1,oo,sumdigits(bitxor(i,2*i),2)-2*n||print(i))


Attempt This Online!

Outputs the sequence infinitely.

For each positive integer $$\i$/extract_tex], print it if the sum of binary digits of $$\\operatorname{bitxor}(i,2i)$$/extract_tex] is $$\2n\$$. # Python 3, 61 bytes def f(n,i=1): while[n-1!=bin(i).count('01')or print(i)]:i+=1  A function that, given the number of runs, $$\n\$$, will print indefinitely. Try it online! ### How? The number of runs of 1s is the number of occurrences of 01 plus one (a binary number always starts with a one). The clause of the while loop will always be truthy as it is either [True] (when i has not got the right number of runs of ones) or [None] (when it does and print(i) executes and returns None). # MATL, 14 12 bytes @BY'wsG=?@D  Outputs the sequence indefinitely. Try it online! (you can stop it to see the output). ### Explanation  % Do...while @ % Push iteration index, starting at 1 B % Convert to binary. Gives, for example, [1 1 0 0 0] at iteration 24 Y' % Run-length encoding. Gives two outputs: [1 0], [2 3] in the example. % (The first output is the one really needed; the second will be % repurposed as loop condition to create an infinite loop) w % Swap. Moves [1 0] to the top of the stack s % Sum. This gives the number of runs of ones G= % Does it equal the input? ? % If so @D % Push iteration index and display immediately % End (implicit) % End (implicit). The loop condition, [2 3] in the example, is always % a vector of non-zero numbers, which is truthy, thereby producing an % infinite loop  # Rust, 52 bytes |j|(1u32..).filter(move|i|(i^i*2).count_ones()==j*2)  Attempt This Online! Uses the xor trick. Could save 1 byte by using u8 and abusing the "ignore number limits" rule. # JavaScript (V8), 56 bytes -2 thanks to @dingledooper Prints the sequence infinitely. And so do the other versions. Using alephalpha's method is more straightforward and shorter. Instead of incrementing each run one by one, $$\k \operatorname{XOR} 2\times k\$$ isolates all of them at once. n=>{for(k=0;g=k=>k&&.5+g(k&k-1);)g(++k^2*k)-n||print(k)}  Try it online! # JavaScript (V8), 61 bytes n=>{for(k=0;g=k=>k&&k%2+g(++k/(k&-k)>>1);)g(++k)-n||print(k)}  Try it online! ### Recursion logic Below is an example of the recursion that happens in $$\g\$$ for $$\k=441=110111001_2\$$, which has three runs of 1's:  0110111001 | odd -> we have a first run of 1's 0110111010 | increment 011011101 | divide by (k & -k) --> remove the trailing zeros 01101110 | right-shift by 1 ------------+-------------------------------------------------- 01101110 | even -> this is not a run of 1's 01101111 | increment 01101111 | divide by (k & -k) --> no change here 0110111 | right-shift by 1 ------------+-------------------------------------------------- 0110111 | odd -> we have a 2nd run of 1's 0111000 | increment 0111 | divide by (k & -k) --> remove the trailing zeros 011 | right-shift by 1 ------------+-------------------------------------------------- 011 | odd -> we have a 3rd run of 1's 100 | increment 1 | divide by (k & -k) --> remove the trailing zeros 0 | right-shift by 1 ------------+-------------------------------------------------- 0 | stop  # JavaScript (V8), 63 bytes A longer, slower, less fun solution using a regular expression. n=>{for(k=1;;k++)k.toString(2).split(/1+/).length+~n||print(k)}  Try it online! • I think this works for 56: n=>{for(k=0;;g(++k^2*k)-n||print(k))g=k=>k&&.5+g(k&k-1)} Dec 9, 2022 at 7:04 # Excel (ms365), 86, 80 bytes -8 Bytes thanks to jdt Formula in A1: =LET(x,ROW(A:A),FILTER(x,MAP(BASE(x,2),LAMBDA(a,COUNTA(TEXTSPLIT(a,0,,1))))=B1))  ROW(1:1048576) is used since that is the upper limit for Excel's rowcount in ms365. • I think ROW(A:A) will also work. – jdt Dec 11, 2022 at 19:07 # Raku, 36 bytes {grep *.base(2).comb(/1+/)==_,1..*}  Try it online! Anonymous function that takes $$\n\$$ and returns an infinite sequence. # Jelly, 9 bytes BŒgSḢ=ð#  Try it online! Full program taking n and k as successive command line arguments, outputting the first k elements of the sequence for n. A fun 11-byte alternative is BIAS:2‘ð#.  ð# Count up the first k integers from n, which satisfy, given n: Œg Group runs in the B binary representation of the candidate. S Sum the runs column-wise. Ḣ= Is the first sum equal to n?  # Python 3, 100 bytes from itertools import* def f(n): k=1 while 1: if 0<len([*groupby(bin(k))])-2*n<3:print(k) k+=1  Try it online! itertools.groupby can be used to find consecutive groups of equal values, and we can check the total number of groups to verify if its valid. • 98 bytes Dec 9, 2022 at 6:49 • Or 79 bytes using @alephalpha's method Dec 9, 2022 at 7:14 # JavaScript (V8), 55 bytes Takes $$\ n \$$ as input, and outputs the corresponding sequence infinitely. Based on the recurrence f(i) = f(i/2) + (i%4==1), which records the number of runs of ones in binary. The funny-looking expression, i%4%3%2, is used to save a byte over (i%4==1). n=>{for(i=0;;)(os[++i]=i%4%3%2+~~os[i>>1])-n||print(i)}  Try it online! # 05AB1E, 7 bytes ∞ʒbγĀOQ  Outputs the infinite sequence. γĀO could alternatively be Ô1ö: Try it online or verify the first 100 items up to $$\n\$$=6. Explanation: ∞ # Push the infinite list of positive integers: [1,2,3,...] ʒ # Filter it by: b # Convert the current integer to a binary-string γ # Split it into groups of equal adjacent items Ā # Python-style truthify each group: 1 for runs of 1s: "1"/"11"/"111"/etc.; # 0 for runs of 0s: "0"/"00"/"000"/etc. O # Sum it together to get the amount of groups of 1s Q # Check if its equal to the (implicit) input-integer # (after which the filtered infinite list is output implicitly as result) Ô # Connected-uniquify each group of equal adjacent items 1ö # Convert it from base-1 to base-10, basically summing the digits  # Pip, 23 21 bytes W++iI+TBiBXi*2=a*2Pi  Try It Online! Port of @alephalpha's answer. ALternatively, a 27 23 byte version taking n and k and returning the first k items -2 bytes (and -4 from the n+k version) thanks to @DLosc • 21 bytes by moving the increment into the loop condition, since 0 will never be an output. (Link is to TIO because DSO doesn't handle infinite loops well. As it turns out, this solution is the same length in Pip Classic as in modern Pip.) Dec 9, 2022 at 18:27 • Also, here's 23 bytes for the "first k items" version. Dec 9, 2022 at 18:33 # ><> (Fish), 71 bytes i1:0:2%?\2 ,40. >:?v~{:}= ?^1+10. 01.\:2%?v\1+1-2, 1.11,2-1/ /:naob  Try ## Explanation ><> lacks any kind of bitwise operators. So the only way to do this is with modulo. Basically, There I built a state machine that keeps track of the last bit. If num%2 == 1 and this wasn't true in the last state we add one to the streak. Top edge, red corner: Setup: Read the input, and start counting from 1. Top edge: Left dark blue half. Start a loop. Set current streak to 0. Then we reach the state if the last bit was a 0. We mod 1 and if it is 1 we go down to add 1 to the streak. Otherwise we divide the number by 2 and return to the :2 part. Second row, left part and third row left half: This is the state where the last bit was a 1. If it is a 1 again we sub 1 div 2 then jump back. If it is a 0 we can go back to the last state 0 state. If the entire number is 0 we jump to middle row right half. Middle row, right half: Compare the streak to the input. If they are equal print it (bottom right corner red) In either case add 1 to the counter and jump back to the start. Third row right half: This is the case if the last digit was a 0 but this is a 1. Add one to the streak. # Vyxal, 8 bytes bĠ∩Ṡ⁰c)ȯ  Try it Online! Takes k and n and returns the first k items. Port of Jelly. ## Explained (old) b0€ꜝL⁰=)ȯ -------)ȯ # first k integers where: b0€ # the binary representation of the number ꜝ # with empty lists removed L⁰= # is of length n  # Retina, 129 bytes L\d+ * "+"{_(1*) _01 Td1001* /^(_)+(?<-1>1+(0+|))+(?(1)^)/^{_(1*) _01 ))Td1001* +(\d*)\D+(\d) .(1*2*_2*)¶  Try it online! No test suite because of the way the program uses history. Takes k and n as input and outputs the kth number in the sequence for n. Explanation: L\d+ *  Drop k and convert n to unary. "+"{ )  Repeat k times. _(1*) _01 Td1001*  Increment the binary number after n. /^(_)+(?<-1>1+(0+|))+(?(1)^)/^{ )  Repeat while the binary number does not have exactly n runs of 1 bits... _(1*) _01 Td1001*  ... increment the binary number after n. +(\d*)\D+(\d) .(1*2*_2*)¶  Convert the binary number to decimal. # Charcoal, 29 28 bytes ＮθＮη≔⁰ζＷ‹ⅉη«≦⊕ζ¿⁼θ⊕№⍘ζ²01⟦Ｉζ  Try it online! Link is to verbose version of code. Outputs the first k elements. Explanation: ＮθＮη  Input n and k. ≔⁰ζ  Start at zero. Ｗ‹ⅉη«  Repeat until k numbers have been output. ≦⊕ζ  Try the next number. ¿⁼θ⊕№⍘ζ²01  If this number has n-1 copies of 01, then... ⟦Ｉζ  ... output this number on its own line. Edit: Saved 1 byte by using @JonathanAllen's run counting technique. # Brachylog, 7 bytes ℕ≜ḃḅzh+  A generator predicate that takes $$\n\$$ through its output parameter and produces the numbers from the corresponding sequence through its input parameter. Try it online! ### Explanation ℕ≜ḃḅzh+ ℕ The input parameter is a nonnegative integer ≜ Try each possibility in ascending order ḃ Convert to binary digits ḅ Group into blocks (runs of identical items) z Zip the list of blocks h Take the first sublist (which contains the first element of each block) + Sum The predicate succeeds if that sum is equal to the output parameter (i.e. n); otherwise, it fails, backtracks, and tries the next number  # Japt, 12 bytes _¤qT èÊ¥U}jV  Try it Inputs as n k. Outputs the first k elements. Can be changed to output the k-th element (0-indexed) by swapping j to i. Can reverse the inputs by swapping U and V. _¤qT èÊ¥U}jV _ }jV # Get the first k non-negative integers where this is true: ¤ # Convert to binary string qT # Split using "0" as a delimiter èÊ # Count the non-empty items ¥U # Return true if it equals n  There could easily be a 4-byte alternative to qT èÊ, but I haven't been able to find one yet. # Pip, 16 bytes W++iI+X1NTBi=aPi  Outputs the sequence forever. Try it online! (Works in both Pip Classic and modern Pip.) ### Explanation Implements the spec directly. W++iI+X1NTBi=aPi a is first command-line argument; i is 0 (implicit) W Loop while ++i increment i is truthy (i.e. forever): I If... X1 Convert 1 to a regex + Apply the + quantifier to it (one or more 1's) N Count the number of matches in TBi i, converted to binary =a ... equals the program argument: Pi Print that value of i  # Python, 83 bytes f=lambda n,k,b=1,s=.5:n and((k<b)*(4**(s+n-1)-f(n-.5,b-k-1))or f(n,k,b+b*n/s,s+.5))  Attempt This Online! Given n and k this directly computes the k-th term of the n-th series. Not competitive with the count-up-and-filter methods but I thought it may be interesting. # x86 32-bit machine code, 22 bytes 53 31 C0 40 6B D8 FE 4B 21 C3 F3 0F B8 DB 39 D3 75 F1 E2 EF 5B C3  Try it online! Following the fastcall calling convention, this takes a 1-indexed k in ECX and n in EDX, and returns a number in EAX. In assembly: f: push ebx # Save the value of EBX onto the stack. xor eax, eax # Set EAX to 0. r: inc eax # Add 1 to EAX. EAX will hold the number, x, being tested. imul ebx, eax, -2 # Set EBX to EAX times -2. dec ebx # Reduce EBX by 1, making -2x-1, which is the ones' complement of 2x. and ebx, eax # Set EBX to its bitwise AND with EAX. # Before this, EBX has a 1 bit to the left of each 0 bit in x and at the end. # The result of this AND has a 1 bit at the end of each run of 1 bits in x. popcnt ebx, ebx # Set EBX to the number of 1 bits in EBX. cmp ebx, edx # Compare that with n (in EDX). jne r # Jump back, to repeat, if they are not equal. loop r # Reduce ECX by 1 and jump back if it's nonzero, counting down from k. pop ebx # Restore the value of EBX from the stack. ret # Return.  # J, 27 bytes [{[:I.]=1#.2</\"1[:#:@i.4^+  Try it online! Takes k, 0-indexed, as left argument and n as right argument. 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1  Some earlier versions: [i.~[:+/$=1#.2</\"1[:#:@i.4^+ [i.~[:+/$$=[:+/2</\0|:[:#:@i.4^+
[i.~[:+/\]=0+/@(}:<}.)@|:[:#:@i.4^+


# C (gcc), 79 bytes

i;j;m;t;f(n,k){for(i=0;k;k-=!m)for(m=n,j=i++,t=0;j;j/=2)t^j&1?t=!t,m-=t:0;--i;}


Try it online!

Inputs $$\n\$$ and $$\k\$$.
Returns the $$\k^\text{th}\$$ number which has exactly $$\n\$$ runs of ones in binary.

• Suggest m-=t=!t instead of t=!t,m-=t Dec 11, 2022 at 7:19

# Perl 5, 60 + 2 (-na options) = 62 bytes

Given n and k and outputs the first k numbers of the sequence for n.

{$F+=say if$F[0]==split/0+/,sprintf'%b',++$_;$F[1]>\$F&&redo}


Try it online!

# Japt, 11 bytes

Returns the kth term, 0-indexed

@¶X¤ò< Ê}iV


Try it

@¶X¤ò< Ê}iV     :Implicit input of integers U=n & V=k
@               :Function taking an integer X as argument
¶              :  Test if U is equal to
X¤            :    X converted to a binary string
ò<          :    Partitioned between characters that are less than each other
Ê        :    Length
}       :End function
iV     :Get the Vth integer that returns true


# Julia, 52 bytes

>(x,i=0)=count("01",bitstring(i))==x&&@show(i)~x>i+1
`

Attempt This Online!

infinite recursive function, needs Julia 1.3 or later