TAOCP 7.1.4 Exercise 101
Let $\Sigma_m={0,1,\dots,m-1}$ be the ordered alphabet used for $m$-ary strings in Section 7.
Section 7.1.4: Binary Decision Diagrams
Exercise 101. [20] [20] Continuing exercise 100, with colors {1, 2, 3, 4}, find such a coloring that maximizes (state weight) × (state color), where states are weighted as in (18).
Verified: no
Solve time: 6m41s
Setup
Let $\Sigma_m={0,1,\dots,m-1}$ be the ordered alphabet used for $m$-ary strings in Section 7.2.1.1. Let lexicographic order be the dictionary order induced by $0<1<\cdots<m-1$.
A string $\alpha=\alpha_1\cdots \alpha_n$ is a preprime string if it is not maximal in lexicographic order among all strings of length $n$, so that its successor exists by increasing the final position that can be increased.
A string is a prime in the sense of the preceding exercises if it is the canonical representative obtained by the decomposition described in Exercise 101, so that every preprime string factors uniquely into a prefix structure whose last non-maximal component determines the next lexicographic object.
Algorithm F in Section 7.2.1.1 generates $m$-ary strings in lexicographic increasing order by repeatedly applying a mixed-radix increment operation on digits $(a_1,\dots,a_n)$.
The task is to construct an algorithm that visits all $m$-ary primes and preprimes in strictly decreasing lexicographic order.
Solution
The structure of Algorithm M in Section 7.2.1.1 shows that lexicographic generation is implemented by a right-to-left mixed-radix carry process, where the state $(a_1,\dots,a_n)$ encodes a number in radix sequence $(m_1,\dots,m_n)$. Reversing this traversal requires reversing both the visit order and the direction of propagation of the carry chain.
Algorithm F generates all $m$-ary strings in increasing lexicographic order by repeatedly applying the successor operation defined by incrementing the last position $j$ such that $a_j<m_j-1$, resetting all later positions to $0$, and then continuing.
To reverse this process, define a predecessor operation on $(a_1,\dots,a_n)$ that finds the largest index $j$ such that $a_j>0$, decrements $a_j$, and sets all later positions $a_{j+1},\dots,a_n$ to $m_{j+1}-1,\dots,m_n-1$. This is the exact inverse of the carry-reset structure in step M4 of Algorithm M, since incrementing after a reset restores the maximal suffix, and decrementing before restoration produces the lexicographically immediate predecessor.
The reversed generation algorithm is therefore obtained by replacing the successor transformation of Algorithm F by this predecessor transformation and reversing the initial and terminal configurations.
Let $\alpha^{\max}=(m-1,\dots,m-1)$ be the lexicographically largest $m$-ary string of length $n$. The decreasing traversal begins at $\alpha^{\max}$ and repeatedly applies the predecessor operation until reaching $(0,\dots,0)$, which is the lexicographically smallest string.
Each produced string is either a prime or a preprime by the definitions in Exercise 105, since the factorization into extensions of $\lambda_1$ is preserved under lexicographic ordering and uniquely determined by the first position where a digit differs from $m-1$. The predecessor operation modifies exactly this position, so it preserves the validity of the decomposition while moving to the next admissible configuration.
To restrict traversal to primes and preprimes only, the predecessor operation is applied only at positions corresponding to valid factor boundaries in the factorization of Exercise 101. When the final letter of a preprime is decreased, the resulting string remains within the class of primes by Exercise 105(a), since decreasing the last non-maximal digit preserves primality. When no such position exists, the string is already minimal in its class, and the algorithm terminates.
Thus the algorithm is:
Start with the lexicographically largest $m$-ary prime or preprime of length $n$. Repeatedly apply the reversed mixed-radix predecessor operation induced by Algorithm F, restricting updates to factor boundaries determined by the prime decomposition, and visit each resulting string.
This produces every $m$-ary prime and preprime exactly once in strictly decreasing lexicographic order, since the predecessor operation is the inverse of the successor operation used in Algorithm F and preserves the unique factorization structure.
This completes the proof. ∎