for general alphabet size in place of 2, with an algorithm for constructing them. Finally, when in 1944 Kees Posthumus conjectured the count for binary sequences, de Bruijn proved the conjecture in 1946, through which the problem became well-known. Karl Popper independently describes these objects in his The Logic of Scientific Discovery (1934), calling them "shortest random-like sequences". Examples Taking A = {0, 1}, there are two distinct B(2, 3): 00010111 and 11101000, one being the reverse or negation of the other. Two of the 16 possible B(2, 4) in the same alphabet are 0000100110101111 and 0000111101100101. Two of the 2048 possible B(2, 5) in the same alphabet are 00000100011001010011101011011111 and 00000101001000111110111001101011. Construction The de Bruijn sequences can be constructed by taking a Hamiltonian path of an n-dimensional de Bruijn graph over k symbols (or equivalently, an Eulerian cycle of an (n − 1)-dimensional de Bruijn graph). An alternative construction involves concatenating together, in lexicographic order, all the Lyndon words whose length divides n. An inverse Burrows–Wheeler transform can be used to generate the required Lyndon words in lexicographic order. De Bruijn sequences can also be constructed using shift registers or via finite fields. Example using de Bruijn graph Goal: to construct a B(2, 4) de Bruijn sequence of length 24 = 16 using Eulerian (n − 1 = 4 − 1 = 3) 3-D de Bruijn graph cycle. Each edge in this 3-dimensional de Bruijn graph corresponds to a sequence of four digits: the three digits that label the vertex that the edge is leaving followed by the one that labels the edge. If one traverses the edge labeled 1 from 000, one arrives at 001, thereby indicating the presence of the subsequence 0001 in the de Bruijn sequence. To traverse each edge exactly once is to use each of the 16 four-digit sequences exactly once. For example, suppose we follow the following Eulerian path through these vertices: 000, 000, 001, 011, 111, 111, 110, 101, 011, 110, 100, 001, 010, 101, 010, 100, 000. These are the output sequences of length k: 0 0 0 0 _ 0 0 0 1 _ _ 0 0 1 1 This corresponds to the following de Bruijn sequence: 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 The eight vertices appear in the sequence in the following way: {0 0 0 0} 1 1