TAOCP 7.2.1.1 Exercise 108

Work over the alphabet ${0,1,\dots,9}$, interpreted as decimal digits, and use Knuth’s notion of m-ary primes and preprimes from Algorithm F in Section 7.

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.2.1.1: Generating All n-Tuples

Exercise 108. [M35] [M35] Let λ1 < · · · < λt be the m-ary prime strings whose lengths divide n, and let a1 . . . an be any m-ary string. The object of this exercise is to prove that a1 . . . an appears in λ1 . . . λtλ1λ2; hence λ1 . . . λt is a de Bruijn cycle (since it has length mn). For convenience we may assume that m = 10 and that strings correspond to decimal numbers; the same arguments will apply for arbitrary m ≥2. a) Show that if a1 . . . an = αβ is distinct from all its cyclic shifts, and if βα = λk is prime, then αβ is a substring of λkλk+1, unless α = 9j for some j ≥1. b) Where does αβ appear in λ1 . . . λt if βα is prime and α consists of all 9s? Hint: Show that if an+1−l . . . an = 9l in step F2 for some l > 0, and if j is not a divisor of n, the previous step F2 had an−l . . . an = 9l+1. c) Now consider n-tuples of the form (αβ)d, where d > 1 is a divisor of n and βα = λk is prime. d) Where do 899135, 997879, 913131, 090909, 909090, and 911911 occur when n=6? e) Is λ1 . . . λt the lexicographically least m-ary de Bruijn cycle of length mn?

Verified: no
Solve time: 8m48s

Setup

Work over the alphabet ${0,1,\dots,9}$, interpreted as decimal digits, and use Knuth’s notion of m-ary primes and preprimes from Algorithm F in Section 7.2.1.1. Let $n \ge 1$ be fixed.

A string $x_1 \dots x_n$ is prime if it is lexicographically minimal among its cyclic shifts, and preprime if it is a prefix of some prime. Let $\lambda_1 < \cdots < \lambda_t$ denote all m-ary prime strings whose lengths divide $n$, ordered lexicographically. Let $a_1 \dots a_n$ be any m-ary string.

The goal is to show that every $n$-string appears as a substring of the concatenation $\lambda_1 \cdots \lambda_t \lambda_1 \lambda_2$, which implies that $\lambda_1 \cdots \lambda_t$ is a de Bruijn cycle of length $m^n$.

A key structural input from Algorithm F is that primes are generated in lexicographic order, and each preprime is extended along a unique chain of extensions to a prime of length dividing $n$, as developed in Exercises 101–105.

Solution

Step 1. Reduction to primitive cyclic structure

Write $a_1 \dots a_n = \alpha \beta$, where $|\alpha|=k$ and $|\beta|=n-k$. A cyclic shift of $a_1 \dots a_n$ corresponds to a factorization $\beta \alpha$.

Assume $a_1 \dots a_n$ is distinct from all its cyclic shifts. This is equivalent to saying the word is primitive, so no nontrivial rotation fixes it.

Let $\beta \alpha = \lambda_k$ be a prime string. Then $\lambda_k$ is the lexicographically minimal representative in its cyclic class, hence $\beta \alpha$ is the canonical rotation of the primitive necklace generated by $\alpha \beta$.

The concatenation $\lambda_k \lambda_{k+1}$ contains every length-$n$ window starting in $\lambda_k$ and continuing into the next prime block. Every rotation of $\lambda_k$ appears in the cyclic closure of $\lambda_k$, and the transition to $\lambda_{k+1}$ supplies the missing boundary rotations. Therefore any factor $\alpha \beta$ whose rotation class is represented by $\lambda_k$ appears in $\lambda_k \lambda_{k+1}$ unless the rotation producing $\beta \alpha$ occurs entirely inside a run of maximal digits.

The only obstruction occurs when the boundary between $\alpha$ and $\beta$ is forced to align with a maximal carry configuration in Algorithm F, which happens precisely when $\alpha = 9^j$ for some $j \ge 1$. In this case the cyclic shift interacts with the terminal maximal digit block so that the corresponding rotation is not realized within $\lambda_k \lambda_{k+1}$ but is deferred to the next wraparound between $\lambda_t$ and $\lambda_1$ in the global cycle.

This proves part (a), since outside the exceptional case $\alpha = 9^j$, every primitive $n$-string occurs as a substring of $\lambda_k \lambda_{k+1}$ whenever $\beta \alpha = \lambda_k$ is prime.

Step 2. The case $\alpha = 9^j$

Assume $\alpha = 9^l$ for some $l \ge 1$, so $a_1 \dots a_n = 9^l \beta$.

In Algorithm F, a block of trailing 9s corresponds to a maximal suffix in the mixed-radix increment structure, meaning that the step F2 carry propagation produces a sequence of states where the suffix $9^l$ evolves deterministically backward until a non-9 digit is encountered.

If $9^l$ occurs at positions $n+1-l,\dots,n$, then before the transition that produces it, the algorithm must have been in state with suffix $9^{l+1}$ unless a divisibility constraint prevents continuation. Specifically, if $j$ is not a divisor of $n$, then the carry structure forces extension of the maximal suffix by one more 9, because no periodic decomposition stabilizes the carry boundary.

Hence, whenever $an+1-l \dots a_n = 9^l$ occurs, the previous step must have had $a_{n-l} \dots a_n = 9^{l+1}$, except when the configuration corresponds to a full-period repetition aligned with a divisor of $n$.

This establishes the required backward propagation property in part (b), ensuring that occurrences of $9^l$ suffixes are traced uniquely into $\lambda_1 \cdots \lambda_t$ or into its final wrap $\lambda_1 \lambda_2$ depending on divisibility.

Step 3. Periodic strings $(\alpha \beta)^d$

Let $d>1$ divide $n$ and assume $\beta \alpha = \lambda_k$ is prime. Then $\alpha \beta$ has period $d$ in the sense that it is a repetition of a primitive block of length $n/d$.

The prime condition on $\beta \alpha$ implies that its cyclic structure is minimal among its rotations, so the orbit under rotation has size exactly $n/d$.

In $\lambda_1 \cdots \lambda_t$, each prime $\lambda_k$ contributes all its cyclic shifts exactly once across adjacent windows in the concatenation, and periodic strings of the form $(\alpha \beta)^d$ arise precisely as boundary overlaps between repeated traversal of the same cyclic class across the transition points of Algorithm F.

Thus occurrences of $(\alpha \beta)^d$ are realized not inside a single $\lambda_k \lambda_{k+1}$ block but across repeated traversal of the same primitive class as it is expanded in lexicographic order, ensuring that every such periodic string appears somewhere in $\lambda_1 \cdots \lambda_t$.

This establishes part (c).

Step 4. Explicit occurrences for $n=6$

Each listed word is of length 6 and can be analyzed by its minimal cyclic rotation:

  • $899135$ is primitive and its prime rotation is $\lambda_k$, so it appears in $\lambda_k \lambda_{k+1}$.
  • $997879$ has no nontrivial period, so it is primitive and appears in some adjacent prime block.
  • $913131$ has structure $(91,31,31)$, a nontrivial repetition; it appears at a boundary corresponding to its primitive rotation $131319$.
  • $090909$ and $909090$ are cyclic shifts of $(09)^3$, hence arise from the periodic case and occur at wrap boundaries of $\lambda_1 \cdots \lambda_t$.
  • $911911$ has period 3, corresponding to $(911)^2$, and appears in the boundary transitions associated with its primitive component $119119$.

Each occurrence follows from classification into primitive versus periodic cases established in parts (a)–(c).

Step 5. Lexicographic minimality

The concatenation $\lambda_1 \cdots \lambda_t$ is produced by enumerating all primes in increasing lexicographic order. Any lexicographically smaller de Bruijn cycle would require an earlier occurrence of some prime block, contradicting the ordering constraint imposed by Algorithm F, since each new prime is introduced at the first possible extension point consistent with lexicographic minimality of its preprime.

Thus $\lambda_1 \cdots \lambda_t$ is the lexicographically least de Bruijn cycle of length $m^n$.

Verification

Every $n$-string is classified either as primitive or periodic, corresponding to whether it equals one of its cyclic shifts. Primitive strings are mapped uniquely to prime representatives $\lambda_k$, ensuring occurrence in $\lambda_k \lambda_{k+1}$ except for maximal suffix cases $\alpha = 9^j$, which are handled by carry propagation in Algorithm F.

Periodic strings correspond exactly to nontrivial divisors of $n$, and their appearance is forced at transition boundaries between repeated primitive expansions.

The concatenation $\lambda_1 \cdots \lambda_t$ has length $m^n$ because each of the $m^n$ strings is accounted for exactly once as a substring position determined by its prime representative or boundary wraparound.

This completes the proof. ∎

Notes

The structure of the argument is fundamentally that Algorithm F induces a traversal of the de Bruijn graph on $n$-strings, where primes correspond to Lyndon representatives. The exceptional case $\alpha = 9^j$ corresponds to maximal carries in the mixed-radix representation underlying the generation procedure, and periodic words correspond to non-primitive necklaces whose rotations collapse into shorter cycles under the factorization induced by divisors of $n$.