Measure the lengths of binary patterns

Question

Let's consider the sequence of the binary representation of positive integers (without any leading zero):

1 2  3  4   5   6   7   8    9    10   11   12   ...
1 10 11 100 101 110 111 1000 1001 1010 1011 1100 ...

If we join them together, we get:

1101110010111011110001001101010111100 ...

If we now look for the patterns /1+0+/, we can split it as follows:

110 11100 10 1110 1111000 100 110 10 10 111100 ...

We define \$s_n\$ as the length of the \$n\$-th pattern built that way. Your task is to generate this sequence.

The first few terms are:

3, 5, 2, 4, 7, 3, 3, 2, 2, 6, 3, 5, 9, 4, 4, 2, 3, 4, 3, 2, 2, 3, 3, 2, 8, 4, 4, 2, 3, 7, 4, 6, 11, 5, 5, ...

_{Related OEIS sequence: A056062, which includes the binary representation of \$0\$ in the initial string and counts \$0\$'s and \$1\$'s separately.}

Rules

You may either:

• take \$n\$ as input and return the \$n\$-th term, 1-indexed
• take \$n\$ as input and return the \$n\$-th term, 0-indexed
• take \$n\$ as input and return the \$n\$ first terms
• take no input and print the sequence forever

This is a code-golf challenge.

Some more examples

The following terms are 1-indexed.

s(81)    = 13
s(100)   = 3
s(101)   = 2
s(200)   = 5
s(1000)  = 5
s(1025)  = 19
s(53249) = 29

Answer 1

Husk, 7 bytes

mLġ≤ṁḋN

Try it online!

Takes no input and prints ALL the numbers!

Explanation

mLġ≤ṁḋN
      N        The list of all positive integers [1,2,3...]
    ṁḋ         Convert each to binary and concatenate the resulting digits
  ġ≤           Split them in groups where each digit is less than or equal to the previous one (basically cuts wherever there is a 0 followed by a 1)
mL             Compute the length of each group

Answer 2

Python, ⁷⁷ 67 bytes

lambda n:len(''.join(f'{i:b}'for i in range(9*n)).split('01')[n])+2

Try it online!

Returns the \$n^\text{th}\$ term, 1-indexed.

Answer 3

MATL, 15 bytes

E:"@B]v&Y'2esG)

This takes n as input and outputs the n-th term, 1-indexed.

Try it online!

Explanation

A binary pattern of the specified form ends at least as often as every even number. So for input n, considering the numbers 1, 2, ..., 2*n guarantees that at least n patterns are obtained.

E      % Implicit input: n. Push 2*n
:"     % For each k in [| 2 ... 2*n]
  @    %   Push k
  B    %   Binary expansion. Gives a row vector containing 1's and 0's
]      % End
v      % Concatenate everything into a column vector
&Y'    % Lengths of run-length encoding. Runs contain 1's and 0's alternately
2e     % Reshape as a two-column matrix, in column-major order
s      % Sum of each column. This gives the lenghts of the desired patterns
G)     % Take the n-th entry. Implicit display

Answer 4

Haskell, 80 bytes

([1..]>>=f)#0
f 0=[]
f x=f(div x 2)++[mod x 2]
(0:1:x)#l=l+1:x#1
(a:x)#l=x#(l+1)

Try it online!

Inspired by Leo's Husk answer, calculates an infinite list.

Answer 5

Octave, 62 bytes

@(n)diff(regexp([arrayfun(@dec2bin,1:4*n,'un',0){:}],'1+'))(n)

Try it online!

Explanation

@(n)                                                           % function with input n
                                   1:4*n                       % range [1, 2, ... 4*n]
                 arrayfun(@dec2bin,     ,'un',0)               % convert each to binary string
                [                               {:}]           % concat into one string
         regexp(                                    ,'1+')     % starting indices of runs of 1's
    diff(                                                 )    % consecutive differences
                                                           (n) % take n-th entry

Answer 6

Jelly, 12 11 bytes

ḤB€FI»0kƲẈḣ

Try it online!

A monadic link taking an integer \$n\$ and returning the first \$n\$ terms of the series.

Change from ×9 to Ḥ inspired by @JonathanAllan’s answer. Thanks!

Answer 7

Ruby, 48 bytes

->n{("%b%b"*n%[*1..n*2]).scan(/1+0+/)[n-1].size}

Try it online!

Answer 8

05AB1E, 9 bytes

∞bSγ2ôεSg

Untested, since TIO isn't working.. >.> But it should work (unless one of those builtins used isn't lazy).
I'll try to finally install 05AB1E locally later today to verify if it indeed works.
EDIT: Installed 05AB1E locally, and apparently it didn't work due to the Join on the infinite list. So here an alternative 9-byter that does actually work.

Outputs the infinite sequence.

Try it online.

Explanation:

∞          # Push an infinite list of positive integers: [1,2,3,4,5,6,...]
 b         # Convert each to a binary string
           #  → ["1","10","11","100","101","110",...]
  S        # Convert it to a flattened list of digits
           #  → [1,1,0,1,1,1,0,0,1,0,1,1,1,0,...]
   γ       # Split them into parts of consecutive equal digits
           #  → [[1,1],[0],[1,1,1],[0,0],[1],[0],[1,1,1],[0],...]
    2ô     # Split all that into parts of size 2
           #  → [[[1,1],[0]],[[1,1,1],[0,0]],[[1],[0]],[[1,1,1],[0]],...]
      ε    # Map over each pair
       S   #  Convert it to a flattened list of digits again
           #   → [[1,1,0],[1,1,1,0,0],[1,0],[1,1,1,0],...]
        g  #  Pop and push its length
           #   → [3,5,2,4,...]
           # (after which the mapped infinite list is output implicitly as result)

Answer 9

Perl 5 -n, 73 bytes

$_=join'',map{sprintf"%b",$_}1..($n=$_)*2;say y///c for(/1+0+/g)[0..$n-1]

Try it online!

Takes input n via stdin, prints the first n numbers in the sequence.

Answer 10

K (ngn/k), 26 bytes

{x##'(&0>':t)_t:,/2\'!2*x}

Try it online!

Returns the first n items.

J, 35 bytes

{[:((1,2</\])#;.1])@;[:#:&.>[:i.3&*

Try it online!

Returns the nth item

Answer 11

Haskell, 135 128 bytes

• Saved seven bytes thanks to ovs.

g$b=<<[1..]
b 0=[];b n=b(div n 2)++[mod n 2]
l(1:r)1=1+l r 1;l(0:r)0=1+l r 0;l(0:r)1=1+l r 0;l(1:r)0=0
g a=l a 1:g(drop(l a 1)a)

Try it online!

Answer 12

Jelly, 11 bytes

ḤB€FŒgẈ+2/ḣ

A monadic Link accepting an integer, n, which yields a list of the first n values.

Try it online!

How?

ḤB€FŒgẈ+2/ḣ - Link: integer, n
Ḥ           - double (n)
  €         - for each v in (implicit range = [1..2n]):
 B          -   (v) to binary
   F        - flatten
    Œg      - group runs
      Ẉ     - get lengths
        2/  - 2-wise reduce by:
       +    -   addition
          ḣ - head to index (n)

Answer 13

bash + GNU utilities, 76 58 57 bytes

seq -f 2o%.fn $[2*$1]|dc|sed -E "s/(1*0*){$1}.*/\1Zp/"|dc

Try it online!

Thanks to user41805 for suggestions that ended up shaving 18 bytes off! And for 1 more byte now too.

Takes \$n\$ as an argument, and prints the \$n^\text{th}\$ entry in the sequence (with 1-based indexing).

Answer 14

Charcoal, 34 22 bytes

≔…⌕Ａ⭆⊗⊕θ⍘ι²01⊕θηＩ⁻⊟η⊟η

Try it online! Link is to verbose version of code. Based on @LuisMendo's observation that the numbers up to 2n provide sufficient digits, although I search for 01 so I actually need 0 through 2n+1. Explanation:

⭆⊗⊕θ⍘ι²

Convert all the numbers from 0 to 2n+1 to base 2 and concatenate them.

≔…⌕Ａ...01⊕θη

Find the positions of the substrings 01 but truncated after the nth entry.

Ｉ⁻⊟η⊟η

Output the difference between the last two positions.

Answer 15

Jelly, 15 14 bytes

×3ŻBFœṣØ.ḊẈ+2ḣ

Try it online! Thanks to @JonathanAllan and @NickKennedy for helping me out, in chat, to finish this solution. I came up with ×3RBFœṣØ.Ẉ+2ḣ but that fails for n = 1!

How it works:

×3ŻBFœṣØ.ḊẈ+2ḣ    Monadic link: takes `n` as input and returns the first `n` terms
×3                Multiply input by three and
  Ż                create the list [0, 1, ..., 3n].
   B              Get the binary representation of each number and
    F              flatten to get [0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, ...]
                  Now we find the /1+0+/ patterns by looking at occurrences of [0, 1],
                   i.e. when one pattern ends and the next begins:
     œṣ           Split the [0, 1, 1, 0, 1, 1, 1, 0 ...] list at occurrences of
       Ø.         [0, 1], so [0, 1, 1, 0, 1, 1, 1, 0 ...] -> [[], [1], [1, 1, ...], ...]
         Ḋ         and drop the first element of the resulting list (the empty one).
          Ẉ       Finally we get the length of each sublist,
           +2      add 2 (to compensate for the lost 1 and 0),
             ḣ     and take the first `n` elements of that.

Answer 16

Red, 122 111 bytes

func[n][b: copy""repeat i 2 * n[append b find enbase/base
to#{}i 2"1"]parse b[n copy i[any"1"any"0"]]length? i]

Try it online!

Answer 17

PHP, 108 bytes

for($a=[$p=$i=1];;$p=$c,$o++){if(!$a)$a=str_split(decbin(++$i));if($p<$c=array_shift($a)){echo$o,',';$o=0;}}

Try it online!

Will print the sequence indefinitely.

Answer 18

Gaia, 13 bytes

ḣ┅b¦_ėt(2/Σ¦E

Try it online!

Port of Luis' MATL answer.

Answer 19

Japt, 11 bytes

Outputs the nth 1-indexed term.

g°U²ô¤¬ò<)l

Try it

g°U²ô¤¬ò<)l     :Implicit input of integer U
g               :Index into
 °U             :  Increment U
   ²            :  Square it
    ô           :  Range [0,result]
     ¤          :  To binary strings
      ¬         :  Join
       ò<       :  Partition after characters that are less than the next
         )      :End indexing
          l     :Length

Answer 20

C (gcc), ^{124 \$\cdots\$ 109} 104 bytes

Saved 2 3 4 8 9 14 bytes thanks to Arnauld!!!

c;t;b;i;f(n){for(i=c=0,t=1;++i;){for(b=0;i>>++b;);for(;b--;++c)if(t^i>>b&1&&(t^=1)?c*=!--n:0)return c;}}

Try it online!

Goes through positive integers \$i\$ catching transitions from \$0\$ to \$1\$ as it rolls through the non-leading-zero bits of the \$i\$'s.

Returns the \$n^\text{th}\$ term, 1-indexed.

Answer 21

W x, 7 bytes

REALLY slow. The array is 1-indexed and it outputs all upto the input. (Glad that I tie with Husk BTW. Special bonus: it doesn't involve infinite lists!)

♫│x╤►U╟

Uncompressed:

^k2BLHkr

Explanation

^        % 10 ^ input. Make sure that enough items are calculated.
 k       % Find the length range of that.
  2B     % Convert every item to binary.
         % Since at least 1 item >= the base, this vectorizes.

         % Automatic flatten before grouping
    LH   % Grouping: Is the previous item >= current item?
      kr % Reduce by length

Flag:x  % Output all items upto the input, including input-indexed item. 1-indexed.

W x, 8 bytes

You can try this without having to wait for a long time.

☺│╪å∟↕c╟

Uncompressed:

3*k2BLHkr

Explanation

3*         % Input times 3, idea copied from RGS's answer.
  k        % Provide a length-range
   2B      % Convert all to binary
     LH    % Group by >=
           % Automatic flattening before grouping
       kr  % Reduce by length

Flag:x      % Output all less than the input index. INCLUDING the input index item.
```

Answer 22

APL (Dyalog Extended), 17 bytes

{⍵⊃≢¨⊆⍨1+∊⊤¨⍳+⍨⍵}

Try it online!

Gives nth term, 1-indexed.

How it works

{⍵⊃≢¨⊆⍨1+∊⊤¨⍳+⍨⍵}
{               }  ⍝ ⍵←n
             +⍨⍵   ⍝ Double of n
            ⍳      ⍝ 1 .. 2n, inclusive
         ∊⊤¨  ⍝ Convert each to binary and flatten
       1+     ⍝ Add 1
     ⊆⍨       ⍝ Partition self into non-increasing segments
              ⍝ (Without 1+, zero items are dropped)
   ≢¨  ⍝ Lengths of each segment
 ⍵⊃    ⍝ Take nth item

Answer 23

Vyxal, 67 bits^v2, 8.375 bytes

Þ∞bfĠ2ẇvf@

Try it Online!

Bitstring:

0010011101110110001111101100111001011111001011101000111011000011110

Answer 24

Factor, 92 bytes

: f ( n -- n ) dup 3 * [0,b] [ >bin ] map concat "01" " " replace " " split nth length 2 + ;

Try it online!

Answer 25

APL (Dyalog Classic), 29 bytes

{⍵+.=+\2</∊,(2∘⊥⍣¯1)¨⍳3+⍵}

Try it online!

Will post explanation soon!

Answer 26

Zpr'(h, 369 bytes

s |> \

(g (foldr (op-> ++) () (map b |N)))
(e ())|>o
(e (S ()))|>z
(e (S (S .n)))|>(e n)
(h ())|>()
(h (S ()))|>()
(h (S (S .n)))|>(S (h n))
(b ())|>()
(b (S .n))|>((b (h (S n))) ++ (' (e n) ()))
(l (' z (' o .r)))|>1
(l (' z (' z .r)))|>(S (l (' z r)))
(l (' o (' o .r)))|>(S (l (' o r)))
(l (' o (' z .r)))|>(S (l (' z r)))
(g .a)|>(' (l a) (g (drop (l a) a)))
<|prelude.zpr

main |> (take 8 s)

Execution

Zpr-h-master/stdlib$ ../Zprh --de-peano above.zpr
(' 3 (' 5 (' 2 (' 4 (' 7 (' 3 (' 3 (' 2 0))))))))

Explanation

; build the sequence by splitting the bits of all natural numbers |N
sequence |> (generate (foldr (op-> ++) () (map bits |N)))

; compute if a natural number is even (parity shifted by one)
(even ())         |> one
(even (S ()))     |> zero
(even (S (S .n))) |> (even n)

; halve a natural number, rounding down
(halve ())         |> ()
(halve (S ()))     |> ()
(halve (S (S .n))) |> (S (halve n))

; compute a natural number's binary representation
(bits ())     |> ()
(bits (S .n)) |> ((bits (halve (S n))) ++ (' (even n) ()))

; compute the length of the pattern sought after at the bit stream's beginning
(len (' zero (' one .rest)))  |> 1
(len (' zero (' zero .rest))) |> (S (len (' zero rest)))
(len (' one (' one .rest)))   |> (S (len (' one rest)))
(len (' one (' zero .rest)))  |> (S (len (' zero rest)))

(generate .all-bits) |> (' (len all-bits) \
                           (generate (drop (len all-bits) all-bits)))

; include from the standard library
<| prelude.zpr

; output the first eight sequence members
main |> (take 8 sequence)

Answer 27

Wolfram Language (Mathematica), 70 bytes

Tr[1^Join@@Partition[Split[Join@@IntegerDigits[Range[2#],2]],2][[#]]]&

Try it online!