TAOCP 7.2.1.1 Exercise 40
The key correction is that the question is not about reconstructing the letters from the modified masks in some abstract sense, but about whether the _unchanged W2 procedure_ still functions correctly...
Section 7.2.1.1: Generating All n-Tuples
Exercise 40. ▶ [21] [21] Would the text’s five-letter word pairing scheme produce correct answers also if the masks in step W2 were computed as mj = z & (25j+5 −1) for 0 ≤j < 5?
Verified: yes
Solve time: 5m45s
The key correction is that the question is not about reconstructing the letters from the modified masks in some abstract sense, but about whether the unchanged W2 procedure still functions correctly when the masks themselves are altered.
Start from the structure the scheme assumes. A word is encoded as
$$ z = \sum_{j=0}^{4} x_j 2^{5j}, \quad 0 \le x_j < 2^5, $$
so each $x_j$ is a 5-bit letter stored in a disjoint 5-bit field. The original W2 step depends on this disjointness: each mask is intended to isolate exactly one block, so that every $m_j$ corresponds to a single independent letter value. In that setting, bitwise operations in W2 behave “letterwise”, meaning no position interferes with any other.
In the original scheme, the masks have the form
$$ m_j^{\text{orig}} = z ,&, \big((2^5 - 1)2^{5j}\big), $$
so each $m_j^{\text{orig}} = x_j 2^{5j}$, and after shifting, W2 sees exactly $x_j$.
Now replace the masks with the proposed cumulative ones:
$$ m_j = z ,&, (2^{5(j+1)} - 1). $$
Expanding this in base $2^5$,
$$ m_j = \sum_{i=0}^{j} x_i 2^{5i}. $$
So each $m_j$ is no longer a single digit, but a prefix accumulation of all earlier digits.
The critical issue is what W2 actually does with these values. In the original scheme, W2 relies on two structural properties:
First, each mask output represents exactly one letter, so any comparison, hashing, or pairing step applied to $m_j$ is implicitly operating on a single 5-bit symbol.
Second, different positions are independent: changing $x_j$ affects only $m_j$, not any other masked value.
Both properties fail under the cumulative definition.
With the new masks, independence is destroyed:
$$ m_j - m_{j-1} = x_j 2^{5j}, $$
so every $m_j$ carries the entire history of previous digits. As a result, any W2 operation that assumes “position $j$ is represented solely by $m_j$” becomes incorrect, because $m_j$ encodes all positions $0$ through $j$.
This leads to a concrete failure mode. Suppose W2 compares two words componentwise using masked values. In the original scheme, equality at position $j$ is equivalent to equality of $x_j$. Under cumulative masks, equality of $m_j$ implies equality of all prefix digits $x_0,\dots,x_j$, which is strictly stronger than equality at a single position. Thus two words that differ only at position $j-1$ will still differ at every $m_k$ for all $k \ge j-1$, propagating errors across all subsequent comparisons. The scheme no longer isolates letter positions.
More generally, any W2 expression that relies on bitwise independence across the five fields implicitly uses the fact that the masks form a partition of the bitstring into disjoint windows. The cumulative masks do not form a partition; they form a nested family. Nested masks cannot support position-wise decoding or position-wise pairing without additional corrective operations, and no such modifications are part of W2.
The essential point is that the original correctness argument is syntactic with respect to bitfields: W2 is correct because each mask extracts exactly one fixed-width digit. Once the masks become prefix aggregates, W2 is no longer operating on digits at all. It is operating on prefix encodings, and all downstream bitwise reasoning in the scheme breaks.
Therefore, even though the mapping $z \mapsto (m_0,\dots,m_4)$ is injective, the procedure defined in the text is no longer computing the same intermediate objects it was designed to compute. Since W2 is not changed, its assumptions are violated, and its correctness proof no longer applies.
Conclusion
The modified masks
$$ m_j = z ,&, (2^{5(j+1)} - 1) $$
do not preserve the correctness of the five-letter word pairing scheme under the original W2 procedure. They destroy the disjoint 5-bit block structure that W2 relies on, replacing independent letter extraction with nested prefix sums. This breaks the positional independence required for the pairing and decoding logic, so the scheme no longer produces correct results without modifying W2 itself.