# pattern in a bit sequence

• February 20th 2010, 10:51 AM
gitterrost4
pattern in a bit sequence
Hello,

I don't know, if my problem really boils down to a number theory problem, but I think it will be mostly that.

The task is to create a sequence of bits (0 or 1) that contains all sequences of a certain length n. The primitive and most intuitive way to do this, is to just concatenate the possible sequences with length n.

For example for n=2:

00011011

In this sequence the sequence "00" appears more than once. Apparently the sequence 00110 is much more efficient.

So I thought of an algorithm that would create sequence of minimal length, which match the requirement. (I proved the correctness and the minimality of the resulting sequence):

Algorithm:
1. start the sequence with n zeroes
2. while not every sequence of length n is used:
2.1 try to attach a one to the sequence and look, if the last n bits were already used.
2.2 if yes, attach the one
2.3 else attach a zero

This Algorithm gives the following sequences:
n=2:
00110
n=3:
0001110100
n=4:
0000111101100101000

A file listing the sequences through n=9 can be found here:
http://dl.dropbox.com/u/1588518/bitfolgen

The problem with my implementation of the algorithm is, that you have to use an array with all possible sequences of length n. Meaning an array of the size of $2^n$. So a normal computer having 2GB RAM can only calculate these sequences up to n=31.

My desire is to find an algorithm which creates this (or an equivalent) sequence without using up that much memory. Meaning an algorithm that could produce these sequences for big values of n, provided one has enough time.

After not getting further with my algorithms, I looked at the possible minimal valid sequences. The first would be:
n=1 01, 10
n=2 01100, 00110, 10011, 11001
So it seems, that for one value of n there are $2^{2^{n-1}}$ different valid sequences.