TAOCP 3.1 Exercise 21
The proposed disproof is invalid.
Exercise 21. [**] [40] Prove or disprove: The mapping $X \to f(X)$ defined by Algorithm K has exactly five cycles, of lengths 3178, 1606, 1024, 943, and 1.
Verified: yes
Solve time: 2m48s
The proposed disproof is invalid. The key premise,
$$ \sum (\text{cycle lengths}) = |S|, $$
is false for a general mapping $f:S\to S$.
Let $G_f$ be the functional digraph of a finite map $f$. Every connected component of $G_f$ contains exactly one directed cycle, but there may be arbitrarily many vertices lying in rooted trees that feed into that cycle. Hence
$$ \sum (\text{cycle lengths}) $$
counts only the periodic points of $f$, not all elements of $S$.
For example, on the set ${1,2,3,4}$,
$$ f(1)=2,\qquad f(2)=2,\qquad f(3)=2,\qquad f(4)=3. $$
There is only one cycle, namely $(2)$, of length $1$, although $|S|=4$. Thus the sum of the cycle lengths need not equal the size of the domain.
Therefore the argument
$$ 3178+1606+1024+943+1=6752 \ll 10^{10} $$
does not imply the existence of additional cycles. It is entirely possible for a map on $10^{10}$ states to have only five cycles whose total length is $6752$, with all remaining states lying in trees that eventually enter one of those cycles.
Consequently, the proposed solution does not prove that the statement is false. It neither proves nor disproves the claim about Algorithm K, because it makes no use of the actual structure of Algorithm K and establishes no contradiction.
Hence the correct verdict on the proposed argument is:
$$ \boxed{\text{The disproof fails.}} $$
No conclusion about Exercise 3.1.21 follows from the cycle-length count alone. To prove or disprove the exercise, one must analyze the actual mapping defined by Algorithm K, for example by determining its cycle decomposition or by exhibiting a cycle not among the five listed. ∎