DE BRUIJN not de Bruijn's, and a 52-year head start
A cyclic string of 0s and 1s in which every n-bit pattern appears exactly once as you slide a window along it — maximal overlap, zero waste. It powers keypad-cracking, position encoders, and a famously branch-free trick to find the lowest set bit. And the name is a 52-year misattribution.
THE TECHNIQUE every window once, around a cycle
For alphabet size 2 and window n, a de Bruijn sequence B(2,n) has length 2n and contains all 2n binary strings of length n exactly once (reading cyclically). Below: pick n, generate one, and watch every window get checked off. live demo
HISTORY & CREDIT a Dutch name on a French proof
“de Bruijn sequence” — and de Bruijn (1946) was first beaten by 52 years, then said so himself. cited
c. 600–200 BCE · Indian prosody (Pingala’s gana system) has the idea of enumerating light/heavy syllable-triples; the order-3 mnemonic is a later, medieval crystallization — not Pingala’s own words, and not Panini. 1894 · Camille Flye Sainte-Marie proves the binary existence and count — answering a problem posed that year — 52 years before de Bruijn. 1944 / 1946 · Posthumus conjectures the count; de Bruijn proves it and the object takes his name. In 1975 he formally acknowledges Sainte-Marie’s priority. 1998 · Leiserson, Prokop & Randall (MIT) use a de Bruijn sequence to index the low set bit of a word in one multiply and shift — branch-free, standard in chess engines.
Every length-n window unique means n adjacent readings fix your position on the whole track — that is a position encoder. Sainte-Marie, 1894
RECOMMEND FOR I-13 the isolate runs; the magic multiply overflows
The bit-scan’s first step — isolate the lowest set bit with v & −v (two’s complement) — runs in real I-13 on the integrated bitwise ops:
Recommend: a real, subtle wall. The de Bruijn bit-scan finishes with a perfect-hash multiply by a magic constant, then a shift — but that product (0x077CB531 × a power of two) reaches ~262, past f64’s exact range (253), and it relies on wrapping mod 232. I-13’s * is f64 — no wraparound — so the magic multiply can’t be done exactly. It wants a fixed-width modular multiply (or bignum). The sequence generation itself runs (a 1-D array + the bitwise ops) for small n; the distinct-sequence count is bignum past n=4. Honest note: the low-bit isolate and the sequence run today; only the magic-hash step needs a value kind I-13 doesn’t yet have (u32 wraparound).