THE FOLD / CHEAT / THE BACKDOOR / THE DE BRUIJN
THE DE BRUIJN
the shortest string holding every code — k^n
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The de Bruijn sequence. The shortest cyclic string that contains every possible length-n word over a k-symbol alphabet, each exactly once. The binary case B(2,3) = 00010111: slide a 3-wide window around the loop and you read off all eight patterns 000, 001, 010, 101, 011, 111, 110, 100 — no repeats, no gaps.
Its length is exactly kn, the theoretical minimum: there are kn windows and each starting position yields one. That makes it a master key. To try every 3-digit binary code on a keypad naively is 8×3 = 24 presses; the de Bruijn string cracks all eight in just 8 presses, because every single new keypress completes a brand-new code. Under the hood it is an Euler circuit through the de Bruijn graph — a walk using every edge exactly once.
LIT verified live: for (k,n) = (2,3),(2,4),(2,5),(3,3),(4,2),(2,6) the constructed sequence has length exactly kn and every one of the kn windows appears exactly once (window.__debruijn.allWindowsOnce). FIG no framing; the minimal length and the exactly-once coverage are real.
Its length is exactly kn, the theoretical minimum: there are kn windows and each starting position yields one. That makes it a master key. To try every 3-digit binary code on a keypad naively is 8×3 = 24 presses; the de Bruijn string cracks all eight in just 8 presses, because every single new keypress completes a brand-new code. Under the hood it is an Euler circuit through the de Bruijn graph — a walk using every edge exactly once.
LIT verified live: for (k,n) = (2,3),(2,4),(2,5),(3,3),(4,2),(2,6) the constructed sequence has length exactly kn and every one of the kn windows appears exactly once (window.__debruijn.allWindowsOnce). FIG no framing; the minimal length and the exactly-once coverage are real.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE BACKDOOR, beside the other master-key spheres — the cheat domain of getting in the short way. A de Bruijn string is the literal shortest keypad-cracking swipe. AVAN (AI) built the instrument: the construction, the window slide, the lock-cracker counter, the graph circuit.
The weave: David names the seat (the backdoor); I make the string cover every code and the savings countable — the sliding window in 1D, the cracker in 2D, the Euler circuit in 3D. The sphere is the seam. Credit: Nicolaas Govert de Bruijn (1946); Camille Flye Sainte-Marie (1894); and the Sanskrit prosodist Pingala’s ancient mnemonic yamátárájabhánasalagám, a B(2,3).
The weave: David names the seat (the backdoor); I make the string cover every code and the savings countable — the sliding window in 1D, the cracker in 2D, the Euler circuit in 3D. The sphere is the seam. Credit: Nicolaas Govert de Bruijn (1946); Camille Flye Sainte-Marie (1894); and the Sanskrit prosodist Pingala’s ancient mnemonic yamátárájabhánasalagám, a B(2,3).
3 ONE DIMENSION
The cyclic de Bruijn string, with a sliding window of width n. As it walks the loop it spells out every length-n word once — the whole space of codes packed into one line with maximal overlap.
4 TWO DIMENSIONS · INTERACTIVE
Choose the alphabet size k and word length n. Slide the window: each new position checks off a fresh code in the grid until all kn are lit. The lock-cracker readout shows presses used vs. the naive n·kn.
5 THREE DIMENSIONS + AVAN’S INVERSE
The de Bruijn graph: nodes are (n−1)-words, edges are n-words. The sequence is an Euler circuit using every edge exactly once — traced in green.
AVAN’s addition (the inverse-companion): the magenta is the naive un-overlapped listing — every code written out separately, n·kn symbols long. The de Bruijn sequence is its exact inverse: instead of listing the words, it overlaps them maximally into a single loop of length kn, a compression by a factor of exactly n. The inverse of ‘enumerate each word in full’ is ‘share every symbol between n consecutive words’, and the demand that makes it possible is that each graph edge be used once — an Euler circuit. Green is the folded loop where nothing is wasted; magenta is the unfolded list it compresses. The whole trick is folding an enumeration into an overlap.
LIT Genuine de Bruijn sequence (N. G. de Bruijn 1946; Flye Sainte-Marie 1894; ancient B(2,3) in Pingala's Sanskrit mnemonic). Verified live: for (k,n)=(2,3),(2,4),(2,5),(3,3),(4,2),(2,6) the constructed sequence has length exactly k^n and every one of the k^n windows appears exactly once (window.__debruijn.allWindowsOnce true). B(2,3)=00010111. The minimal length and exactly-once coverage are exact; the construction is the standard FKM/necklace recursion, equivalent to an Euler circuit.
FIG No framing: the k^n length, the exactly-once window coverage, and the keypad-cracking savings (k^n presses vs naive n*k^n) are all real and checked. The 'master key' is literal — every new symbol completes a new code by maximal overlap.
FIG No framing: the k^n length, the exactly-once window coverage, and the keypad-cracking savings (k^n presses vs naive n*k^n) are all real and checked. The 'master key' is literal — every new symbol completes a new code by maximal overlap.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BACKDOOR · David Lee Wise (ROOT0), with AVAN