# Measure the lengths of binary patterns

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$/extract_tex] 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 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 • Just to make sure; does an infinite list as a value fall under the fourth output category? – Jonathan Frech Mar 20 '20 at 2:44 • @JonathanFrech As long as it can be easily viewed somehow -- partially, obviously -- that's fine with me. (But that's actually a good question that should be asked on Meta if it wasn't already.) – Arnauld Mar 20 '20 at 8:42 • Can the sequence be 2-indexed? – user92069 Mar 21 '20 at 7:46 • @a'_' No, sorry. Let's stick with the sequence default rules. – Arnauld Mar 21 '20 at 7:55 ## 26 Answers # 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 # Python, 77 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. • Save 1 byte by replacing +2-(n<2) with -~(n>1). – Chas Brown Mar 19 '20 at 23:05 • If you use range(9*n), the starting 0 helps you not getting the special case at start. 67 bytes – Surculose Sputum Mar 19 '20 at 23:08 • @SurculoseSputum Was just updating to that! :D – Noodle9 Mar 19 '20 at 23:09 # 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 # 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. # 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 # 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! # Ruby, 48 bytes ->n{("%b%b"*n%[*1..n*2]).scan(/1+0+/)[n-1].size} Try it online! # 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) • Alternative 9: ∞bS.¬‹}€g – Grimmy Apr 7 '20 at 10:35 • @Grimmy What does do? It's not in the wiki, and I'm a bit too lazy to dive into the code. ;) (And I've the huge golf you did on my other answer. I will update it when I have some time.) – Kevin Cruijssen Apr 7 '20 at 10:41 • It's in info.txt. .¬ = pop a split a on function f, where f = [(a, b) → bool], usage: .¬<func>} – Grimmy Apr 7 '20 at 10:41 # 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. • Save 11 bytes by returning the n-th entry, 0-based: Try it online! – Xcali Mar 20 '20 at 14:31 • @Xcali++ is unnecessary keeping 1-indexeded Try it online! – Nahuel Fouilleul Mar 20 '20 at 15:15 # 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

• 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! • The first line can be g$b=<<[1..]. – ovs Mar 20 '20 at 14:39
• @ovs Thank you very much. – Jonathan Frech Mar 20 '20 at 16:22

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

Ḥ           - 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:
ḣ - head to index (n)

# bash + GNU utilities, 7658 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). • I believe you can replace (1*0*){$1}(1*0+) with (1*0*){$1} and use \1 instead of \2 in the sed substitution, and include i=1 in the for loop and remove 0 in the dc command to save some bytes. Actually, I think using seq | xargs can be shorter than the for-loop. – user41805 Mar 20 '20 at 11:10 • Thanks -- I'll take a look at this. I had put the 0 in the dc command precisely so I could eliminate i=0 in the loop initialization, for a savings of 2 bytes. – Mitchell Spector Mar 20 '20 at 16:28 • TIO's back in action! :D – Noodle9 Mar 20 '20 at 18:11 • @user41805 Thanks for the suggestions! They shortened the code considerably. – Mitchell Spector Mar 20 '20 at 20:56 • Nice usage of seq -f instead of xargs. I believe you can use dc instead of wc -c by changing the replacement part of the sed s command to save a byte – user41805 Mar 21 '20 at 8:22 # 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. # 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. # 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! # 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. # Gaia, 13 bytes ḣ┅b¦_ėt(2/Σ¦E Try it online! Port of Luis' MATL answer. # 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 # 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. • I wonder if there's something to do with __builtin_clz(), but a naive attempt is +2 bytes :-/ – Arnauld Mar 20 '20 at 18:12 • @Arnauld +1 byte :-/ – Noodle9 Mar 20 '20 at 19:33 # Wx, 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. # Wx, 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. $$`$$ # 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 # Factor, 92 bytes : f ( n -- n ) dup 3 * [0,b] [ >bin ] map concat "01" " " replace " " split nth length 2 + ; Try it online! # APL (Dyalog Classic), 29 bytes {⍵+.=+\2</∊,(2∘⊥⍣¯1)¨⍳3+⍵} Try it online! Will post explanation soon! • ,(2∘⊥⍣¯1)¨ can be just 2⊥⍣¯1¨ – Adám Mar 23 '20 at 9:44 # 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)

# Wolfram Language (Mathematica), 70 bytes

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

Try it online!