27
\$\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 '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 '20 at 8:42
  • \$\begingroup\$ Can the sequence be 2-indexed? \$\endgroup\$ – user92069 Mar 21 '20 at 7:46
  • \$\begingroup\$ @a'_' No, sorry. Let's stick with the sequence default rules. \$\endgroup\$ – Arnauld Mar 21 '20 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
\$\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.

\$\endgroup\$
  • \$\begingroup\$ Save 1 byte by replacing +2-(n<2) with -~(n>1). \$\endgroup\$ – Chas Brown Mar 19 '20 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 '20 at 23:08
  • \$\begingroup\$ @SurculoseSputum Was just updating to that! :D \$\endgroup\$ – Noodle9 Mar 19 '20 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
\$\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.

\$\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
\$\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!

\$\endgroup\$
2
\$\begingroup\$

Ruby, 48 bytes

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

Try it online!

\$\endgroup\$
2
\$\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)
\$\endgroup\$
  • \$\begingroup\$ Alternative 9: ∞bS.¬‹}€g \$\endgroup\$ – Grimmy Apr 7 '20 at 10:35
  • \$\begingroup\$ @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.) \$\endgroup\$ – Kevin Cruijssen Apr 7 '20 at 10:41
  • \$\begingroup\$ It's in info.txt. .¬ = pop a split a on function f, where f = [(a, b) → bool], usage: .¬<func>} \$\endgroup\$ – Grimmy Apr 7 '20 at 10:41
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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Save 11 bytes by returning the n-th entry, 0-based: Try it online! \$\endgroup\$ – Xcali Mar 20 '20 at 14:31
  • 1
    \$\begingroup\$ @Xcali++ is unnecessary keeping 1-indexeded Try it online! \$\endgroup\$ – Nahuel Fouilleul Mar 20 '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

\$\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!

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

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

\$\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.
\$\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!

\$\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.

\$\endgroup\$
1
\$\begingroup\$

Gaia, 13 bytes

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

Try it online!

Port of Luis' MATL 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
\$\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.

\$\endgroup\$
  • \$\begingroup\$ I wonder if there's something to do with __builtin_clz(), but a naive attempt is +2 bytes :-/ \$\endgroup\$ – Arnauld Mar 20 '20 at 18:12
  • \$\begingroup\$ @Arnauld +1 byte :-/ \$\endgroup\$ – Noodle9 Mar 20 '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.
```
\$\endgroup\$
1
\$\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
\$\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!

\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog Classic), 29 bytes

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

Try it online!

Will post explanation soon!

\$\endgroup\$
  • \$\begingroup\$ ,(2∘⊥⍣¯1)¨ can be just 2⊥⍣¯1¨ \$\endgroup\$ – Adám Mar 23 '20 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)
\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 70 bytes

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

Try it online!

\$\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.