On 4/18/07, James Propp <propp@math.wisc.edu> wrote:
Fred Lunnon wrote:
Perhaps it's worth mentioning a bomb-proof but clumsier alternative. deBruijn sequences --- (k!)^k^(n-1)/k^n distinct 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.
Can you explain in more detail how this works? I'm not seeing it.
Jim
Starting with n = 1: S = 01; there's no choice about the next iteration n = 2: S = 0110; now generate any old deBruijn sequence with span 4 --- say the first in numerical order, 000010 0110 101111 --- and shift it until the previous S (occurring as a factor at just one position, by definition of deBruijn sequence) lies at the front n = 4: S = 0110101111000010; at the next iteration we shall generate 65536 bits, which I fear our moderator might consider immoderate ... For the Galois sequence variation, the algorithm must generate primitive polynomials (to generate each new finite sequence) and compute discrete logarithms (to locate the old as a factor of the new). Fred Lunnon