Editing De Bruijn sequence (section)

== History ==
The earliest known example of a de Bruijn sequence comes from [[Sanskrit prosody]] where, since the work of [[Pingala]], each possible three-syllable pattern of long and short syllables is given a name, such as 'y' for short–long–long and 'm' for long–long–long. To remember these names, the mnemonic ''yamātārājabhānasalagām'' is used, in which each three-syllable pattern occurs starting at its name: 'yamātā' has a short–long–long pattern, 'mātārā' has a long–long–long pattern, and so on, until 'salagām' which has a short–short–long pattern. This mnemonic, equivalent to a de Bruijn sequence on binary 3-tuples, is of unknown antiquity, but is at least as old as [[Charles Philip Brown]]'s 1869 book on Sanskrit prosody that mentions it and considers it "an ancient line, written by [[Pāṇini]]".<ref>{{harvtxt|Brown|1869}}; {{harvtxt|Stein|1963}}; {{harvtxt|Kak|2000}}; {{harvtxt|Knuth|2006}}; {{harvtxt|Hall|2008}}.</ref>

In 1894, A. de Rivière raised the question in an issue of the French problem journal ''[[L'Intermédiaire des Mathématiciens]]'', of the existence of a circular arrangement of zeroes and ones of size <math>2^n</math> that contains all <math>2^n</math> binary sequences of length <math>n</math>. The problem was solved (in the affirmative), along with the count of <math>2^{2^{n-1} - n}</math> distinct solutions, by Camille Flye Sainte-Marie in the same year.{{sfnp|de Bruijn|1975}} This was largely forgotten, and {{harvtxt|Martin|1934}} proved the existence of such cycles for general alphabet size in place of 2, with an algorithm for constructing them. Finally, when in 1944 [[Kees Posthumus]] [[conjecture]]d the count <math>2^{2^{n-1} - n}</math> for binary sequences, de Bruijn proved the conjecture in 1946, through which the problem became well known.{{sfnp|de Bruijn|1975}}

[[Karl Popper]] independently describes these objects in his ''[[The Logic of Scientific Discovery]]'' (1934), calling them "shortest random-like sequences".{{sfnp|Popper|2002}}