TAOCP 4.6.3 Exercise 17

Section 4.6.3: Evaluation of Powers

Exercise 17. [M25] Explain how to find the intervals $J_1, \ldots, J_k$ that are required in the proof of Lemma J.

Verified: no
Solve time: 2m18s

Solution

In the proof of Lemma J, the intervals $J_1,\ldots,J_k$ are introduced in order to partition a finite set of admissible values into maximal consecutive blocks.

Let $S$ denote the set of integers that satisfy the condition appearing in Lemma J. Arrange the elements of $S$ in increasing order,

$$ s_1 < s_2 < \cdots < s_m . $$

The required intervals are obtained by scanning this ordered list and grouping together consecutive integers.

Begin with the smallest element $s_1$. Continue as long as the next element differs by $1$. If

$$ s_i,s_{i+1},\ldots,s_j $$

is a maximal consecutive run, that is,

$$ s_{t+1}=s_t+1 \qquad (i\le t<j), $$

while either $i=1$ or $s_i>s_{i-1}+1$, and either $j=m$ or $s_{j+1}>s_j+1$,

then define

$$ J_r=[,s_i,s_j,]. $$

After this interval has been formed, continue with the first unused element and repeat the same procedure. The process terminates after finitely many steps and yields intervals

$$ J_1,\ldots,J_k $$

having the properties required in the proof:

1. Every element of $S$ belongs to exactly one interval $J_r$.
2. The intervals are pairwise disjoint.
3. Each $J_r$ is maximal with respect to inclusion among intervals consisting entirely of admissible integers.

Equivalently, the endpoints of the intervals are determined by the gaps in $S$: a new interval begins immediately after each missing integer and ends immediately before the next missing integer.

Thus the intervals $J_1,\ldots,J_k$ are found simply by decomposing the admissible integers into their maximal contiguous blocks. This is precisely the construction assumed in the proof of Lemma J. ∎