26
\$\begingroup\$

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 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
\$\endgroup\$
  • \$\begingroup\$ Just to make sure; does an infinite list as a value fall under the fourth output category? \$\endgroup\$ – Jonathan Frech Mar 20 at 2:44
  • \$\begingroup\$ @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.) \$\endgroup\$ – Arnauld Mar 20 at 8:42
  • \$\begingroup\$ Can the sequence be 2-indexed? \$\endgroup\$ – petStorm Mar 21 at 7:46
  • \$\begingroup\$ @a'_' No, sorry. Let's stick with the sequence default rules. \$\endgroup\$ – Arnauld Mar 21 at 7:55

26 Answers 26

9
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
5
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Save 1 byte by replacing +2-(n<2) with -~(n>1). \$\endgroup\$ – Chas Brown Mar 19 at 23:05
  • \$\begingroup\$ If you use range(9*n), the starting 0 helps you not getting the special case at start. 67 bytes \$\endgroup\$ – Surculose Sputum Mar 19 at 23:08
  • \$\begingroup\$ @SurculoseSputum Was just updating to that! :D \$\endgroup\$ – Noodle9 Mar 19 at 23:09
4
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
4
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
4
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

Ruby, 48 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • 2
    \$\begingroup\$ Save 11 bytes by returning the n-th entry, 0-based: Try it online! \$\endgroup\$ – Xcali Mar 20 at 14:31
  • 1
    \$\begingroup\$ @Xcali++ is unnecessary keeping 1-indexeded Try it online! \$\endgroup\$ – Nahuel Fouilleul Mar 20 at 15:15
2
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ The first line can be g$b=<<[1..]. \$\endgroup\$ – ovs Mar 20 at 14:39
  • \$\begingroup\$ @ovs Thank you very much. \$\endgroup\$ – Jonathan Frech Mar 20 at 16:22
2
\$\begingroup\$

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)
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – user41805 Mar 20 at 11:10
  • \$\begingroup\$ 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. \$\endgroup\$ – Mitchell Spector Mar 20 at 16:28
  • 1
    \$\begingroup\$ TIO's back in action! :D \$\endgroup\$ – Noodle9 Mar 20 at 18:11
  • \$\begingroup\$ @user41805 Thanks for the suggestions! They shortened the code considerably. \$\endgroup\$ – Mitchell Spector Mar 20 at 20:56
  • \$\begingroup\$ 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 \$\endgroup\$ – user41805 Mar 21 at 8:22
1
\$\begingroup\$

Charcoal, 34 22 bytes

≔…⌕A⭆⊗⊕θ⍘ι²01⊕θηI⁻⊟η⊟η

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.

≔…⌕A...01⊕θη

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

I⁻⊟η⊟η

Output the difference between the last two positions.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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)
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Gaia, 13 bytes

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

Try it online!

Port of Luis' MATL answer.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I wonder if there's something to do with __builtin_clz(), but a naive attempt is +2 bytes :-/ \$\endgroup\$ – Arnauld Mar 20 at 18:12
  • \$\begingroup\$ @Arnauld +1 byte :-/ \$\endgroup\$ – Noodle9 Mar 20 at 19:33
1
\$\begingroup\$

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.
```
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Factor, 92 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog Classic), 29 bytes

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

Try it online!

Will post explanation soon!

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ ,(2∘⊥⍣¯1)¨ can be just 2⊥⍣¯1¨ \$\endgroup\$ – Adám Mar 23 at 9:44
0
\$\begingroup\$

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)
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 70 bytes

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

Try it online!

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.