Sources page biographical material

5.E.2. MEMORY WHEELS = CHAIN CODES
These are cycles of 2ⁿ 0s and 1s such that each n tuple of 0s and 1s appears just once. They are sometimes called De Bruijn sequences, but they have now been traced back to the late 19C. An example for n = 3 is 00010111.
Émile Baudot. 1884. Used the code for 2⁵ in telegraphy. ??NYS -- mentioned by Stein.

A. de Rivière, proposer; C. Flye Sainte-Marie, solver. Question no. 58. L'Intermédiare des Mathématiciens 1 (1894) 19-20 & 107-110. ??NYS -- described in Ralston and Fredricksen (but he gives no. 48 at one point). Deals with the general problem of a cycle of kⁿ symbols such that every n tuple of the k basic symbols occurs just once. Gives the graphical method and shows that such cycles always exist and there are k!^g(n)/ kⁿ of them, where g(n) = k^n 1. This work was unknown to the following authors until about 1975.

N. G. de Bruijn. A combinatorial problem. Nederl. Akad. Wetensch. Proc. 49 (1946) 758 764. ??NYS -- described in Ralston and Fredricksen. Gives the graphical method for finding examples and finds there are 2^f(n) solutions, where f(n) = 2^n-1 - n.

I. J. Good. Normal recurring decimals. J. London Math. Soc. 21 (1946) 167-169. ??NYS -- described in Ralston and Fredricksen. Shows there are solutions but doesn't get the number.

R. L. Goodstein. Note 2590: A permutation problem. MG 40 (No. 331) (Feb 1956) 46 47. Obtains a kind of recurrence for consecutive n tuples.

Sherman K. Stein. Mathematics: The Man made Universe. Freeman, 1963. Chap. 9: Memory wheels. c= The mathematician as explorer, SA (May 1961) 149 158. Surveys the topic. Cites the c1000 Sanskrit word: yamátárájabhánasalagám used as the mnemonic for 01110100(01) giving all triples of short and long beats in Sanskrit poetry and music. Describes the many reinventions, including Baudot (1882), ??NYS, and the work of Good (1946), ??NYS, and de Bruijn (1946), ??NYS. 15 references.

R. L. Goodstein. A generalized permutation problem. MG 54 (No. 389) (Oct 1970) 266 267. Extends his 1956 note to find a cycle of aⁿ symbols such that the n tuples are distinct.

Anthony Ralston. De Bruijn sequences -- A model example of the interaction of discrete mathematics and computer science. MM 55 (1982) 131 143 & cover. Deals with the general problem of cycles of kⁿ symbols such that every n tuple of the k basic symbols occurs just once. Discusses the history and various proofs and algorithms which show that such cycles always exist. 27 references.

Harold Fredricksen. A survey of full length nonlinear shift register cycle algorithms. SIAM Review 24:2 (Apr 1982) 195-221. Mostly about their properties and their generation, but includes a discussion of the door lock connection, a mention of using the 2³ case as a switch for three lights, and gives a good history. The door lock connection is that certain push button door locks will open when a four digit code is entered, but they open if the last four buttons pressed are the correct code, so using a chain code reduces the number of button pushes required by a burglar to 1/4 of the number required if he tries all four digit combinations. 58 references.

At G4G2, 1996, Persi Diaconis spoke about applications of the chain code in magic and mentioned uses in repeated measurement designs, random number generators, robot location, door locks, DNA comparison.

They were first used in card tricks by Charles T. Jordan in 1910. Diaconis' example had a deck of cards which were cut and then five consecutive cards were dealt to five people in a row. He then said he would determine what cards they had, but first he needed some help so he asked those with red cards to step forward. The position of the red cards gives the location of the five cards in a cycle of 32 (which was the size of the deck)! Further, there are simple recurrences for the sequence so it is fairly easy to determine the location. One can code the binary quintuples to give the suit and value of the first card and then use the succeeding quintuples for the succeeding cards.

Long versions of the chain code are printed on factory floors so that a robot can read it and locate itself.

In Jan 2000, I discussed the Sanskrit chain code with a Sanskrit scholar, Dominik Wujastyk, who said that there is no known Sanskrit source for it. He has asked numerous pandits who did not know of it and he said there is is a forthcoming paper on it, but that it did not locate any Sanskrit source.