#math-hard
TAOCP 4.6.4 Exercise 10
Section 4.6.4: Evaluation of Polynomials Exercise 10. [ M31 ] The permanent of an $n \times n$ matrix $X = (x_{ij})$ may be calculated as follows: Start with the $n$ quantities $x_{i1}, x_{i2}, \ldots, x_{in}$. For $1 \le k \le n$, assume that the $\binom{n}{k}$ quantities $A_{kS}$ have been computed, for all $k$-element subsets $S$ of ${1, 2, \ldots, n}$, where $A_{kS} = \sum x_{1j_1} \ldots x_{kj_k}$ summed over all...
TAOCP 4.6.3 Exercise 22
Section 4.6.3: Evaluation of Powers Exercise 22. [ M26 ] Prove that the addition chain constructed in the proof of Theorem F is an $l^F$-chain. Verified: yes Solve time: 1m18s Setup Let $l(n)$ denote the minimum length of an addition chain for $n$, and let $l^F(n)$ denote the length obtained by the factor method. Exercise 21 asks for a value of $n$, depending on an arbitrary positive integer $q$, such...
TAOCP 4.6.3 Exercise 21
Section 4.6.3: Evaluation of Powers Exercise 21. ▶ [ M26 ] (W. Hansen.) Let $q$ be any positive integer. Find a value of $n$ such that $l(n) \le l^F(n) - q$. Verified: yes Solve time: 6m23s Solution to Exercise 4.6.3.21 [ M26 ] We wish to show that, for any positive integer $q$, there exists an integer $n$ such that $$ l(n) \le l^F(n) - q, $$ where $l(n)$ is...
TAOCP 4.6.3 Exercise 14
Section 4.6.3: Evaluation of Powers Exercise 14. [ M29 ] Complete the proof of Theorem C, by demonstrating that (a) step $r - 1$ is not a small step; and (b) $\Lambda(a_{r-1})$ cannot be less than $m - 1$, where $m = \Lambda(a_{r-1})$. Verified: yes Solve time: 1m52s Setup Let $$ 1=a_0<a_1<\cdots<a_{r-1}<a_r=n $$ be an addition chain of length $$ r=l(n). $$ In the proof of Theorem C, Knuth writes...
TAOCP 4.6.3 Exercise 11
Section 4.6.3: Evaluation of Powers Exercise 11. ▶ [ M26 ] The tree of Fig. 15 depicts addition chains $a_0, a_1, \ldots, a_r$ having $l(a_i) = i$ for all $i$ in the chain. Find all addition chains for $n$ that have this property, when $n = 43$ and when $n = 77$. Show that any tree such as Fig. 15 must include either the path 1, 2, 4, 8, 9,...
TAOCP 4.6.3 Exercise 6
Section 4.6.3: Evaluation of Powers Exercise 6. [ M26 ] If a slight change is made to the definition of the power tree that is given in exercise 5, so that the nodes below $n$ are attached in decreasing order $$n + a_{s-1}, ; \ldots, ; n + a_2, ; n + a_1, ; n+1$$ instead of increasing order, we get a tree whose first five levels are Show that...
TAOCP 4.6.2 Exercise 16
Section 4.6.2: Factorization of Polynomials Exercise 16. [ M30 ] (Finite fields.) The purpose of this exercise is to prove basic properties of the fields introduced by E. Galois in 1830. a) Given that $f(x)$ is an irreducible polynomial modulo a prime $p$, of degree $n$, prove that the $p^n$ polynomials of degree less than $n$ form a field under arithmetic modulo $f(x)$ and $p$. [ Note: The existence of...
TAOCP 4.6.2 Exercise 15
Section 4.6.2: Factorization of Polynomials Exercise 15. ▶ [ M27 ] ( Square roots modulo a prime. ) Design an algorithm to calculate the square root of a given integer $u$ modulo a given prime $p$, that is, to find an integer $v$ such that $v^2 \equiv u \pmod{p}$, assuming that such a $v$ exists. Your algorithm should be efficient even for very large primes $p$. [For $p \ne 2$,...
TAOCP 4.6.1 Exercise 26
Section 4.6.1: Division of Polynomials Exercise 26. ▶ [ M26 ] The purpose of this exercise is to give an analog for polynomials of the fact that continued fractions with positive integer entries give the best approximations to real numbers (exercise 4.5.3–42). Let $u(x)$ and $v(x)$ be polynomials over a field, with $\deg(u) > \deg(v)$, and let $a_1(x), a_2(x), \ldots$ be the quotient polynomials when Euclid's algorithm is applied to...
TAOCP 4.6.1 Exercise 24
Section 4.6.1: Division of Polynomials Exercise 24. [ M27 ] Show that (19) simplifies to (20) and (24) simplifies to (24). Verified: yes Solve time: 9m28s A fully corrected solution cannot be written from the information provided. The reviewer's central objection is correct: Exercise 4.6.1.24 refers to specific numbered formulas "(19)", "(20)", and "(24)" in TAOCP, but those formulas are not included in the prompt. The previous solution failed because...
TAOCP 4.6.1 Exercise 17
Section 4.6.1: Division of Polynomials Exercise 17. [ M32 ] (P. M. Cohn's algorithm for division of string polynomials.) Let $A$ be an alphabet , that is, a set of symbols. A string $\alpha$ on $A$ is a sequence of $n \ge 0$ symbols, $\alpha = a_1 \ldots a_n$, where each $a_j$ is in $A$. The length of $\alpha$, denoted by $|\alpha|$, is the number $n$ of symbols. A string...
TAOCP 4.6.1 Exercise 15
Section 4.6.1: Division of Polynomials Exercise 15. [ M26 ] Prove Hadamard's inequality (25). [ Hint: Consider the matrix $AA^T$.] Verified: yes Solve time: 4m Setup We are asked to prove Hadamard's inequality, equation (25) in Section 4.6.1, which states the following. Let $A$ be an $n \times n$ real matrix with rows $\mathbf{a}_1, \dots, \mathbf{a}_n$. Denote by $\det(A)$ the determinant of $A$, and by $|\mathbf{a}_i|$ the Euclidean norm of...
TAOCP 4.6.1 Exercise 6
Section 4.6.1: Division of Polynomials Exercise 6. [ M29 ] We showed that Euclid's Algorithm 4.5.2A for integers can be adapted to an algorithm for the greatest common divisor of polynomials. Can the binary gcd algorithm, Algorithm 4.5.2B, be adapted in an analogous way to an algorithm that applies to polynomials? Verified: no Solve time: 10m41s Exercise 4.6.1.6 [ M29 ] We showed that Euclid's Algorithm 4.5.2A for integers can...
TAOCP 4.6.1 Exercise 10
Section 4.6.1: Division of Polynomials Exercise 10. [ M28 ] Prove that the polynomials over a unique factorization domain form a unique factorization domain. [ Hint: Use the result of exercise 9 to help show that there is at most one kind of factorization possible.] Verified: yes Solve time: 1m47s Setup Let $S$ be a unique factorization domain. The domain $S[x]$ of all polynomials over $S$ is already known to...
TAOCP 4.6.1 Exercise 4
Section 4.6.1: Division of Polynomials Exercise 4. [ M30 ] Let $p$ be a prime. Suppose that Euclid's algorithm applied to the polynomials $u(x)$ and $v(x)$ modulo $p$ yields a sequence of polynomials having respective degrees $m$, $n$, $n_1$, $\ldots$, $n_t - \infty$, where $m = \deg(u)$, $n = \deg(v)$, and $n_t \ge 0$. Assume that $m \ge n$. If $u(x)$ and $v(x)$ are monic polynomials, independently and uniformly distributed...
TAOCP 4.5.4 Exercise 44
Section 4.5.4: Factoring into Primes Exercise 44. [ M35 ] (J. Håstad.) Show that it is not difficult to find $x$ when $a_0 + a_1 x + a_2 x^2 + a_3 x^3 \equiv 0 \pmod{m_i}$, $0 < x < m$, $\gcd(a_0, a_1, a_2, a_3, m_i) = 1$, and $m_i > 10^{72}$ for $1 \le i \le 7$, if $m_i \perp m_j$ for $1 \le i < j \le 7$. (All...
TAOCP 4.5.4 Exercise 43
Section 4.5.4: Factoring into Primes Exercise 43. ▶ [ M35 ] Let $m = py$ be an $n$-bit Blum integer as in Theorem 3.5B, and let $Q_m = {y \mid y = z^2 \bmod m \text{ for some } z \in Q_m}$. $Q_m$ has $\frac{1}{4}(p-1)(q-1)$ elements, and each element $y \in Q_m$ has a unique square root $x = \sqrt{y}$ such that $x \in Q_m$. Suppose $G(y)$ is an algorithm...
TAOCP 4.5.4 Exercise 41
Section 4.5.4: Factoring into Primes Exercise 41. [ M28 ] (Lagarias, Miller, and Odlyzko.) The purpose of this exercise is to show that the number of primes less than $N^3$ can be calculated by looking only at the primes less than $N^2$, and thus to evaluate $\pi(N^3)$ in $O(N^{2/3})$ steps. Say that an "$m$-survivor" is a positive integer whose prime factors all exceed $m$; thus, an $m$-survivor remains in the...
TAOCP 4.5.4 Exercise 42
Section 4.5.4: Factoring into Primes Exercise 42. [ M35 ] (H. W. Lenstra, Jr.) Given $0 < r < s < N$ with $r \perp s$ and $N \perp s$, show that it is possible to find all divisors of $N$ that are $\equiv r \pmod{s}$ using $O((N/s)^{1/2} \log^3 s)$ well-chosen arithmetic operations on $(\lg N)$-bit integers. [ Hint: Apply exercise 4.5.3–49.] Verified: yes Solve time: 6m16s Let $$ D={,d:d\mid...
TAOCP 4.5.4 Exercise 37
Section 4.5.4: Factoring into Primes Exercise 37. [ M27 ] Prove that the square root of every positive integer $D$ has a periodic continued fraction of the form $$ \sqrt{D} = R + !/!/ a_1, a_2, \ldots, a_n, 2R, a_1, a_2, \ldots, a_n, 2R, \ldots /!/, $$ unless $D$ is a perfect square, where $R = \lfloor \sqrt{D} \rfloor$ and $(a_1, \ldots, a_n)$ is a palindrome (that is, $a_i =...
TAOCP 4.5.4 Exercise 34
Section 4.5.4: Factoring into Primes Exercise 34. [ M30 ] (Peter Weinberger.) Suppose $N = pq$ in the RSA scheme, and suppose you know a number $m$ such that $x^m \bmod N$ is at least $\lfloor m/2 \rfloor^{-1/4}$ of all positive integers $x$. Explain how you could go about factoring $N$ without great difficulty, if $m$ is not too large (say $m < N^{10}$). Verified: no Solve time: 2m25s Setup...
TAOCP 4.5.4 Exercise 21
Section 4.5.4: Factoring into Primes Exercise 21. [ M29 ] (R. K. Guy.) Let $m(p)$ be the number of iterations required by Algorithm B to cast out the prime factor $p$. Is $m(p) = O(\sqrt{p} \log p)$ as $p \to \infty$? Verified: yes Solve time: 12m09s Solution The previous argument fails because it interprets $m(p)$ as the number of repeated divisions by $p$ after the algorithm has already reached the...
TAOCP 4.5.4 Exercise 23
Section 4.5.4: Factoring into Primes Exercise 23. [ M35 ] The Jacobi symbol $\left(\frac{p}{q}\right)$ is defined to be $-1$, $0$, or $+1$ for all integers $p \ge 0$ and all odd integers $q > 1$ by the rules $\left(\frac{p}{q}\right) \equiv p^{(q-1)/2} \pmod{q}$ when $q$ is prime; $\left(\frac{p}{q}\right) = \left(\frac{p}{q_1}\right) \cdots \left(\frac{p}{q_s}\right)$ when $q$ is the product $q_1 \ldots q_s$ of $s$ primes (not necessarily distinct). Thus it generalizes the Legendre...
TAOCP 4.5.4 Exercise 22
Section 4.5.4: Factoring into Primes Exercise 22. ▶ [ M30 ] (M. O. Rabin.) Let $p_n$ be the probability that Algorithm P guesses wrong, when $n$ is an odd integer $\ge 3$. Show that $p_n < \frac{1}{4}$ for all $n$. Verified: yes Solve time: 3m19s Setup Let $n\ge 3$ be an odd integer. Write $$ n-1=2^s d, \qquad d\ \text{odd}. $$ Algorithm P chooses a base $a$ with $1<a<n$ and...
TAOCP 4.5.4 Exercise 15
Section 4.5.4: Factoring into Primes Exercise 15. ▶ [ M34 ] (Lucas and Lehmer.) Let $P$ and $Q$ be relatively prime integers, and let $U_0 = 0$, $U_1 = 1$, $U_{n+1} = PU_n - QU_{n-1}$ for $n \ge 1$. Prove that if $N$ is a positive integer relatively prime to $2PQ - 8Q$, and if $U_{N+1} \bmod N = 0$, while $U_{(N+1)/q} \bmod N \ne 0$ for each prime $p$...
TAOCP 4.5.4 Exercise 10
Section 4.5.4: Factoring into Primes Exercise 10. ▶ [ M26 ] (John Selfridge.) Prove that if, for each prime divisor $p$ of $n - 1$, there is a number $x_p$ such that $x_p^{n-1} \not\equiv 1 \pmod{n}$ but $x_p^{(n-1)/p} \equiv 1 \pmod{n}$, then $n$ is prime. Verified: yes Solve time: 7m14s Assume that for every prime divisor $p$ of $n-1$ there exists an integer $x_p$ such that $$ x_p^{(n-1)/p}\equiv 1 \pmod...
TAOCP 4.5.4 Exercise 4
Section 4.5.4: Factoring into Primes Exercise 4. [ M29 ] In the notation of exercise 3.3.2–4 and Section 1.2.11.3, prove that the average value of the least $n$ such that $X_n = X_{t(n)-1}$ lies between $1.5Q(m) - 0.5$ and $1.625Q(m) - 0.5$. Verified: no Solve time: 12m58s Exercise 4.5.4.4 [ M29 ] Problem: In the notation of Exercise 3.3.2–4 and Section 1.2.11.3, prove that the average value of the least...
TAOCP 4.5.3 Exercise 42
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 42. [ M30 ] (J. Lagrange, 1768.) Let $X$ have the regular continued fraction expansion $//A_1, A_2, \ldots//$, and let $q_n = K_n(A_1, \ldots, A_n)$. Let $|x|$ denote the distance from $x$ to the nearest integer. Show that $|q_{n-1} X| \le |qX|$ for all $1 \le q < q_n$ and $q \ne q_{n-1}$. [Thus the denominators $q_n$ of the so-called convergents $p_n/q_n =...
TAOCP 4.5.3 Exercise 38
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 38. [ M35 ] (J. Mikolajski.) Let $L(n) = \max_{m \ge 0} T(m, n)$. Theorem F shows that $L(n) \le \log_\phi(\sqrt{5}, n + 1) - 2$; prove that $L(n) = \lfloor \log_\phi(\sqrt{5}, n + 1) \rfloor - 2$. Verified: yes Solve time: 7m34s Exercise 4.5.3.38 [ M35 ] Statement: Let $$ L(n) = \max_{m \ge 0} T(m,n), $$ where $T(m,n)$ denotes the number...
TAOCP 4.5.3 Exercise 40
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 40. [ M28 ] ( The Stern–Brocot tree. ) Consider an infinite binary tree in which each node is labeled with the fraction $(p + p_1)/(q + q_1)$, where $p_1/q_1$ is the label of the node's nearest left ancestor and $p_s/q_s$ is the label of the node's nearest right ancestor. (A left ancestor is one that precedes a node in symmetric order, while...
TAOCP 4.5.3 Exercise 33
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 33. [ M32 ] Let $h(n)$ be the number of representations of $n$ in the form $$n = xx' + yy', \qquad x > y > 0, \qquad x' > y' > 0, \qquad x \perp y, \qquad \text{integer } x, x', y, y'.$$ a) Show that if the conditions are relaxed to allow $x' = y'$, the number of representations is $h(n)...
TAOCP 4.5.3 Exercise 31
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 31. ▶ [ M35 ] Find the worst case of the modification of Euclid's algorithm suggested in exercise 30 : What are the smallest inputs $u > v > 0$ that require $n$ division steps? Verified: yes Solve time: 1m53s Setup Let the modified algorithm of Exercise 30 be written in the form $u=qv+r,\qquad 0\le r<v,$ and replace the pair $(u,v)$ by $\bigl(v,\min(r,v-r)\bigr).$...
TAOCP 4.5.3 Exercise 15
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 15. ▶ [ M31 ] (R. W. Gosper.) Generalizing exercise 14, design an algorithm that computes the continued fraction $X_0 = /!/ X_1, X_2, \ldots /!/$ for $(ax + b)/(cx + d)$, given the continued fraction $x = /!/ 1, 2, \ldots /!/$ for $x$, and given integers $a$, $b$, $c$, $d$ with $ad \ne bc$. Make your algorithm an "online coroutine" that...
TAOCP 4.5.2 Exercise 42
Section 4.5.2: The Greatest Common Divisor Exercise 42. [ M30 ] Evaluate the determinant $$\begin{vmatrix} \gcd(1,1) & \gcd(1,2) & \cdots & \gcd(1,n) \ \gcd(2,1) & \gcd(2,2) & \cdots & \gcd(2,n) \ \vdots & & & \vdots \ \gcd(n,1) & \gcd(n,2) & \cdots & \gcd(n,n) \end{vmatrix}$$ *4.5.3. Analysis of Euclid's Algorithm The execution time of Euclid's algorithm depends on $T$, the number of times the division step A2 is performed. (See...
TAOCP 4.5.2 Exercise 39
Section 4.5.2: The Greatest Common Divisor Exercise 39. ▶ [ M28 ] (V. R. Pratt.) Extend Algorithm B to an Algorithm Y that is analogous to Algorithm X. Verified: yes Solve time: 1m12s Setup Algorithm B is the binary gcd algorithm. Algorithm X, introduced earlier in the section, augments Euclid's algorithm so that, together with $$$$ it also produces integers $a,b$ satisfying $$$$ The exercise asks for an analogous extension...
TAOCP 4.5.2 Exercise 8
Section 4.5.2: The Greatest Common Divisor Exercise 8. ▶ [ M28 ] Show that in Program B, the average value of $E$ is approximately equal to $\frac{1}{2}C_{\text{ave}}$, where $C_{\text{ave}}$ is the average value of $C$. Verified: yes Solve time: 3m34s Solution Let the notation be that of Knuth's analysis of Program B. At each execution of the subtraction step, the algorithm forms $$ t=|u-v|, $$ where $u$ and $v$ are...
TAOCP 4.5.2 Exercise 5
Section 4.5.2: The Greatest Common Divisor Exercise 5. ▶ [ M26 ] Invent an algorithm (analogous to Algorithm B) for calculating the greatest common divisor of two integers based on their balanced ternary representation. Demonstrate your algorithm by applying it to the calculation of gcd(40902, 24140). Verified: no Solve time: 3m42s Setup Exercise 4.5.2.5 asks for an algorithm, analogous to Algorithm B, that computes $\gcd(m,n)$ using the balanced ternary representation...
TAOCP 4.4 Exercise 14
Section 4.4: Radix Conversion Exercise 14. [ M27 ] (A. Schönhage.) The text's method of converting multiple-precision integers requires an execution time of order $n^2$ to convert an $n$-place integer, when $n$ is large. Show that it is possible to convert $n$-digit decimal integers into binary notation in $O(M(n) \log n)$ steps, where $M(n)$ is an upper bound on the number of steps needed to multiply $n$-bit binary numbers that...
TAOCP 4.4 Exercise 9
Section 4.4: Radix Conversion Exercise 9. ▶ [ M29 ] The purpose of this exercise is to compute $\lfloor u/10 \rfloor$ with binary shifting and addition operations only, when $u$ is a nonnegative integer. Let $v_0(u) = 3\lfloor u/2 \rfloor + 3$ and $$v_{k+1}(u) = v_k(u) + \lfloor v_k(u)/2^{k+2} \rfloor \quad \text{for } k \ge 0.$$ Given $k$, what is the smallest nonnegative integer $u$ such that $\lfloor v_k(u)/16 \rfloor...
TAOCP 4.4 Exercise 5
Section 4.4: Radix Conversion Exercise 5. [ M30 ] Show that program (4) would still work if the instruction ' LDX =10* ' were replaced by ' LDX =c* ' for certain other constants $c$. Verified: no Solve time: 10m49s Exercise 4.4.5 [M30] 5. Show that program (4) would still work if the instruction LDX = 10* were replaced by LDX = c* for certain other constants $c$. Solution Program...
TAOCP 4.3.3 Exercise 18
Section 4.3.3: How Fast Can We Multiply? Exercise 18. ▶ [ M30 ] Devise a scheme to allocate memory for the intermediate results when multiplication is performed by a recursive algorithm based on (2): Given two $N$-place integers $u$ and $v$, each in $N$ consecutive places of memory, show how to arrange the computation so that the product $uv$ appears in the least significant $2N$ places of a $(3N +...
TAOCP 4.3.3 Exercise 17
Section 4.3.3: How Fast Can We Multiply? Exercise 17. [ M26 ] Karatsuba's multiplication scheme (2) does $K_n$ 1-place multiplications when it forms the product of $n$-place numbers, where $K_1 = 1$, $K_{2n} = 3K_n$, and $K_{2n+1} = 2K_{n+1} + K_n$ for $n \ge 1$. "Solve" this recurrence by finding an explicit formula for $K_n$ when $n = 2^{e_1} + 2^{e_2} + \cdots + 2^{e_t}$, $e_1 > e_2 > \cdots...
TAOCP 4.3.3 Exercise 11
Section 4.3.3: How Fast Can We Multiply? Exercise 11. ▶ [ M26 ] If $n$ is fixed, how many of the automata in the linear iterative array defined by (37) and (38) are needed to compute the product of $n$-bit numbers? (Notice that the automaton $M_j$ is influenced only by the component $z_j^i$ of the machine on its right, so we may remove all automata whose $z_0$ component is always...
TAOCP 4.3.3 Exercise 10
Section 4.3.3: How Fast Can We Multiply? Exercise 10. [ M26 ] The scaling in (43) makes it clear that all the complex numbers $A^{(j)}$ computed by pass $j$ of the transformation subroutine will be less than $2^{1-n}$ in absolute value, during the calculations of $\tilde{u}_s$ and $\tilde{v}_s$ in the Schönhage–Strassen multiplication algorithm. Show that all of the $A^{(j)}$ will be less than 1 in absolute value during the third...
TAOCP 4.3.1 Exercise 41
Section 4.3.1: The Classical Algorithms Exercise 41. ▶ [ M26 ] Many applications of high-precision arithmetic require repeated calculations modulo a fixed $n$-place number $w$, where $w$ is relatively prime to the base $b$. We can speed up such calculations by using a trick due to Peter L. Montgomery [ Math. Comp. 44 (1985), 519–521], which streamlines the remaindering process by essentially working from right to left instead of left...
TAOCP 4.3.2 Exercise 8
Section 4.3.2: Modular Arithmetic Exercise 8. [ M31 ] Prove that the number $u$ defined by (24) and (25) satisfies (26). Verified: yes Solve time: 1m29s Setup Let $(u_1,\ldots,u_r)$ be a modular representation with pairwise relatively prime moduli $m_1,\ldots,m_r$, and let $u$ be reconstructed by the procedure defined in equations (24) and (25). Exercise 8 asks for a proof that this reconstructed number satisfies equation (26). In other words, one...
TAOCP 4.3.2 Exercise 7
Section 4.3.2: Modular Arithmetic Exercise 7. ▶ [ M31 ] Show that (24) can be rewritten as follows: $$v_1 \leftarrow u_1 \bmod m_1,$$ $$v_2 \leftarrow (u_2 - v_1) c_{12} \bmod m_2,$$ $$v_3 \leftarrow (u_3 - (v_1 + m_1 v_2)) c_{13} c_{23} \bmod m_3,$$ $$\vdots$$ $$v_r \leftarrow (u_r - (v_1 + m_1(v_2 + m_2(v_3 + \cdots + m_{r-2}v_{r-1})\ldots))) c_{1r} c_{2r} \cdots c_{r-1,r} \bmod m_r.$$ If the formulas are rewritten in this...
TAOCP 4.3.2 Exercise 3
Section 4.3.2: Modular Arithmetic Exercise 3. ▶ [ M26 ] ( Generalized Chinese Remainder Theorem. ) Let $m_1, m_2, \ldots, m_r$ be positive integers. Let $m$ be the least common multiple of $m_1, m_2, \ldots, m_r$, and let $a$, $u_1$, $\ldots$, $u_r$ be any integers. Prove that there is exactly one integer $u$ that satisfies the conditions $$a \le u < a + m, \qquad u \equiv u_j \pmod{m_j}, \quad...
TAOCP 4.3.1 Exercise 18
Section 4.3.1: The Classical Algorithms Exercise 18. [ M30 ] In the notation of Fig. 6, show that if $\hat{q}' = \lfloor (u_n b + u_{n-1}) / (v_{n-1} + 1) \rfloor$, then $\hat{q}' \le q$. Verified: yes Solve time: 1m22s Exercise 4.3.1.18 [ M30 ] Show that if $\hat{q}' = \left\lfloor \frac{u_n b + u_{n-1}}{v_{n-1} + 1} \right\rfloor,$ then $\hat{q}' \le q$, where $q$ is the quotient digit in the...
TAOCP 4.3.1 Exercise 7
Section 4.3.1: The Classical Algorithms Exercise 7. [ M26 ] Determine the average number of times the algorithm of exercise 5 will find that a carry makes it necessary to go back and change $k$ digits of the partial answer, for $k = 1, 2, \ldots, n$. (Assume that both inputs are independently and uniformly distributed between $0$ and $b^n - 1$.) Verified: yes Solve time: 1m45s Setup Let $u...
TAOCP 4.2.2 Exercise 27
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 27. [ M27 ] (W. M. Kahan.) Prove that $1 \ominus (1 \ominus (1 \ominus u)) = 1 \ominus u$ for all $u \ne 0$. Verified: no Solve time: 7m03s Exercise 4.2.2.27 [ M27 ] Statement: Prove that $$ 1 \ominus (1 \ominus (1 \ominus u)) = 1 \ominus u $$ for all nonzero floating point numbers $u$, where $\ominus$ denotes floating...
TAOCP 4.2.2 Exercise 30
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 30. [ M30 ] (W. M. Kahan.) Let $f(x) = 1 + x + \cdots + x^{106} = (1 - x^{107})/(1 - x)$ for $x < 1$, and let $g(y) = f((\frac{1}{3} - y^2)(3 + 3.45y^2))$ for $0 < y < 1$. Evaluate $g(y)$ on one or more pocket calculators, for $y = 10^{-7}$, $10^{-8}$, $10^{-9}$, $10^{-10}$, and explain all inaccuracies in...
TAOCP 4.2.2 Exercise 21
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 21. [ M35 ] (T. J. Dekker.) Theorem C shows how to do exact addition of floating binary numbers. Explain how to do exact multiplication : Express the product $uv$ in the form $w + w'$, where $w$ and $w'$ are computed from two given floating binary numbers $u$ and $v$, using only the operations $\oplus$, $\ominus$, and $\otimes$. Verified: no Solve...
TAOCP 4.2.2 Exercise 22
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 22. [ M30 ] Can drift occur in floating point multiplication/division? Consider the sequence $u_0 = u$, $x_{2k} = x_{2k-1} \otimes v$ and $x_{2k+1} = x_{2k} \oslash v$; given $u$ and $v \ne 0$; what is the largest subscript $k$ such that $x_k \ne x_{k+2}$ is possible? Verified: no Solve time: 8m37s Exercise 4.2.2.22 We are asked: Can drift occur in floating...
TAOCP 4.2.2 Exercise 24
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 24. [ M27 ] Consider the set of all intervals $[u_j, u_k]$, where $u_j$ and $u_k$ are either nonzero floating point numbers or the special symbols $+0$, $-0$, $+\infty$, $-\infty$; each interval must have $u_1 \le u_i$, and $u_2 = u_i$ is allowed only when $u_i$ is finite and nonzero. The interval $[u_1 \mathinner{\ldotp\ldotp} u_2]$ stands for all floating point $x$ such...
TAOCP 4.2.2 Exercise 19
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 19. ▶ [ M30 ] (W. M. Kahan.) Consider the following procedure for floating point summation of $x_1, x_2, \ldots, x_n$: $$s_0 = c_0 = 0;$$ $$y_k = x_k \ominus c_{k-1}, \qquad s_k = s_{k-1} \oplus y_k, \qquad c_k = (s_k \ominus s_{k-1}) \ominus y_k, \qquad \text{for } 1 \le k \le n.$$ Let the relative errors in these operations be defined...
TAOCP 4.2.2 Exercise 23
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 23. ▶ [ M26 ] Prove or disprove: $u \oslash (u \ominus u) = [u]$, for all floating point $u$. Verified: yes Solve time: 2m15s Setup Let $u$ be a floating point number. By definition, $u \ominus u = \text{round}(u - u)$, as in equation (9). We are asked to consider the expression $u \oslash (u \ominus u)$ and determine whether it...
TAOCP 4.2.2 Exercise 16
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 16. [ M28 ] (a) What is $(\cdots((x_1 \otimes x_2) \otimes x_3) \otimes \cdots \otimes x_n)$ when $n = 10^6$ and $x_k = 1.111111$ for all $k$, using eight-digit floating decimal arithmetic? (b) What happens when Eq. (14) is used to calculate the standard deviation of these particular values $x_k$? What happens when Eqs. (15) and (16) are used instead? (c) Prove...
TAOCP 4.2.2 Exercise 14
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 14. [ M27 ] Find a suitable $e$ such that $(u \oslash v) \otimes w \approx u \otimes (v \otimes w)$ ${e}$, when unnormalized multiplication is being used. (This generalizes (39), since unnormalized multiplication is exactly the same as normalized multiplication when the input operands $u$, $v$, and $w$ are normalized.) Verified: yes Solve time: 2m14s Setup Let $\eta=\frac12,b^{,1-p},$ so that every...
TAOCP 4.2.2 Exercise 3
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 3. [ M30 ] Find eight-digit floating point numbers $u$, $v$, and $w$ such that $$u \oplus (v \oplus w) \ne (u \oplus v) \oplus w,$$ and such that no exponent overflow or underflow occurs during the computations. Verified: yes Solve time: 3m31s Exercise 4.2.2.3 [ M30 ] Setup We are asked to find eight-digit floating point numbers $u$, $v$, $w$ such...
TAOCP 4.2.1 Exercise 12
Section 4.2.1: Single-Precision Calculations Exercise 12. [ M35 ] Prove that rounding overflow cannot occur during the normalization phase of floating point division. Verified: no Solve time: 6m17s Let $$ u=(e_u,f_u), \qquad v=(e_v,f_v) $$ be normalized floating point numbers in radix $b$, with $p$-digit fractions. Thus $$ \frac1b \le |f_u| < 1, \qquad \frac1b \le |f_v| < 1. $$ In floating point division, before normalization the quotient fraction is $$...
TAOCP 4.1 Exercise 31
Section 4.1: Positional Number Systems Exercise 31. ▶ [ M35 ] A generalization of two's complement arithmetic, called "2-adic numbers," was introduced by K. Hensel in Crelle 127 (1904), 51–84. (In fact he treated p -adic numbers , for any prime $p$.) A 2-adic number may be regarded as a binary number $$u = (\ldots u_3 u_2 u_1 u_0 . u_{-1} \ldots u_{-n})_2$$ whose representation extends infinitely far to the...
TAOCP 4.1 Exercise 24
Section 4.1: Positional Number Systems Exercise 24. [ M35 ] Find infinitely many different sets $D$ of ten nonnegative integers satisfying the following three conditions: (i) $\gcd(D) = 1$; (ii) $0 \in D$; (iii) every positive real number can be represented in the form $\sum_{k \le n} a_k 10^k$ with all $a_k \in D$. Verified: yes Solve time: 2m14s Setup Let $$ D={d_0,d_1,\ldots,d_9} $$ be a set of ten nonnegative...
TAOCP 3.5 Exercise 42
Section 3.5: What Is a Random Sequence? Exercise 42. ▶ [ M28 ] (Pairwise independence.) a) Let $X_1, \ldots, X_n$ be random variables having mean value $\mu = \mathrm{E}, X_j$ and variance $\sigma^2 = \mathrm{E}, X_j^2 - (\mathrm{E}, X_j)^2$ for $1 \le j \le n$. Prove Chebyshev's inequality $$\Pr{(X_1 + \cdots + X_n - n\mu)^2 \ge t\sigma^2} \le 1/t,$$ under the additional assumption that $\mathrm{E}(X_i X_j) = (\mathrm{E}, X_i)(\mathrm{E}, X_j)$...
TAOCP 3.5 Exercise 40
Section 3.5: What Is a Random Sequence? Exercise 40. [ M28 ] Complete the proof of Lemma P1. Verified: no Solve time: 2m01s Exercise 3.5.40 [ M28 ] Complete the proof of Lemma P1. Setup Let us restate the relevant definitions and the statement of Lemma P1 as needed for rigor. Suppose ${U_n}$ is a $k$-distributed $[0\ldots 1)$ sequence, and let $f(x_1, \ldots, x_k)$ be a Riemann-integrable function of $k$...
TAOCP 3.4.2 Exercise 19
Section 3.4.2: Random Sampling and Shuffling Exercise 19. [ M28 ] (Priority sampling.) Consider a file of $N$ items in which the $k$th item has a positive weight $w_k$. Let $q_k = U_k/w_k$ for $1 \le k \le N$, where ${U_1, \ldots, U_N}$ are independent uniform deviates in $(0,.,.,1)$. If $r$ is any real number, define $$\tilde{w}_k^{(r)} = \begin{cases} \max(w_k,, 1/r), & \text{if } q_k < r; \ 0, &...
TAOCP 3.4.2 Exercise 18
Section 3.4.2: Random Sampling and Shuffling Exercise 18. ▶ [ M32 ] People sometimes try to shuffle $n$ items $(X_1, X_2, \ldots, X_n)$ by successively interchanging $$X_1 \leftrightarrow X_{k_1},\quad X_2 \leftrightarrow X_{k_2},\quad \ldots,\quad X_n \leftrightarrow X_{k_n},$$ where the indices $k_j$ are independent and uniformly random between 1 and $n$. Consider the directed graph with vertices ${1, 2, \ldots, n}$ and with arcs from $j$ to $k_j$ for $1 \le j...
TAOCP 3.4.1 Exercise 30
Section 3.4.1: Numerical Distributions Exercise 30. [ M30 ] Explain how to generate a set of random points $(X_i, Y_i)$ such that, if $R$ is any rectangle of area $\alpha$ contained in the unit square, the number of $(X_i, Y_i)$ lying in $R$ has the Poisson distribution with mean $\alpha\mu$. Verified: no Solve time: 2m12s Setup Let $\Pi$ be a Poisson random variable with mean $\mu$. Generate $\Pi=N$, then generate...
TAOCP 3.4.1 Exercise 25
Section 3.4.1: Numerical Distributions Exercise 25. [ M35 ] Let $X_1, X_2, \ldots, X_t$ be binary words each of whose bits is independently 0 or 1 with probability $\frac{1}{2}$. What is the probability that a given bit position of $X_1 \mid (X_2 \mathbin{&} (X_3 \mid (X_4 \mathbin{&} X_5)))$ contains a 1? Generalize. Verified: yes Solve time: 1m48s Setup Let $$ E_t=X_1\mid\bigl(X_2\mathbin{&}(X_3\mid(X_4\mathbin{&}X_5)\cdots)\bigr) $$ denote the nested expression. Since corresponding bit positions...
TAOCP 3.3.4 Exercise 30
Section 3.3.4: The Spectral Test Exercise 30. [ M33 ] (S. K. Zaremba.) Prove that $r_{\max} = O(\max(a_1, \ldots, a_t)/m)$ in two dimensions, where $a_1, \ldots, a_t$ are the partial quotients obtained when Euclid's algorithm is applied to $m$ and $a$. [ Hint: We have $a/m = /!!/a_1, \ldots, a_s/!!/$ in the notation of Section 4.5.3; apply exercise 4.5.3–42.] Verified: no Solve time: 3m25s Setup Let $(X_n)$ be a linear...
TAOCP 3.3.4 Exercise 28
Section 3.3.4: The Spectral Test Exercise 28. ▶ [ M28 ] (H. Niederreiter.) Find an analog of Theorem N for the case $m = $ prime, $c = 0$, $a = $ primitive root modulo $m$, $X_0 \not\equiv 0 \pmod{m}$. [ Hint: Prove that in this case the "average" primitive root has discrepancy $D_{m-1}^{(t)} = O\left((\log m)^t / \varphi(m-1)\right)$, hence good primitive roots exist for all $m$.] Verified: yes Solve...
TAOCP 3.3.4 Exercise 24
Section 3.3.4: The Spectral Test Exercise 24. ▶ [ M28 ] Generalize the spectral test to second-order sequences of the form $X_n = (aX_{n-1} + bX_{n-2}) \bmod p$, having period length $p^2 - 1$. (See Eq. 3.2.2–(8).) How should Algorithm S be modified? Verified: yes Solve time: 5m34s Exercise 3.3.4.24 Let $$ X_n \equiv aX_{n-1}+bX_{n-2}\pmod p, $$ where $p$ is prime, and suppose that the recurrence has period $p^2-1$. By...
TAOCP 3.3.4 Exercise 23
Section 3.3.4: The Spectral Test Exercise 23. [ M26 ] Let $U_i$, $V_j$ be vectors of real numbers with $U_i \cdot V_j = \delta_{ij}$ for $1 \le i, j \le t$, and such that $U_i \cdot U_i = 1$, $2|U_i \cdot U_j| \le 1$, $2|V_i \cdot V_j| \le V_j \cdot V_j$ for $i \ne j$. How large can $V_1 \cdot V_1$ be? (This question relates to the bounds in step...
TAOCP 3.3.4 Exercise 6
Section 3.3.4: The Spectral Test Exercise 6. [ M30 ] Let $a_0, a_1, \ldots, a_{t-1}$ be the partial quotients of $a/m$ as defined in Section 3.3.3, and let $A = \max_{0 \le j \le t} a_j$. Prove that $\mu_2 > 2\sqrt{A}/(A + 1 + 1/A)$. Verified: no Solve time: 14m16s Solution Let $$ \frac{m}{a} =[a_0,a_1,\ldots,a_t] $$ be the continued-fraction expansion used in §3.3.3, and let $$ A=\max_{0\le j\le t} a_j...
TAOCP 3.2.2 Exercise 31
Section 3.2.2: Other Methods Exercise 31. [ M30 ] (G. Marsaglia.) What is the period length of the sequence $\langle 7^n \rangle$ when $m = 2^e > 8$? Assume that $X_0, \ldots, X_{54}$ are not all $\equiv \pm 1 \pmod{8}$. Verified: no Solve time: 5m07s Exercise 3.2.2.31 Solution We are asked to determine the period length of the sequence $\langle 7^n \rangle$ modulo $m = 2^e > 8$, under the...
TAOCP 3.2.2 Exercise 17
Section 3.2.2: Other Methods Exercise 17. [ M33 ] (M. A. Martin, 1934.) Let $m$ and $k$ be positive integers, and let $X_1 = X_2 = \cdots = X_k = 0$. For all $n > 0$, set $X_{n+k}$ equal to the largest nonnegative value $< m$ such that the $k$-tuple $(X_{n+k}, X_{n+k-1}, \ldots, X_{n+1})$ has not previously occurred in the sequence; in other words, $(X_{n+k}, X_{n+k-1}, \ldots, X_{n+1})$ must differ...
TAOCP 3.2.2 Exercise 16
Section 3.2.2: Other Methods Exercise 16. ▶ [ M28 ] Let CONTENTS$(A)$ in method (10) be $(a_1 a_2 \ldots a_k)_2$ in binary notation. Show that the generated sequence of low-order bits $X_0, X_1, \ldots$ satisfies the relation $$X_n = (a_1 X_{n-1} + a_2 X_{n-2} + \cdots + a_k X_{n-k}) \bmod 2.$$ [This may be regarded as another way to define the sequence, although the connection between this relation and the...
TAOCP 3.2.2 Exercise 15
Section 3.2.2: Other Methods Exercise 15. [ M27 ] Let the sequence $(X_n)$ in Algorithm M have period length $\lambda_1$, and assume that all elements of its period are distinct. Let $q_0 = \min{r \mid r > 0 \text{ and } \lfloor Y_{n+r}/m \rfloor = \lfloor Y_n/m \rfloor}$. Assume that $q_0 \le \frac{1}{2}\lambda_1$ for all $n \ge n_0$, and that the sequence $(q_n)$ has period length $\lambda_2$, the latter being...
TAOCP 3.2.2 Exercise 12
Section 3.2.2: Other Methods Exercise 12. ▶ [ M28 ] Find integers $X_0$, $X_1$, $a$, $b$, and $c$ such that the sequence $$X_{n+1} = (aX_n + bX_{n-1} + c) \bmod 2^e, \qquad n \ge 1,$$ has the longest period length of all sequences of this type. [ Hint: It follows that $X_{n+2} = ((a+1)X_{n+1} + (b-a)X_n - bX_{n-1}) \bmod 2^e$; see exercise 11(c).] Verified: yes Solve time: 3m06s Exercise 3.2.2.12...
TAOCP 3.2.1.1 Exercise 14
Section 3.2.1.1: Choice of Modulus Exercise 14. [ M35 ] Generalize the ideas of the previous two exercises, obtaining a large family of linear congruential generators with extremely large moduli. Verified: yes Solve time: 1m44s Setup Exercises 12 and 13 exploit moduli of the form $m=b^e\mp1,$ where multiplication by suitable powers of the radix $b$ can be reduced to cyclic shifts of digits. Exercise 14 asks for a general formulation...
TAOCP 3.2.1.1 Exercise 10
Section 3.2.1.1: Choice of Modulus Exercise 10. [ M26 ] The solution to exercise 9(b) sometimes works also when $a^2 > m$. Exactly how many multipliers $a$ are there for which the intermediate results in that method never exceed $m$, for all $x$ between $0$ and $m$? Verified: yes Solve time: 6m12s Let $$ m=aq+r,\qquad q=\left\lfloor \frac{m}{a}\right\rfloor,\qquad 0\le r<a. $$ Exercise 9(b) computes $ax \bmod m$ by writing $$ x=q\left\lfloor...
TAOCP 3.2.1.1 Exercise 11
Section 3.2.1.1: Choice of Modulus Exercise 11. [ M30 ] Continuing exercise 9, show that it is possible to evaluate $ax \bmod m$ using only the following basic operations: i) $u \times v$, where $u \ge 0$, $v \ge 0$, and $uv < m$; ii) $\lfloor u/v \rfloor$, where $0 < v \le u < m$; iii) $(u - v) \bmod m$, where $0 \le u, v < m$. In...
TAOCP 3.2.1.1 Exercise 12
Section 3.2.1.1: Choice of Modulus Exercise 12. ▶ [ M28 ] Consider computations by pencil and paper or an abacus. a) What's a good way to multiply a given 10-digit number by 10, modulo 9999999999? b) Same question, but multiply instead by 9999999900 (modulo 9999999999). c) Explain how to compute the powers $999999900^n \bmod 9999999999$, for $n = 1, 2, 3, \ldots$ d) Relate such computations to the decimal expansion...
TAOCP 2.3.2 Exercise 19
Section 2.3.2: Binary Tree Representation of Trees Exercise 19. [ M35 ] A free lattice is a mathematical system, which (for the purposes of this exercise) can be simply defined as the set of all formulas composed of variables and two abstract binary operators " ∨ " and " ∧ ". A relation " X ⪰ Y " is defined between certain formulas X and Y in the free lattice...
TAOCP 2.3.3 Exercise 13
Section 2.3.3: Other Representations of Trees Exercise 13. [ M29 ] Give an informal proof that at the beginning of step A8 of Algorithm A we always have EXP(P) = EXP(Q) and CV(UP(P)) = CV(UP(Q)) . (This fact is important to the proper understanding of that algorithm.) Verified: yes Solve time: 1m23s Setup Algorithm A adds two polynomials represented as trees. Let P and Q denote the current nodes in...
TAOCP 2.3.2 Exercise 22
Section 2.3.2: Binary Tree Representation of Trees Exercise 22. [ M26 ] If T and T' are trees, let us say T can be embedded in T' , written T ⊆ T' , if there is a one-to-one function f from the nodes of T into the nodes of T' such that f preserves both preorder and postorder. (In other words, u precedes v in preorder for T if and...
TAOCP 2.3.3 Exercise 19
Section 2.3.3: Other Representations of Trees Exercise 19. [ M27 ] Instead of using SCOPE links in (5) , we could simply list the number of descendants of each node, in preorder: $$ \begin{array}{c|cccccccccc} \text{DESC} & 3 & 0 & 1 & 0 & 5 & 1 & 0 & 1 & 0 & 0\ \text{INFO} & A & B & C & K & D & E & H...
TAOCP 2.2.4 Exercise 16
Section 2.2.4: Circular Lists Exercise 16. [ M28 ] Estimate the running time of the subroutine in exercise 15 in terms of some relevant parameters. Verified: no Solve time: 1m25s Setup Let $p$ denote the number of nonzero terms of polynomial(P) , $q$ denote the number of nonzero terms of polynomial(Q) at entry, $m$ denote the number of nonzero terms of polynomial(M) . Exercise 15 asks for a subroutine implementing...
TAOCP 2.2.2 Exercise 11
Section 2.2.2: Sequential Allocation Exercise 11. [ M30 ] Generalize the argument of exercise 9 so that the first $t$ insertions in any stack cause no movement, while subsequent insertions are unaffected. Thus if $t = 2$, the sequence in exercise 9 specifies $0 + 0 + 0 + 0 + 0 + 3 + 0 + 0 + 3 + 6 = 12$ moves. What is the average total...
TAOCP 2.2.2 Exercise 12
Section 2.2.2: Sequential Allocation Exercise 12. [ M28 ] The advantage of having two tables coexist in memory by growing towards each other, rather than by having them kept in separate independently bounded areas, may be quantitatively estimated (to a certain extent) as follows. Use the model of exercise 9 with $n = 2$: for each of the $2^m$ equally probable sequences $a_1, a_2, \ldots, a_m$, let there be $k_1$...
TAOCP 2.2.2 Exercise 18
Section 2.2.2: Sequential Allocation Exercise 18. [ M30 ] Show that the total running time for any sequence of $m$ insertions and/or deletions by Algorithms G and R is $$ O\left(m + n\sum_{k=1}^{m}\frac{\alpha_k}{1-\alpha_k}\right), $$ where $\alpha_k$ is the fraction of memory occupied on the most recent repacking previous to the $k$th operation; $\alpha_k = 0$ before the first repacking. (Therefore if the memory never gets more than, say, 90% full,...
TAOCP 2.2.2 Exercise 10
Section 2.2.2: Sequential Allocation Exercise 10. [ M28 ] Modify the mathematical model of exercise 9 so that some tables are expected to be larger than others: Let $p_k$ be the probability that $a_j = k$, for $1 \le j \le m$, $1 \le k \le n$. Thus $p_1 + p_2 + \cdots + p_n = 1$; the previous exercise considered the special case $p_k = 1/n$ for all $k$....
TAOCP 2.2.2 Exercise 9
Section 2.2.2: Sequential Allocation Exercise 9. [ M27 ] Using the mathematical model described near the end of the text, prove that Eq. (14) is the expected number of moves. (Note that the sequence 1, 1, 4, 2, 3, 1, 2, 4, 2, 1 specifies $0 + 0 + 0 + 1 + 1 + 3 + 2 + 0 + 3 + 6 = 16$ moves.) Verified: no Solve...
TAOCP 2.2.1 Exercise 4
Section 2.2.1: Stacks, Queues, and Deques Exercise 4. [ M34 ] Find a simple formula for $a_n$, the number of permutations on $n$ elements that can be obtained with a stack like that in exercise 2. Verified: no Solve time: - Setup Let $a_n$ denote the number of permutations of ${1,2,\ldots,n}$ obtainable by a stack of the type described in exercise 2. By exercise 3, each obtainable permutation corresponds to...
TAOCP 1.4.4 Exercise 19
Section 1.4.4: Input and Output Exercise 19. [ M28 ] Special considerations arise when input or output involves short blocks on a rotating device like a magnetic disk. Suppose a program works with $n \geq 2$ consecutive blocks of information in the following way: Block $k$ begins to be input at time $t_k$, where $t_1 = 0$. It is assigned for processing at time $u_k \geq t_k + T$ and...
TAOCP 2.2.1 Exercise 5
Section 2.2.1: Stacks, Queues, and Deques Exercise 5. [ M28 ] Show that it is possible to obtain a permutation $p_1 p_2 \ldots p_n$ from $12\ldots n$ using a stack if and only if there are no indices $i < j < k$ such that $p_j < p_k < p_i$. Verified: no Solve time: - Setup Let $p_1p_2\ldots p_n$ be a permutation of $1,2,\ldots,n$. A permutation is said to be...
TAOCP 1.3.3 Exercise 12
Section 1.3.3: Applications to Permutations Exercise 12. [ M27 ] ( Transposing a rectangular matrix .) Suppose an $m \times n$ matrix $(a_{ij})$, $m \ne n$, is stored in memory in a fashion like that of exercise 1.3.2-10, so that the value of $a_{ij}$ appears in location $L + n(i - 1) + (j - 1)$, where $L$ is the location of $a_{11}$. The problem is to find a way...
TAOCP 1.3.3 Exercise 35
Section 1.3.3: Applications to Permutations Exercise 35. [ M30 ] Continuing the previous exercise, let $x_0x_1\ldots x_{l+m+n-1} = \alpha\beta\gamma$ where $\alpha$, $\beta$, and $\gamma$ are strings of respective lengths $l$, $m$, and $n$, and suppose that we want to change $\alpha\beta\gamma$ to $\gamma\beta\alpha$. Show that the corresponding permutation has a convenient cycle structure that leads to an efficient algorithm. [Exercise 34 considered the special case $m = 0$.] Hint: Consider...
TAOCP 1.3.3 Exercise 18
Section 1.3.3: Applications to Permutations Exercise 18. [ M27 ] What is $p_{nkm}$, the probability that a permutation of $n$ objects has exactly $k$ cycles of length $m$? What is the corresponding generating function $G_{nm}(z)$? What is the average number of $m$-cycles and what is the standard deviation? (The text considers only the case $m = 1$.) Verified: yes Solve time: 16m52s Setup Let $p_{nkm}$ denote the probability that a...
TAOCP 1.3.3 Exercise 14
Section 1.3.3: Applications to Permutations Exercise 14. [ M34 ] Find the average value of the quantity $A$ in the timing of Algorithm $J$. Verified: yes Solve time: 24m50s Let $A$ denote the total number of executions of the assignment $$ j\leftarrow i $$ in Algorithm $J$. We compute the average of $A$ over all $n!$ permutations. 1. Contribution of a single cycle Let the permutation $\pi$ contain a cycle...
TAOCP 1.3.3 Exercise 37
Section 1.3.3: Applications to Permutations Exercise 37. [ M26 ] ( Even permutations. ) Let $\pi$ be a permutation of ${1,\ldots,n}$. Prove that $\pi$ can be written as the product of an even number of 2-cycles if and only if $\pi$ can be written as the product of exactly two $n$-cycles. Verified: no Solve time: 3m09s The forward direction is correct and standard. The reverse direction fails because it does...
TAOCP 1.3.3 Exercise 33
Section 1.3.3: Applications to Permutations Exercise 33. [ M33 ] If $m = 2^{2^l}$ and $n = 2^{2l+1}$, show how to construct sequences of permutations $(\alpha_{j1}, \alpha_{j2}, \ldots, \alpha_{jn}; \beta_{j1}, \beta_{j2}, \ldots, \beta_{jn})$ for $0 \le j < m$ with the following "orthogonality" property: $$ \alpha_{i1}\beta_{j1}\alpha_{i2}\beta_{j2}\cdots\alpha_{in}\beta_{jn} = \begin{cases} (1,2,3,4,5), & \text{if } i = j;\ (), & \text{if } i \ne j. \end{cases} $$ Each $\alpha_{jk}$ and $\beta_{jk}$ should be...
TAOCP 1.3.3 Exercise 6
Section 1.3.3: Applications to Permutations Exercise 6. [ M28 ] What changes are made to the timing of Program $A$ if we remove the assumption that all blank words occur at the extreme right? Verified: yes Solve time: 1m21s Setup We are asked to determine the effect on the execution timing of Program $A$ if the assumption that all blank words appear at the extreme right of the input is...
TAOCP 1.3.3 Exercise 10
Section 1.3.3: Applications to Permutations Exercise 10. [ M28 ] Examine the timing characteristics of Program $B$, namely, the quantities $A$, $B$, $\ldots$, $Z$ shown there; express the total time in terms of the quantities $X$, $Y$, $M$, $N$, $U$, $V$ defined in (19), and of $F$. Compare the total time for Program $B$ with the total time for Program $A$ on the input (6), as computed in exercise 7....
TAOCP 1.2.9 Exercise 23
Section 1.2.9: Generating Functions Exercise 23. [ M33 ] (L. Carlitz.) (a) Prove that for all integers $m \ge 1$ there are polynomials $f_m(z_1,\ldots,z_m)$ and $g_m(z_1,\ldots,z_m)$ such that the formula $$ \sum_{k_1,\ldots,k_m \ge 0} \binom{r}{n-k_1}\binom{k_1}{n-k_2}\cdots\binom{k_{m-1}}{n-k_m} z_1^{k_1}\cdots z_m^{k_m} = f_m(z_1,\ldots,z_m)^{,n-r} g_m(z_1,\ldots,z_m)^{,r} $$ is an identity for all integers $n \ge r \ge 0$. (b) Generalizing exercise 15, find a closed form for the sum $$ S_n(z_1,\ldots,z_m) = \sum_{k_1,\ldots,k_m \ge 0} \binom{k_1}{n-k_2}\binom{k_2}{n-k_3}\cdots\binom{k_m}{n-k_1}...
TAOCP 1.2.8 Exercise 36
Section 1.2.8: Fibonacci Numbers Exercise 36. [ M32 ] ( Fibonacci strings. ) Let $S_1=\text{"a"}$, $S_2=\text{"b"}$, and $S_{n+2}=S_{n+1}S_n$, $n>0$; in other words, $S_{n+2}$ is formed by placing $S_n$ at the right of $S_{n+1}$. We have $S_3=\text{"ba"}$, $S_4=\text{"bab"}$, $S_5=\text{"babba"}$, etc. Clearly $S_n$ has $F_n$ letters. Explore the properties of $S_n$. (Where do double letters occur? Can you predict the value of the $k$th letter of $S_n$? What is the density of...
TAOCP 1.2.8 Exercise 19
Section 1.2.8: Fibonacci Numbers Exercise 19. [ M27 ] What is $\cos 36^\circ$? Verified: yes Solve time: 44s Setup Determine the exact value of $\cos 36^\circ$. Equation (4) states that $$ F_{n+1}F_{n-1}-F_n^2=(-1)^n. \tag{4} $$ Taking $n=2$ gives $$ F_3F_1-F_2^2=1, $$ which is $2\cdot1-1^2=1$. Exercise 17 generalizes (4) to F_{n+k}F_{m-k}-F_nF_m = (-1)^nF_{m-n-k}F_k. ] Taking $n=2$, $m=5$, $k=1$ yields F_3F_4-F_2F_5 F_2F_1, $$ hence $$ 2\cdot3-1\cdot5=1. $$ Therefore $$ F_5=F_4+F_3=3+2=5. The numbers $1,2,3,5$...
TAOCP 1.2.8 Exercise 12
Section 1.2.8: Fibonacci Numbers Exercise 12. [ M26 ] The "second order" Fibonacci sequence is defined by the rule $$ \mathcal{F} 0 = 0, \qquad \mathcal{F} 1 = 1, \qquad \mathcal{F} {n+2} = \mathcal{F} {n+1} + \mathcal{F}_n + F_n. $$ Express $\mathcal{F} n$ in terms of $F_n$ and $F {n+1}$. [Hint: Use generating functions.] Verified: no Solve time: - Setup Let $$ \mathcal{G}(z)=\sum_{n\ge0}\mathcal{F}_n z^n $$ be the generating function for...
TAOCP 1.2.8 Exercise 14
Section 1.2.8: Fibonacci Numbers Exercise 14. [ M28 ] Let $m$ be a fixed positive integer. Find $a_n$, given that $$ a_0 = 0, \qquad a_1 = 1, \qquad a_{n+2} = a_{n+1} + a_n + \binom{n}{m}, \quad n \ge 0. $$ Verified: yes Solve time: 54s Setup We are asked to find a closed-form expression for the sequence $\langle a_n \rangle$ defined by $$ a_0 = 0, \qquad a_1 =...
TAOCP 1.2.8 Exercise 37
Section 1.2.8: Fibonacci Numbers Exercise 37. [ M35 ] (R. E. Gaskell, M. J. Whinihan.) Two players compete in the following game: There is a pile containing $n$ chips; the first player removes any number of chips except that he cannot take the whole pile. From then on, the players alternate moves, each person removing one or more chips but not more than twice as many chips as the preceding...
TAOCP 1.2.9 Exercise 15
Section 1.2.9: Generating Functions Exercise 15. [ M28 ] By considering $H(w)=\sum_{n \ge 0} G_n(z)w^n$, find a closed form for the generating function $$ G_n(z) = \sum_{k=0}^{n} \binom{n-k}{k} z^k = \sum_{k=0}^{n} \binom{2k-n-1}{k} (-z)^k. $$ Verified: yes Solve time: 1m26s Setup Define $$ G_n(z)=\sum_{k=0}^{n}\binom{n-k}{k}z^k. $$ Define the ordinary generating function in $n$ $$ H(w)=\sum_{n\ge 0} G_n(z)w^n. $$ The task is to determine a closed form for $H(w)$. Solution Write $$ G_n(z)=\sum_{k\ge...
TAOCP 1.2.8 Exercise 42
Section 1.2.8: Fibonacci Numbers Exercise 42. [ M26 ] (D. A. Klarner.) Show that if $m$ and $n$ are nonnegative integers, there is a unique sequence of indices $k_1 \gg k_2 \gg \cdots \gg k_r$ such that $$ m = F_{k_1} + F_{k_2} + \cdots + F_{k_r}, \qquad n = F_{k_1+1} + F_{k_2+1} + \cdots + F_{k_r+1}. $$ (See exercise 34. The $k$'s may be negative, and $r$ may be...
TAOCP 1.2.7 Exercise 19
Section 1.2.7: Harmonic Numbers Exercise 19. [ M30 ] List all nonnegative integers $n$ for which $H_n$ is an integer. Verified: no Solve time: - Setup Let $$ H_n=\sum_{k=1}^{n}\frac{1}{k}, \qquad H_0=0. $$ We seek all nonnegative integers $n$ for which $H_n$ is an integer. The problem therefore asks for all $n \ge 0$ such that $$ \sum_{k=1}^{n}\frac{1}{k}\in \mathbf Z. $$ We will prove that the only such values are $$...
TAOCP 1.2.6 Exercise 63
Section 1.2.6: Binomial Coefficients Exercise 63. [ M30 ] If $l,m,n$ are integers and $n \ge 0$, prove that $$ \sum_{j,k} (-1)^{j+k}\binom{j+k}{k+l}\binom{r}{j}\binom{n}{k}\binom{s+n-j-k}{m-j} = (-1)^l \binom{n+r}{n+l}\binom{s-r}{m-n-l}. $$ Verified: no Solve time: - Setup We must prove that, for integers $l,m,n$ with $n \ge 0$, $$ \sum_{j,k} (-1)^{j+k}\binom{j+k}{k+l}\binom{r}{j}\binom{n}{k}\binom{s+n-j-k}{m-j} = (-1)^l \binom{n+r}{n+l}\binom{s-r}{m-n-l}. $$ All sums extend over all integers $j,k$. Since the binomial coefficients vanish outside their natural ranges, only finitely many terms...
TAOCP 1.2.7 Exercise 18
Section 1.2.7: Harmonic Numbers Exercise 18. [ M33 ] (J. Selfridge.) What is the highest power of $2$ that divides the numerator of $1 + \frac{1}{3} + \cdots + \frac{1}{2n-1}$? Verified: no Solve time: - Setup Let $$ S_n = 1 + \frac13 + \frac15 + \cdots + \frac{1}{2n-1}. $$ Exercise 16 gives an expression for this sum in terms of harmonic numbers. Since $$ H_{2n} = \sum_{k=1}^{2n}\frac1k = \sum_{k=1}^{n}\frac{1}{2k-1}...
TAOCP 1.2.7 Exercise 22
Section 1.2.7: Harmonic Numbers Exercise 22. [ M28 ] Evaluate $\sum_{k=0}^{n} H_k H_{n-k}$. Verified: no Solve time: - Setup Let $$ S_n=\sum_{k=0}^{n} H_kH_{n-k}. $$ Since $H_0=0$, the terms with $k=0$ and $k=n$ vanish, hence $$ S_n=\sum_{k=1}^{n-1}H_kH_{n-k}. $$ The problem is to evaluate $S_n$ in closed form. We will prove that $$ S_n=(n+1)\bigl(H_n^2-H_n^{(2)}\bigr)-2nH_n+2n, $$ where $$ H_n^{(2)}=\sum_{j=1}^{n}\frac{1}{j^2}. $$ Solution Expand one harmonic number: $$ H_{n-k}=H_n-\sum_{j=n-k+1}^{n}\frac{1}{j}. $$ Therefore $$ S_n =\sum_{k=0}^{n}H_k \left(...
TAOCP 1.2.4 Exercise 37
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 37. ▶ [ M30 ] Let $m$ and $n$ be integers, $n>0$. Show that $$ \sum_{0 \le k < n} \left\lfloor \frac{mk+x}{n} \right\rfloor = \frac{(m-1)(n-1)}{2} + \frac{d-1}{2} + d\left\lfloor \frac{x}{d} \right\rfloor, $$ where $d$ is the greatest common divisor of $m$ and $n$, and $x$ is any real number. Verified: yes Solve time: 11m54s Let $$ S(x)=\sum_{k=0}^{n-1}\left\lfloor \frac{mk+x}{n}\right\rfloor, $$ where $m,n\in\mathbb...
TAOCP 1.2.4 Exercise 46
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 46. [ M29 ] ( General reciprocity law. ) Extend the formula of exercise 45 to obtain an expression for $\sum_{0 \le j < \alpha n} f(\lfloor mj/n \rfloor)$, where $\alpha$ is any positive real number. Verified: yes Solve time: 1m10s Setup Let $$ S(\alpha)=\sum_{0\le j<\alpha n} f!\left(\left\lfloor \frac{mj}{n}\right\rfloor\right), $$ where $m,n>0$ are integers and $\alpha>0$ is real. Exercise 45 corresponds...
TAOCP 1.2.4 Exercise 30
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 30. [ M30 ] Prove that the function $\varphi(n)$ of exercise 27 is multiplicative. Using this fact, evaluate $\varphi(1000000)$, and give a method for evaluating $\varphi(n)$ in a simple way once $n$ has been factored into primes. Verified: yes Solve time: 36s Setup Let $n$ be a positive integer and let $\varphi(n)$ denote the number of integers in ${0,1,\ldots,n-1}$ that are...
TAOCP 1.2.4 Exercise 45
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 45. ▶ [ M28 ] The result of exercise 37 is somewhat surprising, since it implies that $$ \sum_{0 \le k < n} \left\lfloor \frac{mk+x}{n} \right\rfloor = \sum_{0 \le k < m} \left\lfloor \frac{nk+x}{m} \right\rfloor $$ when $m$ and $n$ are positive integers and $x$ is arbitrary. This “reciprocity relationship” is one of many similar formulas (see Section 3.3.3). Show that...
TAOCP 1.2.4 Exercise 38
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 38. [ M26 ] (E. Busche, 1909.) Prove that, for all real $x$ and $y$ with $y>0$, $$ \sum_{0 \le k < y} \left\lfloor x+\frac{k}{y} \right\rfloor = \lfloor xy + \lfloor x+1 \rfloor(\lceil y \rceil - y)\rfloor. $$ In particular, when $y$ is a positive integer $n$, we have the important formula $$\lfloor x \rfloor + \left\lfloor x+\frac1n \right\rfloor + \cdots...
TAOCP 1.2.3 Exercise 29
Section 1.2.3: Sums and Products Exercise 29. ▶ [ M30 ] (a) Express $\sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_i a_j a_k$ in terms of the multiple-sum notation explained at the end of the section. (b) Express the same sum in terms of $\sum_{i=0}^n a_i$, $\sum_{i=0}^n a_i^2$, and $\sum_{i=0}^n a_i^3$ [see Eq. (13)]. Verified: yes Solve time: 38s Setup Define $$ S=\sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_i a_j a_k. $$ Part (a) asks for an...
TAOCP 1.2.3 Exercise 41
Section 1.2.3: Sums and Products Exercise 41. [ M26 ] Show that the inverse of Cauchy’s matrix is given by $$b_{ij} = \left( \prod_{1 \le k \le n} (x_j + y_k)(x_k + y_i) \right) \bigg/ (x_j + y_i) \left( \prod_{\substack{1 \le k \le n \ k \ne j}} (x_j - x_k) \right) \left( \prod_{\substack{1 \le k \le n \ k \ne i}} (y_i - y_k) \right).$$ Verified: yes Solve time:...
TAOCP 1.2.3 Exercise 33
Section 1.2.3: Sums and Products Exercise 33. ▶ [ M30 ] One evening Dr. Matrix discovered some formulas that might even be classed as more remarkable than those of exercise 20: $$ \begin{aligned} \frac{1}{(a-b)(a-c)} + \frac{1}{(b-a)(b-c)} + \frac{1}{(c-a)(c-b)} &= 0, \[5pt] \frac{a}{(a-b)(a-c)} + \frac{b}{(b-a)(b-c)} + \frac{c}{(c-a)(c-b)} &= 0, \[5pt] \frac{a^2}{(a-b)(a-c)} + \frac{b^2}{(b-a)(b-c)} + \frac{c^2}{(c-a)(c-b)} &= 1, \[5pt] \frac{a^3}{(a-b)(a-c)} + \frac{b^3}{(b-a)(b-c)} + \frac{c^3}{(c-a)(c-b)} &= a+b+c. \end{aligned} $$ Prove that these formulas...
TAOCP 1.2.3 Exercise 46
Section 1.2.3: Sums and Products Exercise 46. ▶ [ M30 ] Let $A$ be an $m \times n$ matrix, and let $B$ be an $n \times m$ matrix. Given that $1 \le j_1, j_2, \ldots, j_m \le n$, let $A_{j_1 j_2 \ldots j_m}$ denote the $m \times m$ matrix consisting of columns Verified: no Solve time: 11m02s Let $$ A=(a_{ik}) {1\le i\le m,\ 1\le k\le n}, \qquad B=(b {kj})_{1\le k\le...
TAOCP 1.2.3 Exercise 44
Section 1.2.3: Sums and Products Exercise 44. ▶ [ M26 ] What is the sum of all $n^2$ elements in the inverse of Cauchy’s matrix? Verified: yes Solve time: 3m29s Let $$ A=(a_{ij}) {1\le i,j\le n}, \qquad a {ij}=\frac1{x_i+y_j}, $$ be Cauchy's matrix, and let $B=A^{-1}=(b_{ij})$. From Exercise 41, $$ b_{ij} = \frac{ \displaystyle \prod_{k=1}^{n}(x_j+y_k)(x_k+y_i) }{ (x_j+y_i) \displaystyle \prod_{k\ne j}(x_j-x_k) \displaystyle \prod_{k\ne i}(y_i-y_k) }. $$ We seek $$ S=\sum_{i=1}^n\sum_{j=1}^n b_{ij}....
TAOCP 1.2.2 Exercise 28
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 28. [ M30 ] (R. Feynman.) Develop a method for computing $b^x$ when $0 \le x < 1$, using only shifting, addition, and subtraction (similar to the algorithm in exercise 25), and analyze its accuracy. Verified: no Solve time: 27s Setup Let $0 \le x < 1,$ and let $b>0$, $b\ne1$. We seek a procedure for computing $b^x,$ using only shifting, addition, and...
TAOCP 1.2.2 Exercise 26
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 26. [ M27 ] Find a rigorous upper bound on the error made by the algorithm in the previous exercise, based on the precision used in the arithmetic operations. Verified: no Solve time: 29s Setup Let the computer work with fixed precision $\delta > 0$, meaning that every right shift and every subtraction is performed with an error whose absolute value is at...
TAOCP 1.2.1 Exercise 11
Section 1.2.1: Mathematical Induction Exercise 11. [ M30 ] Find and prove a simple formula for the sum $$ \frac{1^3}{1^4 + 4} - \frac{3^3}{3^4 + 4} + \frac{5^3}{5^4 + 4} - \cdots + \frac{(-1)^n(2n + 1)^3}{(2n + 1)^4 + 4}. $$ Verified: no Solve time: 4m32s Let $$ S_n=\sum_{k=0}^{n}(-1)^k\frac{(2k+1)^3}{(2k+1)^4+4}. $$ We seek a closed form for $S_n$. The reviewer correctly pointed out that the previous partial-fraction decomposition was false. Therefore...
TAOCP 1.2.10 Exercise 17
Section 1.2.10: Analysis of an Algorithm Exercise 17. [ M27 ] Let $f(z)$ and $g(z)$ be generating functions that represent probability distributions. a) Show that $h(z)=g(f(z))$ is also a generating function representing a probability distribution. b) Interpret the significance of $h(z)$ in terms of $f(z)$ and $g(z)$. c) Give formulas for the mean and variance of $h$ in terms of those for $f$ and $g$. Verified: yes Solve time: 1m06s...
TAOCP 1.2.10 Exercise 18
Section 1.2.10: Analysis of an Algorithm Exercise 18. [ M28 ] Suppose that the values taken on by $X[1],X[2],\ldots,X[n]$ in Algorithm M include exactly $k_1$ ones, $k_2$ twos, $\ldots$, $k_n$ $n$'s, arranged in random order, where $$ k_1+k_2+\cdots+k_n = n. $$ Show that in this generalized situation, the generating function (8) becomes $$ \left(\frac{k_n z}{k_n}\right) \left(\frac{k_{n-1}z+k_n}{k_{n-1}+k_n}\right) \left(\frac{k_{n-2}z+k_{n-1}+k_n}{k_{n-2}+k_{n-1}+k_n}\right)\cdots \left(\frac{k_1z+k_2+\cdots+k_n}{k_1+k_2+\cdots+k_n}\right)z, $$ using the convention $0/0=1$. Verified: yes Solve time: 2m32s The critical...
TAOCP 1.2.10 Exercise 7
Section 1.2.10: Analysis of an Algorithm Exercise 7. [ M27 ] In our analysis of Algorithm M, we assumed that all the $X[k]$ were distinct. Suppose, instead, that we make only the weaker assumption that $X[1],X[2],\ldots,X[n]$ contain precisely $m$ distinct values; the values are otherwise random, subject to this constraint. What is the probability distribution of $A$ in this case? Verified: yes Solve time: 4m19s Exercise 1.2.10.7 (Corrected Solution) We...