We appreciated the nice opening math club talk given by Pat Dragon. Here is his abstract.
A de Bruijn sequence is a binary string of length $2^n$ which, when viewed cyclically, contains every binary string of length $n$ exactly once as a substring. For example, 00010111 suffices for $n = 3$. Knuth refers to the lexicographically least de Bruijn sequence for each $n$ as the “Granddaddy” sequence due to its venerable origin. In 1934 Martin originally constructed these sequences and later it was shown by Fredericksen et al that they can also be constructed by concatenating the aperiodic prefixes of the binary necklaces of length $n$ in lexicographic order. In a recent publication, we proved that the Granddaddy has a lexicographic partner. The “Grandmama” sequence is constructed by concatenating the aperiodic prefixes of necklaces in co-lexicographic order. This talk will introduce de Bruijn sequences, the FKM algorithm, and some applications.