MathDB

We say that a binary string

s

contains another binary string

t

if there exist indices

i_1,i_2,\ldots,i_{|t|}

with

i_1 < i_2 < \ldots < i_{|t|}

such that

s_{i_1}s_{i_2}\ldots s_{i_{|t|}} = t.

(In other words,

t

is found as a not necessarily contiguous substring of

s

.) For example,

110010

contains

111

. What is the length of the shortest string

s

which contains the binary representations of all the positive integers less than or equal to

2048

Problem Statement