History
The earliest known example of the De Bruijn sequence comes in Sanskrit prosody. The mnemonic yamātārājabhānasalagā was invented by Sanskrit prosodists to memorize the names of three-letter patterns as per the naming convention for three-letter sequences of long and short letters in Pingala's Chandah Shaastra (c. 200 BC). Denoting a long letter as L and short as S, this mnemonic corresponds to the sequence SLLLSLSSSL. By allowing wrapping around, the last two letters can be dropped from the mnemonic to give the circular mnemonic yamātārājabhānasa. The corresponding sequence is SLLLSLSS which is a B(2, 3) sequence for A = {S, L}.
Though the name De Bruijn is attached to these sequences due to his proof of K. Posthumus' conjecture in 1946, in 1975 he acknowledged that priority in this proof belonged to C. Flye Sainte-Marie, who had independently published it in 1894 after the question had been raised in print by A. de Riviere that same year. De Bruijn notes that the problem was also examined in 1934 and again independently in 1944.
Karl Popper independently describes these objects in his The Logic of Scientific Discovery, calling them "shortest random-like sequences".
Read more about this topic: De Bruijn Sequence
Famous quotes containing the word history:
“Free from public debt, at peace with all the world, and with no complicated interests to consult in our intercourse with foreign powers, the present may be hailed as the epoch in our history the most favorable for the settlement of those principles in our domestic policy which shall be best calculated to give stability to our Republic and secure the blessings of freedom to our citizens.”
—Andrew Jackson (1767–1845)
“One classic American landscape haunts all of American literature. It is a picture of Eden, perceived at the instant of history when corruption has just begun to set in. The serpent has shown his scaly head in the undergrowth. The apple gleams on the tree. The old drama of the Fall is ready to start all over again.”
—Jonathan Raban (b. 1942)
“Tell me of the height of the mountains of the moon, or of the diameter of space, and I may believe you, but of the secret history of the Almighty, and I shall pronounce thee mad.”
—Henry David Thoreau (1817–1862)