On 4/17/07, James Propp <propp@math.wisc.edu> wrote:

Fred Lunnon writes: ...

...

Lest this all seem absurdly half-baked, here's an example:

n = 4: 00101101 00001111

n = 5: 00101101 11010100010011 0000011111

A very nice idea! Can it be taken out to infinity?

Jim

n = 6: 0010110111010100010011 000010101111011001110001101001 000000111111 n = 7: [no such sequence ...] A more thorough investigation would backtrack over all possibilities; but at this juncture the original concept looks fairly moribund! Perhaps it's worth mentioning a bomb-proof but clumsier alternative. deBruijn sequences --- (k!)^k^(n-1)/k^n disitnct ones, modulo cyclic shift --- exist for every span n and base k (with k = 2 here). So at each iteration pick any one with span n' = 2^n, then shift it until the previous one with span n appears at the front. Or we might use binary Galois FSR sequences here, instead of deBruijn. These omit the string 0^n; on the other hand, there are theorems bounding the variation in word frequency (see Lidl & Niederreiter). Fred Lunnon