CGAC2022 Day 9: Playing with bits

Question

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.

Task

Given n, output the sequence.

You can use any of sequence 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 code-golf 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.

Answer 1

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\$, print it if the sum of binary digits of \$\operatorname{bitxor}(i,2i)\$ is \$2n\$.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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!

Answer 6

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.

Answer 7

Raku, 36 bytes

{grep *.base(2).comb(/1+/)==$_,1..*}

Try it online!

Anonymous function that takes \$n\$ and returns an infinite sequence.

Answer 8

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?

Answer 9

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.

Answer 10

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!

Answer 11

05AB1E, 7 bytes

∞ʒbγĀOQ

Outputs the infinite sequence.

Try it online or verify the first 100 items up to \$n\$=6.

γĀ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

Answer 12

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

Answer 13

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

Answer 14

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

Answer 15

Retina, 129 bytes

L$`\d+$
*
"$+"{`_(1*)$
_0$1
T`d`10`01*$
/^(_)+(?<-1>1+(0+|$))+(?(1)^)$/^{`_(1*)$
_0$1
))T`d`10`01*$
+`(\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*)$
_0$1
T`d`10`01*$

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*)$
_0$1
T`d`10`01*$

... increment the binary number after n.

+`(\d*)\D+(\d)
$.($1*2*_$2*)¶

Convert the binary number to decimal.

Answer 16

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.

Answer 17

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

Answer 18

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.

Answer 19

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

Answer 20

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.

Answer 21

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.

Answer 22

J, 27 bytes

[{[:I.]=1#.2</\"1[:#:@i.4^+

Try it online!

Takes k, 0-indexed, as left argument and n as right argument.

• 4 ^ +: Raise 4 to the power (^) of the sum (+) of k and n. This is an upper bound for the result, as can be proven by considering numbers of the form (10)*10* in binary.
• [: #: @ i.: Make a list of the integers from 0 (inclusive) to 4^k+n (exclusive) using i., and then by composition (@), convert those numbers into their binary representations (#:), using a 'cap' ([:) to do so monadically.
  The result is a table like this, where each row is a binary representation:

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

• 2 < / \ " 1:
  • For each infix (\) of length 2 (each pair of consecutive bits), apply 'less than' (<) between the bits (/), producing 1 for each 0–1 pair (which appears at the start of each run of ones) and 0 otherwise.
    Note that this will miss the first run when the very first bit is 1, in the second half of the numbers, but there is enough excess in the upper bound of 4^k+n to let us ignore the second half.
  • On its own, that construction would incorrectly take pairs of rows. To fix that, set its rank (") to 1, so that it applies separately to each row, and then it takes pairs of bits within the rows.
• 1 #.: Convert from base 1, obtaining the number of runs of ones in each number. Conveniently, this naturally has rank 1, so it doesn't need rank adjustment.
• ] =: Check for equality (=) with the right argument n (]).
• [: I.: On a list of 0s and 1s, as here, I. gives a list of the indices of the 1s. Again, use a 'cap' ([:) to do this monadically.
• [ {: Use the left argument k ([) as an index ({) into the list.

---

Some earlier versions:

[i.~[:+/\]=1#.2</\"1[:#:@i.4^+
[i.~[:+/\]=[:+/2</\0|:[:#:@i.4^+
[i.~[:+/\]=0+/@(}:<}.)@|:[:#:@i.4^+

Answer 23

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.

Answer 24

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!

Answer 25

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

Answer 26

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