25,161
edits
Changes
Created page with "'''Home * Programming * Data * De Bruijn Sequence''' FILE:LW441-MC-Escher-Moebius-Strip-II-1963.jpg|border|right|thumb|link=http://www.mcescher.com/ga..."
'''[[Main Page|Home]] * [[Programming]] * [[Data]] * De Bruijn Sequence'''
[[FILE:LW441-MC-Escher-Moebius-Strip-II-1963.jpg|border|right|thumb|link=http://www.mcescher.com/gallery/recognition-success/mobius-strip-ii/|[[Arts#Escher|M.C. Escher]] - Möbius Strip II <ref>[http://www.mcescher.com/gallery/recognition-success/ M.C. Escher - The Official Website – Recognition & Success] </ref> <ref>[https://en.wikipedia.org/wiki/M%C3%B6bius_strip Moebius Strip from Wikipedia]</ref> ]]
In [https://en.wikipedia.org/wiki/Combinatorics combinatorial mathematics], a '''k'''-ary '''De Bruijn Sequence''' B(k, n) of order '''n''', named after the Dutch mathematician [[Nicolaas de Bruijn]], is a cyclic sequence of a given alphabet '''A''' with size '''k''' for which every possible subsequence of length '''n''' in '''A''' appears as a sequence of consecutive characters exactly once <ref>[https://en.wikipedia.org/wiki/De_Bruijn_sequence De Bruijn sequence from Wikipedia]</ref>.
In chess programming there are applications of de Bruijn sequences with the Binary alphabet, in [[Hash Table|hashing]] sets like [[Piece-Sets]] or Square-sets, also called [[Bitboards]], most notably in [[BitScan#DeBruijnMultiplation|Bit scanning]] <ref>[[Charles Leiserson|Charles E. Leiserson]], [[Harald Prokop]], [[Keith H. Randall]] ('''1998'''). ''Using de Bruijn Sequences to Index a 1 in a Computer Word''. [http://supertech.csail.mit.edu/papers/debruijn.pdf pdf]</ref> .
=Binary alphabet=
According to De Bruijn himself <ref>[[Nicolaas de Bruijn]] ('''1975'''). ''Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once''. Technical Report, Technische Hogeschool Eindhoven, [http://alexandria.tue.nl/repository/books/252901.pdf pdf]</ref> , the existence of De Bruijn sequences were first proved, for the case of alphabets with two elements, by '''Camille Flye Sainte-Marie''' in 1894, whereas the generalization to larger alphabets is originally due to [[Mathematician#Ehrenfest|Tanja van Ardenne-Ehrenfest]] <ref>[[Nicolaas de Bruijn]] ('''1985'''). ''In Memoriam T. van Ardenne-Ehrenfest''. [http://alexandria.tue.nl/repository/freearticles/597575.pdf pdf]</ref> and himself.
Binary digits or [[Bit|bits]] inside a computer word are B(2, n) de Bruijn sequences, with '''2<span style="vertical-align: super;">n</span>''' bits length and equal number of ones and zeros, with '''2<span style="vertical-align: super;">n</span>''' overlapping unique '''n'''-bit subsequences. Since the sequences are cyclic and '''n-1''' subsequences need to wrap, we restrict them to at least '''n-1''' leading zeros, to make them overlap the hidden trailing "zeros".
Odd sequences have '''n''' leading zeros. The even ones with '''n-1''' leading zeros are rotated (shifted) left by one. Due to '''n''' leading zeros of these odd sequences we further consider, the first subsequence['''0'''] is zero. Due to the overlapping, each subsequence['''i'''+1] is dependent from subsequence['''i''']. The doubled value incremented by either zero or one. Since subsequence['''0'''] is zero, a second zero subsequence with six consecutive binary zeros is further prohibited, and subsequence['''1'''] must be one. Subsequence index '''i''' is counted from most significant bit left to right, and therefor reversed from usual bit-index. A modulo '''2<span style="vertical-align: super;">n</span>''' restricts all subsequences to '''n''' bits:
s[i+1] = (2s[i] + (0|1)) mod (2<span style="vertical-align: super;">n</span>)
The [https://en.wikipedia.org/wiki/Cardinality Cardinality] of all distinct B(2, n) de Bruijn sequences is:
|B(2, n)| = 2<span style="vertical-align: super;">(2<span style="vertical-align: super;">n-1</span> - n)</span>
{| class="wikitable"
|-
! n
! 2<span style="vertical-align: super;">n-1</span> - n
! |B(2, n)|
|-
| style="text-align:center;" | 1
| style="text-align:right;" | 0
| style="text-align:right;" | 1
|-
| style="text-align:center;" | 2
| style="text-align:right;" | 0
| style="text-align:right;" | 1
|-
| style="text-align:center;" | 3
| style="text-align:right;" | 1
| style="text-align:right;" | 2
|-
| style="text-align:center;" | 4
| style="text-align:right;" | 4
| style="text-align:right;" | 16
|-
| style="text-align:center;" | 5
| style="text-align:right;" | 11
| style="text-align:right;" | 2,048
|-
| style="text-align:center;" | 6
| style="text-align:right;" | 26
| style="text-align:right;" | 67,108,864
|-
| style="text-align:center;" | 7
| style="text-align:right;" | 57
| style="text-align:right;" | 144,115,188,075,855,872
|-
| style="text-align:center;" | 8
| style="text-align:right;" | 120
| style="text-align:right;" | ~1.329e+36
|}
==B(2, 1)==
The two one-bit subsequences obviously do not overlap:
<pre>
i 01 s[i]
0 0 0
1 1 1
</pre>
==B(2, 2)==
B(2, 2) implies 2<span style="vertical-align: super;">2</span> or 4-bit sequences. There is one odd four-bit de Bruijn sequence with four overlapping unique two-bit subsequences, 0x3.
<pre>
i 0011|0 s[i]
0 00 . . . 0
1 01 1
2 . 11 . . 3
3 1|0 2
</pre>
==B(2, 3)==
B(2, 3) implies 2<span style="vertical-align: super;">3</span> or 8-bit sequences. There are two odd eight-bit sequences with eight overlapping unique three-bit subsequences, 0x17 and 0x1d. Note that the five relevant bits are reversed.
<pre>
i 00010111|00 s[i] i 00011101|00 s[i]
0 000 . . . . 0 0 000 . . . . 0
1 001 1 1 001 1
2 . 010 . . . 2 2 . 011 . . . 3
3 101 5 3 111 7
4 . . 011 . . 3 4 . . 110 . . 6
5 111 7 5 101 5
6 . . . 11|0 6 6 . . . 01|0 2
7 1|00 4 7 1|00 4
</pre>
==B(2, 4)==
B(2, 4) implies 2<span style="vertical-align: super;">4</span> or 16 bit sequences. There are 16 odd 16-bit sequences with 16 overlapping unique four-bit subsequences:
<pre>
0x09af 0000100110101111
0x09eb 0000100111101011
0x0a6f 0000101001101111
0x0a7b 0000101001111011
0x0b3d 0000101100111101
0x0b4f 0000101101001111
0x0bcd 0000101111001101
0x0bd3 0000101111010011
0x0cbd 0000110010111101
0x0d2f 0000110100101111
0x0d79 0000110101111001
0x0de5 0000110111100101
0x0f2d 0000111100101101
0x0f4b 0000111101001011
0x0f59 0000111101011001
0x0f65 0000111101100101
</pre>
for instance 0x0d2f:
<pre>
i 0000110100101111|000 s[i]
0 0000 . . . . . . . . 0
1 0001 1
2 . 0011 . . . . . . . 3
3 0110 6
4 . . 1101 . . . . . . 13
5 1010 10
6 . . . 0100 . . . . . 4
7 1001 9
8 . . . . 0010 . . . . 2
9 0101 5
10 . . . . . 1011 . . . 11
11 0111 7
12 . . . . . . 1111 . . 15
13 111|0 14
14 . . . . . . . 11|00 12
15 1|000 8
</pre>
==B(2, 5)==
B(2, 5) implies 2<span style="vertical-align: super;">5</span> or 32 bit sequences. There are 2^11 or 2,048 odd 32-bit sequences with 32 overlapping unique five-bit subsequences, for instance 0x076be629
<pre>
i 00000111011010111110011000101001|0000 s[i]
0 00000 . . . . . . . . . . . . . . . . 0
1 00001 1
2 . 00011 . . . . . . . . . . . . . . . 3
3 00111 7
4 . . 01110 . . . . . . . . . . . . . . 14
5 11101 29
6 . . . 11011 . . . . . . . . . . . . . 27
7 10110 22
8 . . . . 01101 . . . . . . . . . . . . 13
9 11010 26
10 . . . . . 10101 . . . . . . . . . . . 21
11 01011 11
12 . . . . . . 10111 . . . . . . . . . . 23
13 01111 15
14 . . . . . . . 11111 . . . . . . . . . 31
15 11110 30
16 . . . . . . . . 11100 . . . . . . . . 28
17 11001 25
18 . . . . . . . . . 10011 . . . . . . . 19
19 00110 6
20 . . . . . . . . . . 01100 . . . . . . 12
21 11000 24
22 . . . . . . . . . . . 10001 . . . . . 17
23 00010 2
24 . . . . . . . . . . . . 00101 . . . . 5
25 01010 10
26 . . . . . . . . . . . . . 10100 . . . 20
27 01001 9
28 . . . . . . . . . . . . . . 1001|0. . 18
29 001|00 4
30 . . . . . . . . . . . . . . . 01|000 8
31 1|0000 16
</pre>
==B(2, 6)==
B(2, 6) implies 2<span style="vertical-align: super;">6</span> or 64 bit sequences. There are 2^26 or 67,108,864 odd 64-bit sequences with 64 overlapping unique six-bit subsequences, for instance 0x022fdd63cc95386d
<pre>
i 0000001000101111110111010110001111001100100101010011100001101101|00000 s[i]
0 000000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0
1 000001 1
2 . 000010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3 000100 4
4 . . 001000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5 010001 17
6 . . . 100010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7 000101 5
8 . . . . 001011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
9 010111 23
10 . . . . . 101111 . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
11 011111 31
12 . . . . . . 111111 . . . . . . . . . . . . . . . . . . . . . . . . . . 63
13 111110 62
14 . . . . . . . 111101 . . . . . . . . . . . . . . . . . . . . . . . . . 61
15 111011 59
16 . . . . . . . . 110111 . . . . . . . . . . . . . . . . . . . . . . . . 55
17 101110 46
18 . . . . . . . . . 011101 . . . . . . . . . . . . . . . . . . . . . . . 29
19 111010 58
20 . . . . . . . . . . 110101 . . . . . . . . . . . . . . . . . . . . . . 53
21 101011 43
22 . . . . . . . . . . . 010110 . . . . . . . . . . . . . . . . . . . . . 22
23 101100 44
24 . . . . . . . . . . . . 011000 . . . . . . . . . . . . . . . . . . . . 24
25 110001 49
26 . . . . . . . . . . . . . 100011 . . . . . . . . . . . . . . . . . . . 35
27 000111 7
28 . . . . . . . . . . . . . . 001111 . . . . . . . . . . . . . . . . . . 15
29 011110 30
30 . . . . . . . . . . . . . . . 111100 . . . . . . . . . . . . . . . . . 60
31 111001 57
32 . . . . . . . . . . . . . . . . 110011 . . . . . . . . . . . . . . . . 51
33 100110 38
34 . . . . . . . . . . . . . . . . . 001100 . . . . . . . . . . . . . . . 12
35 011001 25
36 . . . . . . . . . . . . . . . . . . 110010 . . . . . . . . . . . . . . 50
37 100100 36
38 . . . . . . . . . . . . . . . . . . . 001001 . . . . . . . . . . . . . 9
39 010010 18
40 . . . . . . . . . . . . . . . . . . . . 100101 . . . . . . . . . . . . 37
41 001010 10
42 . . . . . . . . . . . . . . . . . . . . . 010101 . . . . . . . . . . . 21
43 101010 42
44 . . . . . . . . . . . . . . . . . . . . . . 010100 . . . . . . . . . . 20
45 101001 41
46 . . . . . . . . . . . . . . . . . . . . . . . 010011 . . . . . . . . . 19
47 100111 39
48 . . . . . . . . . . . . . . . . . . . . . . . . 001110 . . . . . . . . 14
49 011100 28
50 . . . . . . . . . . . . . . . . . . . . . . . . . 111000 . . . . . . . 56
51 110000 48
52 . . . . . . . . . . . . . . . . . . . . . . . . . . 100001 . . . . . . 33
53 000011 3
54 . . . . . . . . . . . . . . . . . . . . . . . . . . . 000110 . . . . . 6
55 001101 13
56 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 011011 . . . . 27
57 110110 54
58 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101101 . . . 45
59 01101|0 26
60 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1101|00 . 52
61 101|000 40
62 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 01|0000 16
63 1|00000 32
</pre>
<span id="DeBruijnGraphs"></span>
=De Bruijn Graphs=
A De Bruijn graph is a directed graph representing overlaps between sequences of symbols <ref>[https://en.wikipedia.org/wiki/De_Bruijn_graph De Bruijn graph from Wikipedia]</ref> .
* Each vertex has exactly m incoming and m outgoing edges
* Each n-dimensional de Bruijn graph is the [https://en.wikipedia.org/wiki/Line_graph line digraph] of the (n-1)-dimensional de Bruijn graph
* Each de Bruijn graph is [https://en.wikipedia.org/wiki/Euler_cycle Eulerian] and [https://en.wikipedia.org/wiki/Hamiltonian_graph Hamiltonian]. The Euler cycles and Hamiltonian cycles of these graphs are de Bruijn sequences.
[[FILE:DeBruijn-as-line-digraph.svg|none|border|text-bottom]]
The graph construction of the three smallest binary de Bruijn graphs
==B(2, 4) Graph==
: [[FILE:De bruijn graph-for binary sequence of order 4.svg|none|border|text-bottom]]
: A De Bruijn graph. Every four-digit sequence occurs exactly once if one
: traverses every edge exactly once and returns to one's starting point.
<span id="BruijnGraphChessBoard"></span>
==De Bruijn Graph on a Chess Board==
A directed De Bruijn Graph of B(2, 6) sequences with [[Square Mapping Considerations#LittleEndianRankFileMapping|Little-Endian Rank-File Mapping]] board coordinates (a1 = 0, b1 = 1, h8 = 63). For topology reasons, almost each node (except a1 and h8) of the graph is deconcentrated and appears twice in the form of two reversed binary trees. The leaf outputs join the respective reversed tree. Between c6 and f3 is a direct cycle, since 42 is 2*21 and 21 is (2*42 + 1) % 64, with both six-bit pattern reversed - 010101 (21) versus 101010 (42). The challenge is to traverse the graph in any way to visit each of the 64 nodes aka squares exactly once.
<pre>
+----------------->---------------a1--------------<-----------------+
| | |
| b1 |
| +--------------/ \-------------+ |
| c1 d1 |
^ +-----/ \-----+ +-----/ \-----+ |
| e1 f1 g1 h1 |
| +-/ \-+ +-/ \-+ +-/ \-+ +-/ \-+ |
| a2 b2 c2 d2 e2 f2 g2 h2 |
| a3 b3 c3 d3 e3 |f3| g3 h3 a4 b4 c4 d4 e4 f4 g4 h4 |
+-a5b5c5d5e5f5g5h5a6b6c6d6e6f6g6h6 a7b7c7d7e7f7g7h7a8b8c8d8e8f8 | |
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ | |
| |
+----------------->---------------h8--------------<--------------+ ^
| | |
| g8 |
| +--------------/ \-------------+ |
| f8 e8 |
^ +-----/ \-----+ +-----/ \-----+ |
| d8 c8 b8 a8 |
| +-/ \-+ +-/ \-+ +-/ \-+ +-/ \-+ |
| h7 g7 f7 e7 d7 c7 b7 a7 |
| h6 g6 f6 e6 d6 |c6| b6 a6 h5 g5 f5 e5 d5 c5 b5 a5--+
+-h4g4f4e4d4c4b4a4h3g3f3e3d3c3b3a3 h2g2f2e2d2c2b2a2h1g1f1e1d1c1
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
</pre>
=De Bruijn Networks=
So called De Bruijn Networks with the topology of De Bruijn Graphs have interesting properties in processor and computer networks, for instance as described by [[Rainer Feldmann|Feldmann et al.]] to connect [[Transputer]] networks <ref>[[Rainer Feldmann]], [[Peter Mysliwietz]], [[Burkhard Monien]] ('''1991'''). ''A Fully Distributed Chess Program''. [[Advances in Computer Chess 6]], [http://www.top-5000.nl/ps/A%20fully%20distribuited%20chess%20program.pdf pdf]</ref> <ref>[[Rainer Feldmann]] ('''1993'''). ''Game Tree Search on Massively Parallel Systems'' Phd-Thesis, [http://wwwcs.uni-paderborn.de/fachbereich/AG/monien/PUBLICATIONS/POSTSCRIPTS/feldmann_phd.pdf pdf]</ref> .
=See also=
* [[Nicolaas de Bruijn]]
* [[BitScan#DeBruijnMultiplation|De Bruijn Multiplication]] from [[BitScan]]
* [[De Bruijn Sequence Generator]]
* [[Max Euwe#ProuhetThueMorseSequence|Prouhet–Thue–Morse Sequence]]
* [[Pseudorandom Number Generator]]
=Selected Publications=
==1894==
* Camille Flye Sainte-Marie ('''1894'''). ''Solution to question nr. 48'', L'Intermédiaire des Mathématiciens 1, reproduced in [[Nicolaas de Bruijn]] ('''1975'''). ''Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once''. Technical Report, Technische Hogeschool Eindhoven, [http://alexandria.tue.nl/repository/books/252901.pdf pdf]
==1946==
* [[Nicolaas de Bruijn]] ('''1946'''). ''A Combinatorial Problem''. Koninklijke Nederlandse Akademie v. Wetenschappen 49: 758–764.
* [[Jack Good]] ('''1946'''). ''[http://jlms.oxfordjournals.org/cgi/content/citation/s1-21/3/167 Normal Recurring Decimals]''. [http://www.lms.ac.uk/publications/jlms Journal of the London Mathematical Society] <ref>[https://en.wikipedia.org/wiki/Recurring_decimal Recurring decimal from Wikipedia]</ref>
==1950 ...==
* [[Mathematician#LRFord|Lester Randolph Ford, Jr.]] ('''1957'''). ''A Cyclic Arrangement of M-Tuples''. Report No. P-1071. [https://en.wikipedia.org/wiki/RAND_Corporation Rand Corporation]
* [[Mathematician#SMGolomb|Solomon W. Golomb]] ('''1967, 1982'''). ''[https://catalog.hathitrust.org/Record/000466600 Shift Register Sequences]''. Holden-Day Inc., revised 2nd edition, [https://en.wikipedia.org/wiki/Aegean_Park_Press Aegean Park Press]
* [[Mathematician#HMFredricksen|Harold M. Fredricksen]] ('''1968'''). ''Disjoint Cycles from the de Bruijn Graph''. Ph.D. thesis, [[University of Southern California]], advisor [[Mathematician#SMGolomb|Solomon Wolf Golomb]]
==1970 ...==
* [[Mathematician#HMFredricksen|Harold M. Fredricksen]] ('''1970'''). ''The lexicographically least de Bruijn cycle''. [https://en.wikipedia.org/wiki/Journal_of_Combinatorial_Theory Journal of Combinatorial Theory], Vol. 9, No. 1
* [[Mathematician#ALempel|Abraham Lempel]] ('''1970'''). ''On a Homomorphism of the De Bruijn Graph and Its Applications to the Design of Feedback Shift Registers''. [[IEEE#TOC|IEEE Transactions on Computers]], Vol. 19, No. 12
* [[Mathematician#HMFredricksen|Harold M. Fredricksen]] ('''1972'''). ''Generation of the Ford Sequence of Length 2<span style="vertical-align: super;">n</span>, n Large.'' JPL Technical Report 32-1526, Vol. IV, [http://tmo.jpl.nasa.gov/progress_report2/IV/IVM.PDF pdf]
==1990 ...==
* [http://dblp.uni-trier.de/pers/hd/h/Huang:Yuejiang Yuejiang Huang] ('''1990'''). ''[http://www.sciencedirect.com/science/article/pii/019667749090028D A new algorithm for the generation of binary de Bruijn sequences]''. [ftp://ftp.math.utah.edu/pub/tex/bib/toc/jalg.html#11(1):March:1990 Journal of Algorithms, Vol. 11, No. 1]
* [[Mathematician#CJMitchell|Chris J. Mitchell]], [[Mathematician#TEtzion|Tuvi Etzion]], [[Mathematician#KGPaterson|Kenneth G. Paterson]] ('''1996'''). ''A method for constructing decodable de Bruijn Sequences''. [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B603C5EDF04C7DF00B0D604AB96E3226?doi=10.1.1.14.674&rep=rep1&type=pdf pdf] via [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.674 CiteSeerX]
* [http://www.ece.uc.edu/~annexste/UC_Pages/Dr._Fred_Annexsteins_Computer_Science_Department_Homepage_____.html Fred S. Annexstein] ('''1997'''). ''Generating De Bruijn Sequences: An Efficient Implementation.'' [[IEEE#TOC|IEEE Transactions on Computers]], Vol. 46, No. 2, [http://www.ece.uc.edu/~annexste/Papers/Annexstein-GeneratingDB.pdf pdf], [http://www.ece.uc.edu/~annexste/Papers/fastdb.c Supplement: C-code implementation]
* [[Charles Leiserson|Charles E. Leiserson]], [[Harald Prokop]], [[Keith H. Randall]] ('''1998'''). ''Using de Bruijn Sequences to Index a 1 in a Computer Word''. [http://supertech.csail.mit.edu/papers/debruijn.pdf pdf]
==2000 ...==
* [http://research.haifa.ac.il/%7Eevolut/ Vladimir Raphael Rosenfeld] ('''2002'''). ''Enumerating De Bruijn Sequences''. [http://evolution.haifa.ac.il/ Institute of Evolution], [https://en.wikipedia.org/wiki/University_of_Haifa University of Haifa], [http://www.stefangeens.com/br13.pdf pdf]
* [http://research.haifa.ac.il/%7Eevolut/ Vladimir Raphael Rosenfeld] ('''2002'''). ''Enumerating Kautz Sequences''. [http://evolution.haifa.ac.il/ Institute of Evolution], [https://en.wikipedia.org/wiki/University_of_Haifa University of Haifa], [http://elib.mi.sanu.ac.rs/files/journals/kjm/24/d003download.pdf pdf]
* [[Mathematician#ADatta|Anwitaman Datta]], [[Mathematician#SGirdzijauskas|Sarunas Girdzijauskas]], [[Mathematician#KAberer|Karl Aberer]] ('''2004'''). ''On de Bruijn routing in distributed hash tables: There and back again''. P2P2004, The 4th IEEE International Conference on Peer-to-Peer Computing, [http://www.ida.liu.se/conferences/p2p/p2p2004/papers/datta.pdf pdf]
* [[Mathematician#PFraigniaud|Pierre Fraigniaud]], [[Mathematician#PGauron|Philippe Gauron]] ('''2005'''). ''D2B: a de Bruijn Based Content-Addressable Network''. [http://www.liafa.jussieu.fr/%7Epierref/POSTSCRIPTS/D2B.pdf pdf]
* [http://www.math.umn.edu/%7Earmstron/ Drew Armstrong] ('''2006'''). ''De Bruijn Sequences''. [http://www.math.umn.edu/%7Earmstron/5707/DeBruijn.pdf pdf]
* [[Mathematician#JBerstel|Jean Berstel]], [[Mathematician#DPerrin|Dominique Perrin]] ('''2007'''). ''The origins of combinatorics on words''. [http://www.informatik.uni-trier.de/~ley/db/journals/ejc/ejc28.html European Journal of Combinatorics 28], [http://www-igm.univ-mlv.fr/~berstel/Articles/2007Origins.pdf pdf]
==2010 ...==
* [http://www.cs.pu.edu.tw/~yawlin/ Yaw-Ling Lin], [https://sites.google.com/site/charlesbward/ Charles B. Ward], [http://dblp.uni-trier.de/pers/hd/j/Jain:Bharat Bharat Jain], [[Steven Skiena]] ('''2011'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-642-22300-6_50 Constructing Orthogonal de Bruijn Sequences]''. [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science LNCS] 6844, [http://dblp.uni-trier.de/db/conf/wads/wads2011.html#LinWJS11 WADS 2011]
* [https://www.researchgate.net/profile/Zuling_Chang Zuling Chang], [[Mathematician#MFEzerman|Martianus Frederic Ezerman]], [[Mathematician#SanLing|San Ling]], [[Mathematician#HuaxiongWang|Huaxiong Wang]] ('''2016'''). ''On Binary de Bruijn Sequences from LFSRs with Arbitrary Characteristic Polynomials''. [https://arxiv.org/abs/1611.10088 arXiv:1611.10088] <ref>[https://en.wikipedia.org/wiki/Linear-feedback_shift_register LFSR from Wikipedia]</ref>
* [https://www.researchgate.net/profile/Zuling_Chang Zuling Chang], [[Mathematician#MFEzerman|Martianus Frederic Ezerman]], [https://www.linkedin.com/in/adamas-aqsa-fahreza-08927995/ Adamas Aqsa Fahreza], [[Mathematician#SanLing|San Ling]], [[Mathematician#HuaxiongWang|Huaxiong Wang]] ('''2017'''). ''Large Order Binary de Bruijn Sequences via Zech's Logarithms''. [https://arxiv.org/abs/1705.03150 arXiv:1705.03150] <ref>[https://en.wikipedia.org/wiki/Zech%27s_logarithm Zech's logarithm from Wikipedia]</ref>
* [[Mathematician#JSawada|Joe Sawada]], [[Mathematician#AWilliams|Aaron Williams]] ('''2017'''). ''[https://dl.acm.org/citation.cfm?id=3085499 Practical Algorithms to Rank Necklaces, Lyndon Words, and de Bruijn Sequences]''. [https://www.journals.elsevier.com/journal-of-discrete-algorithms/ Journal of Discrete Algorithms], Vol. 43, No. C, [http://www.socs.uoguelph.ca/~sawada/papers/ranking.pdf pdf]
=External Links=
* [https://en.wikipedia.org/wiki/De_Bruijn_sequence De Bruijn sequence from Wikipedia]
* [https://en.wikipedia.org/wiki/De_Bruijn_graph De Bruijn graph from Wikipedia]
* [https://en.wikipedia.org/wiki/Kautz_graph Kautz graph from Wikipedia]
* [https://en.wikipedia.org/wiki/Koorde Koorde from Wikipedia]
* [https://oeis.org/A166315 A166315 - OEIS]
* [https://en.wikipedia.org/wiki/Lyndon_word Lyndon word from Wikipedia]
* [[Videos#If|If]] - [https://en.wikipedia.org/wiki/If_3 Forgotten Roads], [https://en.wikipedia.org/wiki/Beat-Club Beat-Club] [https://www.youtube.com/watch?v=V1BcLk19hVw #71], September 25, 1971, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=JFTX4cwxJLI|alignment=left|valignment=top}}
=References=
<references />
'''[[Data|Up one Level]]'''
[[Category:M. C. Escher]]
[[FILE:LW441-MC-Escher-Moebius-Strip-II-1963.jpg|border|right|thumb|link=http://www.mcescher.com/gallery/recognition-success/mobius-strip-ii/|[[Arts#Escher|M.C. Escher]] - Möbius Strip II <ref>[http://www.mcescher.com/gallery/recognition-success/ M.C. Escher - The Official Website – Recognition & Success] </ref> <ref>[https://en.wikipedia.org/wiki/M%C3%B6bius_strip Moebius Strip from Wikipedia]</ref> ]]
In [https://en.wikipedia.org/wiki/Combinatorics combinatorial mathematics], a '''k'''-ary '''De Bruijn Sequence''' B(k, n) of order '''n''', named after the Dutch mathematician [[Nicolaas de Bruijn]], is a cyclic sequence of a given alphabet '''A''' with size '''k''' for which every possible subsequence of length '''n''' in '''A''' appears as a sequence of consecutive characters exactly once <ref>[https://en.wikipedia.org/wiki/De_Bruijn_sequence De Bruijn sequence from Wikipedia]</ref>.
In chess programming there are applications of de Bruijn sequences with the Binary alphabet, in [[Hash Table|hashing]] sets like [[Piece-Sets]] or Square-sets, also called [[Bitboards]], most notably in [[BitScan#DeBruijnMultiplation|Bit scanning]] <ref>[[Charles Leiserson|Charles E. Leiserson]], [[Harald Prokop]], [[Keith H. Randall]] ('''1998'''). ''Using de Bruijn Sequences to Index a 1 in a Computer Word''. [http://supertech.csail.mit.edu/papers/debruijn.pdf pdf]</ref> .
=Binary alphabet=
According to De Bruijn himself <ref>[[Nicolaas de Bruijn]] ('''1975'''). ''Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once''. Technical Report, Technische Hogeschool Eindhoven, [http://alexandria.tue.nl/repository/books/252901.pdf pdf]</ref> , the existence of De Bruijn sequences were first proved, for the case of alphabets with two elements, by '''Camille Flye Sainte-Marie''' in 1894, whereas the generalization to larger alphabets is originally due to [[Mathematician#Ehrenfest|Tanja van Ardenne-Ehrenfest]] <ref>[[Nicolaas de Bruijn]] ('''1985'''). ''In Memoriam T. van Ardenne-Ehrenfest''. [http://alexandria.tue.nl/repository/freearticles/597575.pdf pdf]</ref> and himself.
Binary digits or [[Bit|bits]] inside a computer word are B(2, n) de Bruijn sequences, with '''2<span style="vertical-align: super;">n</span>''' bits length and equal number of ones and zeros, with '''2<span style="vertical-align: super;">n</span>''' overlapping unique '''n'''-bit subsequences. Since the sequences are cyclic and '''n-1''' subsequences need to wrap, we restrict them to at least '''n-1''' leading zeros, to make them overlap the hidden trailing "zeros".
Odd sequences have '''n''' leading zeros. The even ones with '''n-1''' leading zeros are rotated (shifted) left by one. Due to '''n''' leading zeros of these odd sequences we further consider, the first subsequence['''0'''] is zero. Due to the overlapping, each subsequence['''i'''+1] is dependent from subsequence['''i''']. The doubled value incremented by either zero or one. Since subsequence['''0'''] is zero, a second zero subsequence with six consecutive binary zeros is further prohibited, and subsequence['''1'''] must be one. Subsequence index '''i''' is counted from most significant bit left to right, and therefor reversed from usual bit-index. A modulo '''2<span style="vertical-align: super;">n</span>''' restricts all subsequences to '''n''' bits:
s[i+1] = (2s[i] + (0|1)) mod (2<span style="vertical-align: super;">n</span>)
The [https://en.wikipedia.org/wiki/Cardinality Cardinality] of all distinct B(2, n) de Bruijn sequences is:
|B(2, n)| = 2<span style="vertical-align: super;">(2<span style="vertical-align: super;">n-1</span> - n)</span>
{| class="wikitable"
|-
! n
! 2<span style="vertical-align: super;">n-1</span> - n
! |B(2, n)|
|-
| style="text-align:center;" | 1
| style="text-align:right;" | 0
| style="text-align:right;" | 1
|-
| style="text-align:center;" | 2
| style="text-align:right;" | 0
| style="text-align:right;" | 1
|-
| style="text-align:center;" | 3
| style="text-align:right;" | 1
| style="text-align:right;" | 2
|-
| style="text-align:center;" | 4
| style="text-align:right;" | 4
| style="text-align:right;" | 16
|-
| style="text-align:center;" | 5
| style="text-align:right;" | 11
| style="text-align:right;" | 2,048
|-
| style="text-align:center;" | 6
| style="text-align:right;" | 26
| style="text-align:right;" | 67,108,864
|-
| style="text-align:center;" | 7
| style="text-align:right;" | 57
| style="text-align:right;" | 144,115,188,075,855,872
|-
| style="text-align:center;" | 8
| style="text-align:right;" | 120
| style="text-align:right;" | ~1.329e+36
|}
==B(2, 1)==
The two one-bit subsequences obviously do not overlap:
<pre>
i 01 s[i]
0 0 0
1 1 1
</pre>
==B(2, 2)==
B(2, 2) implies 2<span style="vertical-align: super;">2</span> or 4-bit sequences. There is one odd four-bit de Bruijn sequence with four overlapping unique two-bit subsequences, 0x3.
<pre>
i 0011|0 s[i]
0 00 . . . 0
1 01 1
2 . 11 . . 3
3 1|0 2
</pre>
==B(2, 3)==
B(2, 3) implies 2<span style="vertical-align: super;">3</span> or 8-bit sequences. There are two odd eight-bit sequences with eight overlapping unique three-bit subsequences, 0x17 and 0x1d. Note that the five relevant bits are reversed.
<pre>
i 00010111|00 s[i] i 00011101|00 s[i]
0 000 . . . . 0 0 000 . . . . 0
1 001 1 1 001 1
2 . 010 . . . 2 2 . 011 . . . 3
3 101 5 3 111 7
4 . . 011 . . 3 4 . . 110 . . 6
5 111 7 5 101 5
6 . . . 11|0 6 6 . . . 01|0 2
7 1|00 4 7 1|00 4
</pre>
==B(2, 4)==
B(2, 4) implies 2<span style="vertical-align: super;">4</span> or 16 bit sequences. There are 16 odd 16-bit sequences with 16 overlapping unique four-bit subsequences:
<pre>
0x09af 0000100110101111
0x09eb 0000100111101011
0x0a6f 0000101001101111
0x0a7b 0000101001111011
0x0b3d 0000101100111101
0x0b4f 0000101101001111
0x0bcd 0000101111001101
0x0bd3 0000101111010011
0x0cbd 0000110010111101
0x0d2f 0000110100101111
0x0d79 0000110101111001
0x0de5 0000110111100101
0x0f2d 0000111100101101
0x0f4b 0000111101001011
0x0f59 0000111101011001
0x0f65 0000111101100101
</pre>
for instance 0x0d2f:
<pre>
i 0000110100101111|000 s[i]
0 0000 . . . . . . . . 0
1 0001 1
2 . 0011 . . . . . . . 3
3 0110 6
4 . . 1101 . . . . . . 13
5 1010 10
6 . . . 0100 . . . . . 4
7 1001 9
8 . . . . 0010 . . . . 2
9 0101 5
10 . . . . . 1011 . . . 11
11 0111 7
12 . . . . . . 1111 . . 15
13 111|0 14
14 . . . . . . . 11|00 12
15 1|000 8
</pre>
==B(2, 5)==
B(2, 5) implies 2<span style="vertical-align: super;">5</span> or 32 bit sequences. There are 2^11 or 2,048 odd 32-bit sequences with 32 overlapping unique five-bit subsequences, for instance 0x076be629
<pre>
i 00000111011010111110011000101001|0000 s[i]
0 00000 . . . . . . . . . . . . . . . . 0
1 00001 1
2 . 00011 . . . . . . . . . . . . . . . 3
3 00111 7
4 . . 01110 . . . . . . . . . . . . . . 14
5 11101 29
6 . . . 11011 . . . . . . . . . . . . . 27
7 10110 22
8 . . . . 01101 . . . . . . . . . . . . 13
9 11010 26
10 . . . . . 10101 . . . . . . . . . . . 21
11 01011 11
12 . . . . . . 10111 . . . . . . . . . . 23
13 01111 15
14 . . . . . . . 11111 . . . . . . . . . 31
15 11110 30
16 . . . . . . . . 11100 . . . . . . . . 28
17 11001 25
18 . . . . . . . . . 10011 . . . . . . . 19
19 00110 6
20 . . . . . . . . . . 01100 . . . . . . 12
21 11000 24
22 . . . . . . . . . . . 10001 . . . . . 17
23 00010 2
24 . . . . . . . . . . . . 00101 . . . . 5
25 01010 10
26 . . . . . . . . . . . . . 10100 . . . 20
27 01001 9
28 . . . . . . . . . . . . . . 1001|0. . 18
29 001|00 4
30 . . . . . . . . . . . . . . . 01|000 8
31 1|0000 16
</pre>
==B(2, 6)==
B(2, 6) implies 2<span style="vertical-align: super;">6</span> or 64 bit sequences. There are 2^26 or 67,108,864 odd 64-bit sequences with 64 overlapping unique six-bit subsequences, for instance 0x022fdd63cc95386d
<pre>
i 0000001000101111110111010110001111001100100101010011100001101101|00000 s[i]
0 000000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0
1 000001 1
2 . 000010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3 000100 4
4 . . 001000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5 010001 17
6 . . . 100010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7 000101 5
8 . . . . 001011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
9 010111 23
10 . . . . . 101111 . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
11 011111 31
12 . . . . . . 111111 . . . . . . . . . . . . . . . . . . . . . . . . . . 63
13 111110 62
14 . . . . . . . 111101 . . . . . . . . . . . . . . . . . . . . . . . . . 61
15 111011 59
16 . . . . . . . . 110111 . . . . . . . . . . . . . . . . . . . . . . . . 55
17 101110 46
18 . . . . . . . . . 011101 . . . . . . . . . . . . . . . . . . . . . . . 29
19 111010 58
20 . . . . . . . . . . 110101 . . . . . . . . . . . . . . . . . . . . . . 53
21 101011 43
22 . . . . . . . . . . . 010110 . . . . . . . . . . . . . . . . . . . . . 22
23 101100 44
24 . . . . . . . . . . . . 011000 . . . . . . . . . . . . . . . . . . . . 24
25 110001 49
26 . . . . . . . . . . . . . 100011 . . . . . . . . . . . . . . . . . . . 35
27 000111 7
28 . . . . . . . . . . . . . . 001111 . . . . . . . . . . . . . . . . . . 15
29 011110 30
30 . . . . . . . . . . . . . . . 111100 . . . . . . . . . . . . . . . . . 60
31 111001 57
32 . . . . . . . . . . . . . . . . 110011 . . . . . . . . . . . . . . . . 51
33 100110 38
34 . . . . . . . . . . . . . . . . . 001100 . . . . . . . . . . . . . . . 12
35 011001 25
36 . . . . . . . . . . . . . . . . . . 110010 . . . . . . . . . . . . . . 50
37 100100 36
38 . . . . . . . . . . . . . . . . . . . 001001 . . . . . . . . . . . . . 9
39 010010 18
40 . . . . . . . . . . . . . . . . . . . . 100101 . . . . . . . . . . . . 37
41 001010 10
42 . . . . . . . . . . . . . . . . . . . . . 010101 . . . . . . . . . . . 21
43 101010 42
44 . . . . . . . . . . . . . . . . . . . . . . 010100 . . . . . . . . . . 20
45 101001 41
46 . . . . . . . . . . . . . . . . . . . . . . . 010011 . . . . . . . . . 19
47 100111 39
48 . . . . . . . . . . . . . . . . . . . . . . . . 001110 . . . . . . . . 14
49 011100 28
50 . . . . . . . . . . . . . . . . . . . . . . . . . 111000 . . . . . . . 56
51 110000 48
52 . . . . . . . . . . . . . . . . . . . . . . . . . . 100001 . . . . . . 33
53 000011 3
54 . . . . . . . . . . . . . . . . . . . . . . . . . . . 000110 . . . . . 6
55 001101 13
56 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 011011 . . . . 27
57 110110 54
58 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101101 . . . 45
59 01101|0 26
60 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1101|00 . 52
61 101|000 40
62 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 01|0000 16
63 1|00000 32
</pre>
<span id="DeBruijnGraphs"></span>
=De Bruijn Graphs=
A De Bruijn graph is a directed graph representing overlaps between sequences of symbols <ref>[https://en.wikipedia.org/wiki/De_Bruijn_graph De Bruijn graph from Wikipedia]</ref> .
* Each vertex has exactly m incoming and m outgoing edges
* Each n-dimensional de Bruijn graph is the [https://en.wikipedia.org/wiki/Line_graph line digraph] of the (n-1)-dimensional de Bruijn graph
* Each de Bruijn graph is [https://en.wikipedia.org/wiki/Euler_cycle Eulerian] and [https://en.wikipedia.org/wiki/Hamiltonian_graph Hamiltonian]. The Euler cycles and Hamiltonian cycles of these graphs are de Bruijn sequences.
[[FILE:DeBruijn-as-line-digraph.svg|none|border|text-bottom]]
The graph construction of the three smallest binary de Bruijn graphs
==B(2, 4) Graph==
: [[FILE:De bruijn graph-for binary sequence of order 4.svg|none|border|text-bottom]]
: A De Bruijn graph. Every four-digit sequence occurs exactly once if one
: traverses every edge exactly once and returns to one's starting point.
<span id="BruijnGraphChessBoard"></span>
==De Bruijn Graph on a Chess Board==
A directed De Bruijn Graph of B(2, 6) sequences with [[Square Mapping Considerations#LittleEndianRankFileMapping|Little-Endian Rank-File Mapping]] board coordinates (a1 = 0, b1 = 1, h8 = 63). For topology reasons, almost each node (except a1 and h8) of the graph is deconcentrated and appears twice in the form of two reversed binary trees. The leaf outputs join the respective reversed tree. Between c6 and f3 is a direct cycle, since 42 is 2*21 and 21 is (2*42 + 1) % 64, with both six-bit pattern reversed - 010101 (21) versus 101010 (42). The challenge is to traverse the graph in any way to visit each of the 64 nodes aka squares exactly once.
<pre>
+----------------->---------------a1--------------<-----------------+
| | |
| b1 |
| +--------------/ \-------------+ |
| c1 d1 |
^ +-----/ \-----+ +-----/ \-----+ |
| e1 f1 g1 h1 |
| +-/ \-+ +-/ \-+ +-/ \-+ +-/ \-+ |
| a2 b2 c2 d2 e2 f2 g2 h2 |
| a3 b3 c3 d3 e3 |f3| g3 h3 a4 b4 c4 d4 e4 f4 g4 h4 |
+-a5b5c5d5e5f5g5h5a6b6c6d6e6f6g6h6 a7b7c7d7e7f7g7h7a8b8c8d8e8f8 | |
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ | |
| |
+----------------->---------------h8--------------<--------------+ ^
| | |
| g8 |
| +--------------/ \-------------+ |
| f8 e8 |
^ +-----/ \-----+ +-----/ \-----+ |
| d8 c8 b8 a8 |
| +-/ \-+ +-/ \-+ +-/ \-+ +-/ \-+ |
| h7 g7 f7 e7 d7 c7 b7 a7 |
| h6 g6 f6 e6 d6 |c6| b6 a6 h5 g5 f5 e5 d5 c5 b5 a5--+
+-h4g4f4e4d4c4b4a4h3g3f3e3d3c3b3a3 h2g2f2e2d2c2b2a2h1g1f1e1d1c1
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
</pre>
=De Bruijn Networks=
So called De Bruijn Networks with the topology of De Bruijn Graphs have interesting properties in processor and computer networks, for instance as described by [[Rainer Feldmann|Feldmann et al.]] to connect [[Transputer]] networks <ref>[[Rainer Feldmann]], [[Peter Mysliwietz]], [[Burkhard Monien]] ('''1991'''). ''A Fully Distributed Chess Program''. [[Advances in Computer Chess 6]], [http://www.top-5000.nl/ps/A%20fully%20distribuited%20chess%20program.pdf pdf]</ref> <ref>[[Rainer Feldmann]] ('''1993'''). ''Game Tree Search on Massively Parallel Systems'' Phd-Thesis, [http://wwwcs.uni-paderborn.de/fachbereich/AG/monien/PUBLICATIONS/POSTSCRIPTS/feldmann_phd.pdf pdf]</ref> .
=See also=
* [[Nicolaas de Bruijn]]
* [[BitScan#DeBruijnMultiplation|De Bruijn Multiplication]] from [[BitScan]]
* [[De Bruijn Sequence Generator]]
* [[Max Euwe#ProuhetThueMorseSequence|Prouhet–Thue–Morse Sequence]]
* [[Pseudorandom Number Generator]]
=Selected Publications=
==1894==
* Camille Flye Sainte-Marie ('''1894'''). ''Solution to question nr. 48'', L'Intermédiaire des Mathématiciens 1, reproduced in [[Nicolaas de Bruijn]] ('''1975'''). ''Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once''. Technical Report, Technische Hogeschool Eindhoven, [http://alexandria.tue.nl/repository/books/252901.pdf pdf]
==1946==
* [[Nicolaas de Bruijn]] ('''1946'''). ''A Combinatorial Problem''. Koninklijke Nederlandse Akademie v. Wetenschappen 49: 758–764.
* [[Jack Good]] ('''1946'''). ''[http://jlms.oxfordjournals.org/cgi/content/citation/s1-21/3/167 Normal Recurring Decimals]''. [http://www.lms.ac.uk/publications/jlms Journal of the London Mathematical Society] <ref>[https://en.wikipedia.org/wiki/Recurring_decimal Recurring decimal from Wikipedia]</ref>
==1950 ...==
* [[Mathematician#LRFord|Lester Randolph Ford, Jr.]] ('''1957'''). ''A Cyclic Arrangement of M-Tuples''. Report No. P-1071. [https://en.wikipedia.org/wiki/RAND_Corporation Rand Corporation]
* [[Mathematician#SMGolomb|Solomon W. Golomb]] ('''1967, 1982'''). ''[https://catalog.hathitrust.org/Record/000466600 Shift Register Sequences]''. Holden-Day Inc., revised 2nd edition, [https://en.wikipedia.org/wiki/Aegean_Park_Press Aegean Park Press]
* [[Mathematician#HMFredricksen|Harold M. Fredricksen]] ('''1968'''). ''Disjoint Cycles from the de Bruijn Graph''. Ph.D. thesis, [[University of Southern California]], advisor [[Mathematician#SMGolomb|Solomon Wolf Golomb]]
==1970 ...==
* [[Mathematician#HMFredricksen|Harold M. Fredricksen]] ('''1970'''). ''The lexicographically least de Bruijn cycle''. [https://en.wikipedia.org/wiki/Journal_of_Combinatorial_Theory Journal of Combinatorial Theory], Vol. 9, No. 1
* [[Mathematician#ALempel|Abraham Lempel]] ('''1970'''). ''On a Homomorphism of the De Bruijn Graph and Its Applications to the Design of Feedback Shift Registers''. [[IEEE#TOC|IEEE Transactions on Computers]], Vol. 19, No. 12
* [[Mathematician#HMFredricksen|Harold M. Fredricksen]] ('''1972'''). ''Generation of the Ford Sequence of Length 2<span style="vertical-align: super;">n</span>, n Large.'' JPL Technical Report 32-1526, Vol. IV, [http://tmo.jpl.nasa.gov/progress_report2/IV/IVM.PDF pdf]
==1990 ...==
* [http://dblp.uni-trier.de/pers/hd/h/Huang:Yuejiang Yuejiang Huang] ('''1990'''). ''[http://www.sciencedirect.com/science/article/pii/019667749090028D A new algorithm for the generation of binary de Bruijn sequences]''. [ftp://ftp.math.utah.edu/pub/tex/bib/toc/jalg.html#11(1):March:1990 Journal of Algorithms, Vol. 11, No. 1]
* [[Mathematician#CJMitchell|Chris J. Mitchell]], [[Mathematician#TEtzion|Tuvi Etzion]], [[Mathematician#KGPaterson|Kenneth G. Paterson]] ('''1996'''). ''A method for constructing decodable de Bruijn Sequences''. [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=B603C5EDF04C7DF00B0D604AB96E3226?doi=10.1.1.14.674&rep=rep1&type=pdf pdf] via [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.674 CiteSeerX]
* [http://www.ece.uc.edu/~annexste/UC_Pages/Dr._Fred_Annexsteins_Computer_Science_Department_Homepage_____.html Fred S. Annexstein] ('''1997'''). ''Generating De Bruijn Sequences: An Efficient Implementation.'' [[IEEE#TOC|IEEE Transactions on Computers]], Vol. 46, No. 2, [http://www.ece.uc.edu/~annexste/Papers/Annexstein-GeneratingDB.pdf pdf], [http://www.ece.uc.edu/~annexste/Papers/fastdb.c Supplement: C-code implementation]
* [[Charles Leiserson|Charles E. Leiserson]], [[Harald Prokop]], [[Keith H. Randall]] ('''1998'''). ''Using de Bruijn Sequences to Index a 1 in a Computer Word''. [http://supertech.csail.mit.edu/papers/debruijn.pdf pdf]
==2000 ...==
* [http://research.haifa.ac.il/%7Eevolut/ Vladimir Raphael Rosenfeld] ('''2002'''). ''Enumerating De Bruijn Sequences''. [http://evolution.haifa.ac.il/ Institute of Evolution], [https://en.wikipedia.org/wiki/University_of_Haifa University of Haifa], [http://www.stefangeens.com/br13.pdf pdf]
* [http://research.haifa.ac.il/%7Eevolut/ Vladimir Raphael Rosenfeld] ('''2002'''). ''Enumerating Kautz Sequences''. [http://evolution.haifa.ac.il/ Institute of Evolution], [https://en.wikipedia.org/wiki/University_of_Haifa University of Haifa], [http://elib.mi.sanu.ac.rs/files/journals/kjm/24/d003download.pdf pdf]
* [[Mathematician#ADatta|Anwitaman Datta]], [[Mathematician#SGirdzijauskas|Sarunas Girdzijauskas]], [[Mathematician#KAberer|Karl Aberer]] ('''2004'''). ''On de Bruijn routing in distributed hash tables: There and back again''. P2P2004, The 4th IEEE International Conference on Peer-to-Peer Computing, [http://www.ida.liu.se/conferences/p2p/p2p2004/papers/datta.pdf pdf]
* [[Mathematician#PFraigniaud|Pierre Fraigniaud]], [[Mathematician#PGauron|Philippe Gauron]] ('''2005'''). ''D2B: a de Bruijn Based Content-Addressable Network''. [http://www.liafa.jussieu.fr/%7Epierref/POSTSCRIPTS/D2B.pdf pdf]
* [http://www.math.umn.edu/%7Earmstron/ Drew Armstrong] ('''2006'''). ''De Bruijn Sequences''. [http://www.math.umn.edu/%7Earmstron/5707/DeBruijn.pdf pdf]
* [[Mathematician#JBerstel|Jean Berstel]], [[Mathematician#DPerrin|Dominique Perrin]] ('''2007'''). ''The origins of combinatorics on words''. [http://www.informatik.uni-trier.de/~ley/db/journals/ejc/ejc28.html European Journal of Combinatorics 28], [http://www-igm.univ-mlv.fr/~berstel/Articles/2007Origins.pdf pdf]
==2010 ...==
* [http://www.cs.pu.edu.tw/~yawlin/ Yaw-Ling Lin], [https://sites.google.com/site/charlesbward/ Charles B. Ward], [http://dblp.uni-trier.de/pers/hd/j/Jain:Bharat Bharat Jain], [[Steven Skiena]] ('''2011'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-642-22300-6_50 Constructing Orthogonal de Bruijn Sequences]''. [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science LNCS] 6844, [http://dblp.uni-trier.de/db/conf/wads/wads2011.html#LinWJS11 WADS 2011]
* [https://www.researchgate.net/profile/Zuling_Chang Zuling Chang], [[Mathematician#MFEzerman|Martianus Frederic Ezerman]], [[Mathematician#SanLing|San Ling]], [[Mathematician#HuaxiongWang|Huaxiong Wang]] ('''2016'''). ''On Binary de Bruijn Sequences from LFSRs with Arbitrary Characteristic Polynomials''. [https://arxiv.org/abs/1611.10088 arXiv:1611.10088] <ref>[https://en.wikipedia.org/wiki/Linear-feedback_shift_register LFSR from Wikipedia]</ref>
* [https://www.researchgate.net/profile/Zuling_Chang Zuling Chang], [[Mathematician#MFEzerman|Martianus Frederic Ezerman]], [https://www.linkedin.com/in/adamas-aqsa-fahreza-08927995/ Adamas Aqsa Fahreza], [[Mathematician#SanLing|San Ling]], [[Mathematician#HuaxiongWang|Huaxiong Wang]] ('''2017'''). ''Large Order Binary de Bruijn Sequences via Zech's Logarithms''. [https://arxiv.org/abs/1705.03150 arXiv:1705.03150] <ref>[https://en.wikipedia.org/wiki/Zech%27s_logarithm Zech's logarithm from Wikipedia]</ref>
* [[Mathematician#JSawada|Joe Sawada]], [[Mathematician#AWilliams|Aaron Williams]] ('''2017'''). ''[https://dl.acm.org/citation.cfm?id=3085499 Practical Algorithms to Rank Necklaces, Lyndon Words, and de Bruijn Sequences]''. [https://www.journals.elsevier.com/journal-of-discrete-algorithms/ Journal of Discrete Algorithms], Vol. 43, No. C, [http://www.socs.uoguelph.ca/~sawada/papers/ranking.pdf pdf]
=External Links=
* [https://en.wikipedia.org/wiki/De_Bruijn_sequence De Bruijn sequence from Wikipedia]
* [https://en.wikipedia.org/wiki/De_Bruijn_graph De Bruijn graph from Wikipedia]
* [https://en.wikipedia.org/wiki/Kautz_graph Kautz graph from Wikipedia]
* [https://en.wikipedia.org/wiki/Koorde Koorde from Wikipedia]
* [https://oeis.org/A166315 A166315 - OEIS]
* [https://en.wikipedia.org/wiki/Lyndon_word Lyndon word from Wikipedia]
* [[Videos#If|If]] - [https://en.wikipedia.org/wiki/If_3 Forgotten Roads], [https://en.wikipedia.org/wiki/Beat-Club Beat-Club] [https://www.youtube.com/watch?v=V1BcLk19hVw #71], September 25, 1971, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=JFTX4cwxJLI|alignment=left|valignment=top}}
=References=
<references />
'''[[Data|Up one Level]]'''
[[Category:M. C. Escher]]
