Covering binary strings

[Stefan Steinerberger]

Dear seqfans,

I invented the following problem some time ago and have
unfortunately been unable to solve it. Perhaps some of
you can provide a little insight, a solution or an idea.

The problem is best described as a little game. You are
given a string consisting of "0" and "1" of length n. An
example would be 1000101 (in this case n = 7).

Now you start with your own personal string who in the beginning
has the form 00...00 (n times 0). Now you change your personal
string by "applying arithmetical progressions" in such a manner
that you will eventually obtain the string given (1000101).

To clarify what I mean by "applying arithmetical progressions":
You can chose any arithmetical progression k*x+d with k,d
being integers. Then you look at the intersection of
{1,2,3...,n} and the image set of that progression (where x
takes every integer value). For any element m in that intersection
you move to the mth position of the string and change its value
(0 becomes 1 and 1 becomes 0). How many arithmetical progressions
do you need before you get the "goal string" given?

In our example we only need two arithmetical progressions:
0000000 - we use the arithmetical progression
6*x+1 (...-11, -5, 1, 7, 13, ...), therefore change the string at
the first and at the seventh position and get 1000001.
Now let us use the arithmetical progression 7*x + 5 and we
get 1000101 which is the goal string.

Now the question: For any natural number n, what is the
smallest number of arithmetical progressions you need to
get from the start string 00...00 to any string of length n?

The question can be easily answered for n=2 as there are
only four possible "goal strings". 00 is the start position
and we don't even need a single arithmetical progression
to get there. For 01 we only need to use 3*x+2. We get 10
by applying 3*x+1 once. 11 is obtained by using the
arithmetical progression x.
Thus we only need to apply one arithmetical progression
to cover all strings of length 2. But what about other n?

(It can be easily seen that you need at most n progressions
to cover all strings of length n, but I expect the smallest number
to be somewhere around sqrt(n)).

Perhaps someone can offer a proof, a proof of a special case,
some numerical data or a comment.

Best wishes,
Stefan