``Periods'' of de Bruijn sequences (Q1197392)

A de Bruijn sequence of degree \(n\) is a periodic binary sequence of periodicity \(2^ n\) in which each of the \(2^ n\) possible subsequences of length \(n\) occurs exactly once (in each periodicity). In each periodicity of length \(2^ n\) there are \(2^{n-2}\) ``periods'' (a run of 1's followed by a run of 0's). On the average the length per period is \(M_ 1=4\). In each de Bruijn sequence of degree \(n\geq 4\), and for each \(p\) with \(2\leq p\leq n-2\), periods of length \(p\) occur exactly \((p- 1)2^{n-2-p}\) times in each periodicity of the sequence, accounting for exactly \(2^{n-2}-(n-1)\) periods. The main interest in this paper is in the remaining \(n-1\) periods with length greater than \(n-2\). The sum of the lengths of these long periods is \(n^ 2-n-2\). The two extreme cases relative to these long periods are: one period of length \(2n\) and \(n-2\) periods of length \(n-1\); and \(n-3\) periods of length \(n\) and two periods of length \(n+1\). After establishing these and related results, the paper concludes with a list of open questions concerning the periods, their higher moments, etc., of the \(2^{2^{n-1}-n}\) de Bruijn sequences of degree \(n\).