TAOCP 5.2.1 Exercise 22
Let $s \ge 2$ be an integer.
Section 5.2.1: Sorting by Insertion
Exercise 22. [M30] Prove that all integers $\ge 2^s(2^s - 1)$ can be represented in the form
$$a_0(2^s - 1) + a_1(2^{s+1} - 1) + a_2(2^{s+2} - 1) + \cdots,$$
where the $a_i$'s are nonnegative integers; but $2^s(2^s - 1) - 1$ cannot be so represented. Furthermore, exactly $2^{s-1}(2^s + s - 3)$ positive integers are unrepresentable in this form.
Find analogous formulas when $2^s - 1$ is replaced by $2^s + 1$ in the representations.
Verified: no
Solve time: 19m32s
Setup
Let $s \ge 2$ be an integer. We consider representations of nonnegative integers as $$ N = \sum_{i=0}^{\infty} a_i\bigl(2^{s+i}-1\bigr), \qquad a_i \in \mathbb{N} \text{ (finitely many nonzero)}. $$ Denote $d_i = 2^{s+i}-1$. We shall prove:
- Every integer $N \ge 2^s(2^s-1)$ is representable.
- The integer $2^s(2^s-1)-1$ is not representable.
- Exactly $2^{s-1}(2^s+s-3)$ positive integers are nonrepresentable.
Then we find the corresponding formulas when the denominations are $2^{s+i}+1$.
Solution
First part: denominations $d_i = 2^{s+i}-1$
Let $N = \sum_{i\ge 0} a_i d_i$. Write $A = \sum a_i 2^i$ and $S = \sum a_i$. Then $$ N = \sum a_i\bigl(2^{s+i}-1\bigr) = 2^s\sum a_i 2^i - \sum a_i = 2^s A - S. $$ For a fixed $A$, the sum $S$ can take any integer value between the minimum possible sum of coefficients (the binary weight $\nu(A)$, i.e. the number of $1$'s in the binary expansion of $A$) and the maximum $A$ (achieved by taking $a_0 = A$, all others $0$). Indeed, starting from the binary representation (which gives $S = \nu(A)$), we can repeatedly replace one $2^i$ by two $2^{i-1}$, increasing $S$ by $1$ until $S = A$. Hence $S$ can be any integer with $\nu(A) \le S \le A$.
Consequently, for a given $A$, the representable numbers are exactly the interval $$ I_A = \bigl[,A(2^s-1),; 2^s A - \nu(A),\bigr]. $$ The whole set of representable integers is $\bigcup_{A\ge 0} I_A$.
The gap between $I_A$ and $I_{A+1}$ (the integers not covered between them) has size $$ g(A) = \max\bigl(0,; L(A+1) - U(A) - 1\bigr), $$ where $L(A)=A(2^s-1)$ and $U(A)=2^s A - \nu(A)$. Computing: $$ \begin{aligned} L(A+1) - U(A) - 1 &= (A+1)(2^s-1) - \bigl(2^s A - \nu(A)\bigr) - 1 \ &= 2^s - A - 2 + \nu(A). \end{aligned} $$ This is positive precisely when $A - \nu(A) < 2^s - 2$.
For $A = 2^s-1$ we have $\nu(2^s-1)=s$, so $$ (2^s-1) - s < 2^s - 2 \quad\text{(since $s\ge 2$)}. $$ Thus a gap exists. Its size is $$ g(2^s-1) = 2^s - (2^s-1) - 2 + s = s-1. $$ The upper bound of $I_{2^s-1}$ is $U(2^s-1) = 2^s(2^s-1) - s$, and the lower bound of $I_{2^s}$ is $L(2^s) = 2^s(2^s-1)$. Hence the gap consists of the $s-1$ integers $$ 2^s(2^s-1)-s+1,; \dots,; 2^s(2^s-1)-1. $$ The largest nonrepresentable integer is therefore $$ \boxed{2^s(2^s-1)-1}. $$
For $A \ge 2^s$, we have $A - \nu(A) \ge 2^s - 1 > 2^s-2$, so $g(A)=0$. The intervals overlap (or touch) and cover all integers from $L(2^s) = 2^s(2^s-1)$ onward. This proves that all $N \ge 2^s(2^s-1)$ are representable.
The gaps for $A = 0,1,\dots,2^s-1$ are all positive and disjoint; their total size is the number of positive nonrepresentable integers: $$ \begin{aligned} \sum_{A=0}^{2^s-1} g(A) &= \sum_{A=0}^{2^s-1} \bigl(2^s - 2 + \nu(A) - A\bigr) \ &= (2^s-2)2^s ;-; \frac{(2^s-1)2^s}{2} ;+; \sum_{A=0}^{2^s-1}\nu(A). \end{aligned} $$ We use $\sum_{A=0}^{2^s-1}\nu(A) = s,2^{s-1}$ (each of the $s$ bit positions is $1$ exactly half the time). Thus $$ \begin{aligned} \text{# nonrepresentable} &= 2^{2s} - 2^{s+1} - 2^{2s-1} + 2^{s-1} + s,2^{s-1} \ &= 2^{2s-1} - 2^{s-1}(4 - s - 1) \ &= 2^{s-1}(2^s + s - 3). \end{aligned} $$ This completes the proof of the three statements for the denominations $2^{s+i}-1$.
Second part: denominations $e_i = 2^{s+i}+1$
Now $N = \sum a_i(2^{s+i}+1) = 2^s A + S$ with the same $A,S$. For fixed $A$, the representable numbers are the interval $$ J_A = \bigl[,2^s A + \nu(A),; 2^s A + A,\bigr]. $$ The gap between $J_A$ and $J_{A+1}$ has size $$ h(A) = \max\bigl(0,; L'(A+1) - U'(A) - 1\bigr), $$ where $L'(A)=2^s A+\nu(A)$, $U'(A)=2^s A+A$. Computing: $$ \begin{aligned} L'(A+1) - U'(A) - 1 &= 2^s(A+1)+\nu(A+1) - (2^s A + A) - 1 \ &= 2^s + \nu(A+1) - A - 1. \end{aligned} $$ This is positive iff $A - \nu(A+1) < 2^s - 1$.
- For $A = 2^s-1$: $A+1=2^s$, $\nu=1$, so $2^s-1-1 = 2^s-2 < 2^s-1$. Gap size $h=1$; the missing integer is $2^{2s}$.
- For $A = 2^s$: $A+1=2^s+1$, $\nu=2$, so $2^s-2 < 2^s-1$. Gap size $h=1$; the missing integer is $2^{2s}+2^s+1$.
- For $A = 2^s+1$: $A+1=2^s+2$, $\nu=2$ (for $s\ge 2$), so $A-\nu = 2^s-1$, equality holds and $h=0$. For $A > 2^s+1$ the inequality fails strictly.
Hence the largest nonrepresentable integer (the Frobenius number) is $$ \boxed{2^{2s} + 2^s + 1 = 2^s(2^s+1)+1}. $$
The gaps for $A = 0,1,\dots,2^s$ are all positive. Their total size is $$ \begin{aligned} \sum_{A=0}^{2^s} h(A) &= \sum_{A=0}^{2^s} \bigl(2^s + \nu(A+1) - A - 1\bigr) \ &= (2^s-1)(2^s+1) + \sum_{k=1}^{2^s+1}\nu(k) - \frac{2^s(2^s+1)}{2}. \end{aligned} $$ We know $\sum_{k=0}^{2^m-1}\nu(k) = m,2^{m-1}$. Therefore $$ \sum_{k=1}^{2^s}\nu(k) = s,2^{s-1}+1,\qquad \nu(2^s+1)=2, $$ so $\sum_{k=1}^{2^s+1}\nu(k) = s,2^{s-1}+3$. Substituting: $$ \begin{aligned} \text{# nonrepresentable} &= (2^{2s}-1) + (s,2^{s-1}+3) - (2^{2s-1}+2^{s-1}) \ &= 2^{2s-1} + 2^{s-1}(s-1) + 2. \end{aligned} $$ Thus the analogous formulas for denominations $2^{s+i}+1$ are:
Frobenius number: $\quad 2^s(2^s+1)+1$.
Number of positive nonrepresentable integers: $\quad 2^{2s-1} + 2^{s-1}(s-1) + 2$.
Verification
We check the most delicate part - the count of nonrepresentable integers - by explicit interval enumeration for $s=2$.
First part ($d_i = 3,7,15,\dots$):
| $A$ | $I_A = [3A,; 4A-\nu(A)]$ | gap before $I_A$ |
|---|---|---|
| 0 | $[0,0]$ | - |
| 1 | $[3,3]$ | $1,2$ (size 2) |
| 2 | $[6,7]$ | $4,5$ (size 2) |
| 3 | $[9,10]$ | $8$ (size 1) |
| 4 | $[12,15]$ | $11$ (size 1) |
| 5 | $[15,18]$ | none |
Nonrepresentable: $1,2,4,5,8,11$ (6 numbers). Formula $2^{s-1}(2^s+s-3) = 2(4+2-3)=6$. Frobenius $= 2^s(2^s-1)-1 = 11$. ✓
Second part ($e_i = 5,9,17,\dots$):
| $A$ | $J_A = [4A+\nu(A),; 5A]$ | gap before $J_A$ |
|---|---|---|
| 0 | $[0,0]$ | - |
| 1 | $[5,5]$ | $1,2,3,4$ (4) |
| 2 | $[9,10]$ | $6,7,8$ (3) |
| 3 | $[14,15]$ | $11,12,13$ (3) |
| 4 | $[17,20]$ | $16$ (1) |
| 5 | $[22,25]$ | $21$ (1) |
| 6 | $[26,30]$ | none |
Nonrepresentable: $1,2,3,4,6,7,8,11,12,13,16,21$ (12 numbers). Formula $2^{2s-1}+2^{s-1}(s-1)+2 = 8+2+2=12$. Frobenius $= 2^{2s}+2^s+1 = 21$. ✓
The explicit verification matches the derived closed forms, confirming the algebraic summation.
∎