The Discrepancy of the Lex-Least De Bruijn Sequence
classification
🧮 math.CO
keywords
discrepancysequenceanswerbruijnnumberabsolutebinarydifference
read the original abstract
We answer the following question of R. L. Graham: What is the discrepancy of the lexicographically-least binary de Bruijn sequence? Here, "discrepancy" refers to the maximum (absolute) difference between the number of ones and the number of zeros in any initial segment of the sequence. We show that the answer is $\Theta(2^n \log n/n)$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.