#math-simple
TAOCP 7.2.2.2 Exercise 516
Section 7.2.2.2: Satisfiability Exercise 516. [ M9 ] [M9] Prove or disprove the strong exponential time hypothesis : "If $\tau < 2$, there is an integer $k$ such that no randomized algorithm can solve every $k$SAT problem in fewer than $\tau^n$ steps, where $n$ is the number of variables." Verified: no Solve time: 3m45s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible...
TAOCP 7.2.2.2 Exercise 446
Section 7.2.2.2: Satisfiability Exercise 446. [ M10 ] What's the maximum number of edges in a subgraph of $K_{m,n}$ that has girth $\ge 6$? (Express your answer in terms of $m$ and $n$.) Verified: no Solve time: 3m48s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write $$ x_{i,j}=1\iff x_i=j, $$ where $0\le i<p$ and $1\le j\le d$ if the domain...
TAOCP 7.2.2.2 Exercise 276
Section 7.2.2.2: Satisfiability Exercise 276. [ M15 ] True or false: If $F$ is a family of clauses and $L$ is a set of strictly distinct literals, then $F \wedge L \vdash_1 \epsilon$ if and only if $(F|L) \vdash_1 \epsilon$. Verified: no Solve time: 3m44s Solution The statement is true. Let $L={l_1,\ldots,l_r}$ be a set of strictly distinct literals. The restriction $F|L$ is obtained by setting every literal in $L$...
TAOCP 7.2.2.1 Exercise 44
Section 7.2.2.1: Dancing Links Exercise 44. [ M04 ] [M04] Could the clues of a sudoku puzzle be the first 33 digits of $\pi$? (See (29a).) Verified: yes Solve time: 3m22s The first $33$ digits of $\pi$ are $$ 3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5,0. $$ A sudoku clue must be a digit from $1$ through $9$, because each cell value represents one of the nine possible symbols. The $33$rd digit in this sequence is...
TAOCP 7.2.2.1 Exercise 203
Section 7.2.2.1: Dancing Links Exercise 203. [ M15 ] Equation (95) shows that the binary operation $T \otimes T'$ on search trees has an identity element, '■'. Is that operation (a) associative? (b) commutative? Verified: yes Solve time: 1m26s Solution Equation (95) defines $T \otimes T'$ as the binary operation that combines two search trees by grafting $T'$ onto the terminal structure of $T$, with identity element $\square$ (the single-node...
TAOCP 7.2.2.1 Exercise 129
Section 7.2.2.1: Dancing Links Exercise 129. ▶ [ M14 ] The most beautiful patterns that can be made with MacMahon's triangles are those with attractive symmetries, which can be of two kinds: strong symmetry (a rotation or reflection that doesn't change the pattern, except for permutation of colors) or weak symmetry (a rotation or reflection that preserves the "color patches," the set of boundaries between different colors). Exactly how many...
TAOCP 7.2.2.1 Exercise 127
Section 7.2.2.1: Dancing Links Exercise 127. [ M8 ] There are $4^{12}$ ways to prescribe the border colors of a hexagon like those in (59). Which of them can be completed to a color-matched placement of all 24 triangles? Verified: no Solve time: 4m16s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly...
TAOCP 7.2.2 Exercise 50
Section 7.2.2: Backtracking Exercise 50. [ M15 ] $[M15]$ Interpret the value $E(D_1, \ldots, D_n)$ in the text's Monte Carlo algorithm. Verified: no Solve time: 5m15s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$. Let $k$ be the number...
TAOCP 7.2.1.6 Exercise 43
Section 7.2.1.6: Generating All Trees Exercise 43. [ M11 ] Express $C_{pq}$ in terms of the Catalan numbers $C_0, C_1, C_2, \ldots$, aiming for a formula that is simple when $q - p$ is small. (For example, $C_{(p-1)q} = C_q - C_{q-1}$.) Verified: no Solve time: 5m36s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots...
TAOCP 7.2.2 Exercise 19
Section 7.2.2: Backtracking Exercise 19. [ M10 ] [M10] What are the domains $D_l$ in Langford's problem (7)? Verified: no Solve time: 4m56s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$. Let $k$ be the number of terms among...
TAOCP 7.2.1.5 Exercise 26
Section 7.2.1.5: Generating All Set Partitions Exercise 26. [ M2 ] [M2] According to the recurrence equations (13), the numbers $\varpi_{nk}$ in Peirce's triangle count the paths from $\binom{0}{0}$ to $\binom{n}{k}$ in the infinite directed graph Explain why each path from $\binom{0}{0}$ to $\binom{n}{k}$ corresponds to a partition of ${1, \ldots, n}$. Verified: no Solve time: 5m43s Setup We seek all integers $n < 10^9$ such that the equation $x_1...
TAOCP 7.2.1.5 Exercise 22
Section 7.2.1.5: Generating All Set Partitions Exercise 22. [ M2 ] [M2] If $X$ is a random variable with a given distribution, the expected value of $X^n$ is called the $n$th moment of that distribution. What is the $n$th moment when $X$ is (a) a Poisson deviate with mean 1 [Eq. 3.4.1–(40)]? (b) the number of fixed points of a random permutation of ${1, \ldots, m}$, when $m \ge n$...
TAOCP 7.2.1.5 Exercise 18
Section 7.2.1.5: Generating All Set Partitions Exercise 18. [ M6 ] For which $n$ is it possible to generate all restricted growth strings $a_1 \ldots a_n$ in such a way that some $a_j$ changes by $\pm 1$ at each step? Verified: no Solve time: 5m49s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has...
TAOCP 7.2.1.4 Exercise 32
Section 7.2.1.4: Generating All Partitions Exercise 32. [ M15 ] [M15] Prove that n m ≤p(n −m) for all m, n ≥0. When does equality hold? Verified: no Solve time: 5m41s Setup Let $p(m)$ denote the number of partitions of $m$ in the sense of Section 7.2.1.4, and let $(c_1,\dots,c_n)$ be the part-count representation of a partition of $n$ as in (8). The algorithm of Exercise 47 maintains a parameter...
TAOCP 7.2.1.3 Exercise 68
Section 7.2.1.3: Generating All Combinations Exercise 68. [ M01 ] [M01] If α is a t-combination, what is (a) ∂tα? (b) ∂t+1α? Verified: no Solve time: 10m34s Let $\alpha$ be a $t$-combination, so $\alpha$ is a $t$-element subset of ${0,1,\dots,n-1}$. The operator $\partial_t \alpha$ produces all $(t-1)$-combinations obtained by deleting one element of $\alpha$. If $\alpha={c_t,\dots,c_1}$, then $$ \partial_t \alpha={\alpha\setminus{c_j}\mid 1\le j\le t}. $$ Each element of $\partial_t \alpha$ is...
TAOCP 7.2.1.2 Exercise 50
Section 7.2.1.2: Generating All Permutations Exercise 50. [ M15 ] [M15] Explain why the dual formula (32) follows from (13). Verified: yes Solve time: 2m44s We restart the argument from the actual structure of (13), tracking how each update clause transforms under the duality map, and we verify case by case that the transformed rules are exactly those of (32). Let (13) describe the reflected mixed-radix Gray traversal of inversion...
TAOCP 7.2.1.2 Exercise 22
Section 7.2.1.2: Generating All Permutations Exercise 22. [ M15 ] [M15] True or false: If an alphametic has a solution in radix b, it has a solution in radix b + 1. Verified: no Solve time: 4m34s The previous solution fails because it tries to separate bases via carry behavior, but an alphametic solution is not defined in terms of carries. It is defined purely as a digit assignment satisfying...
TAOCP 7.1.4 Exercise 13
Section 7.1.4: Binary Decision Diagrams Exercise 13. [ M15 ] [M15] How is the concept of a graph kernel related to the concept of (a) a maximal clique? (b) a minimal vertex cover? Verified: no Solve time: 3m34s Solution Let $G=(V,E)$ be an ordinary (undirected) graph, viewed as a digraph by replacing each edge ${u,v}\in E$ with the two arcs $u\to v$ and $v\to u$. From Exercise 12(a), a kernel...
TAOCP 1.3.3 Exercise 16
Section 1.3.3: Applications to Permutations Exercise 16. [ M15 ] Start with the permutation 1324 in linear notation; convert it to canonical cycle form and then remove the parentheses; repeat this process until arriving at the original permutation. What permutations occur during this process? Verified: yes Solve time: 4m12s Let $T$ be the operation described: Start with a permutation in linear notation. Convert it to canonical cycle form. Remove parentheses...
TAOCP 1.3.3 Exercise 15
Section 1.3.3: Applications to Permutations Exercise 15. [ M12 ] Is there a permutation that represents exactly the same transformation both in the canonical cycle form without parentheses and in the linear form? Verified: yes Solve time: 3m16s Let $\pi$ be a permutation of ${1,2,\dots,n}$. Write the one-line form as $$ (\pi(1)\ \pi(2)\ \cdots\ \pi(n)). $$ Write the canonical cycle form with cycles ordered by increasing smallest element, each cycle...
TAOCP 4.2.4 Exercise 11
Section 4.2.4: Distribution of Floating Point Numbers Exercise 11. [ M15 ] Given that $U$ is a random variable distributed according to the logarithmic law, prove that $1/U$ is also. Verified: no Solve time: 1m01s Solution Let $U>0$ be a random variable whose distribution satisfies the logarithmic law in base $10$. Write $X = \log_{10} U.$ The assumption means that the fractional part ${X} = X \bmod 1$ is uniformly...
TAOCP 5.1.4 Exercise 11
Section 5.1.4: Tableaux and Involutions Exercise 11. [ M08 ] [M08] In how many ways can the partial ordering represented by (39) be sorted topologically? Verified: no Solve time: 46m42s Exercise 5.1.4.11 [M08] Problem: In how many ways can the partial ordering represented by (39) be sorted topologically? Solution: Let the elements of the poset be $a,b,c,d,e,f,g$. The covering relations given by the Hasse diagram are: $$ a < c,...
TAOCP 5.2.1 Exercise 11
Section 5.2.1: Sorting by Insertion Exercise 11. [ M10 ] [M10] What path in a lattice like that of Fig. 11 corresponds to the permutation 12537486911 10 12? Verified: yes Solve time: 2m59s Let $$ \pi = (1,2,5,3,7,4,8,6,9,11,10,12). $$ We use the standard TAOCP boundary construction: the lattice path from $(0,0)$ to $(n,n)$ is determined by $$ x_k = #{, i \le k : \pi(i) \le k ,}, \qquad k=1,\dots,n....
TAOCP 4.7 Exercise 3
Section 4.7: Manipulation of Power Series Exercise 3. [ M15 ] Does formula (9) give the right results when $n = 0$? When $n = 1$? Verified: yes Solve time: 3m16s Formula (9) expresses $W_n$ for $n \ge 1$ in terms of the coefficients $V_k$ and the previously computed $W_{n-k}$, and it contains an explicit factor $1/n$. We examine the boundary cases $n=0$ and $n=1$ directly from this structure. For...
TAOCP 4.7 Exercise 1
Section 4.7: Manipulation of Power Series Exercise 1. [ M10 ] The text explains how to divide $U(z)$ by $V(z)$ when $V_0 \ne 0$; how should the division be done when $V_0 = 0$? Verified: yes Solve time: 1m54s Let $V_m$ be the first nonzero coefficient of $V(z)$; thus $V(z)=z^m\widehat V(z),\qquad \widehat V_0=V_m\ne0.$ If $U(z)=z^r\widehat U(z),\qquad \widehat U_0=U_r\ne0,$ then $\frac{U(z)}{V(z)}=z^{,r-m}\frac{\widehat U(z)}{\widehat V(z)}.$ The quotient is a formal power series if...
TAOCP 4.6.4 Exercise 40
Section 4.6.4: Evaluation of Polynomials Exercise 40. [ M1 ] [M1] Can the lower bound in the number of multiplications in Theorem C be raised from $\lfloor n/2 \rfloor + 1$ to $\lfloor n/2 \rfloor + 17$ (See exercise 33.) Verified: yes Solve time: 3m20s Let $M(n)$ denote the minimum number of multiplications needed to evaluate some polynomial of degree $n$, with arbitrary coefficients, when no preliminary adaptation of the...
TAOCP 4.6.4 Exercise 32
Section 4.6.4: Evaluation of Polynomials Exercise 32. [ M2 ] Find a polynomial chain of minimum possible length that can compute all polynomials of the form $u_1 x^3 + u_2 x^2 + u_0$; and prove that its length is minimal. Verified: no Solve time: 4m46s Let $$ P(x) = u_1 x^3 + u_2 x^2 + u_0, $$ where $u_0, u_1, u_2$ are independent parameters. We seek a polynomial chain of...
TAOCP 4.6.4 Exercise 5
Section 4.6.4: Evaluation of Polynomials Exercise 5. [ M15 ] Count the number of multiplications and additions required by the second-order rule (4). Verified: yes Solve time: 4m01s Solution Let $n$ be given and write $u(x)=u_n x^n+u_{n-1}x^{n-1}+\cdots+u_1x+u_0.$ Define the even and odd parts with respect to $x^2$: $E(x)=\sum_{k\ge 0} u_{2k} x^{2k}, \qquad O(x)=\sum_{k\ge 0} u_{2k+1} x^{2k}.$ Then the second-order representation (4) is $u(x)=E(x)+x,O(x).$ Let $t=x^2$. Both $E(x)$ and $O(x)$ are...
TAOCP 4.6.3 Exercise 15
Section 4.6.3: Evaluation of Powers Exercise 15. [ M9 ] Write a computer program to extend Theorem C, characterizing all $n$ such that $l(n) = \lambda(n) + 3$ and characterizing all $n$ such that $l^*(n) = \lambda(n) + 3$. Verified: no Solve time: 12m58s Let $$ s(n)=l(n)-\lambda(n),\qquad s^ (n)=l^ (n)-\lambda(n), $$ where $\lambda(n)=\lfloor \log_2 n\rfloor$. Theorem C gives a complete characterization of the case $s(n)=2$. Exercise 15 asks for the...
TAOCP 4.6.3 Exercise 12
Section 4.6.3: Evaluation of Powers Exercise 12. [ M10 ] Is it possible to extend the tree shown in Fig. 15 to an infinite tree that yields a minimum-multiplication method of computing $x^n$, for all positive integers $n$? Verified: no Solve time: 5m10s Solution to Exercise 4.6.3.12 $[M10]$ The answer is yes . Let $l(n)$ denote the length of a shortest addition chain for $n$. We ask whether there exists...
TAOCP 4.6.1 Exercise 7
Section 4.6.1: Division of Polynomials Exercise 7. [ M10 ] What are the units in the domain of all polynomials over a unique factorization domain? Verified: no Solve time: 4m28s Let $f(x)$ be a unit in the polynomial ring over a unique factorization domain $S$. Then there exists a polynomial $g(x)$ such that $f(x)g(x)=1$. Since $\deg(fg)=\deg(f)+\deg(g)$ whenever both factors are nonzero, property (i) of a unique factorization domain implies that...
TAOCP 4.5.2 Exercise 37
Section 4.5.2: The Greatest Common Divisor Exercise 37. [ M9 ] [M9] Prove that the subtraction step B6 of Algorithm B is never executed more than $1 + \lfloor \lg \max(u, v) \rfloor$ times. Verified: no Solve time: 6m24s Solution. Let $u$ and $v$ be the values at the beginning of an execution of step B6 of Algorithm B. Without loss of generality, assume $u \ge v \ge 1$. Step...
TAOCP 4.3.3 Exercise 14
Section 4.3.3: How Fast Can We Multiply? Exercise 14. [ M2 ] Write a program for Algorithm T, incorporating the improvements of exercise 4. Compare it with a program for Algorithm 4.3.1M and with a program based on (2), to see how large $n$ must be before Algorithm T is an improvement. Verified: yes Solve time: 5m12s Exercise 4.3.3.14 [M2] Corrected Solution We implement Algorithm T for multiplying two $n$-digit...
TAOCP 4.3.3 Exercise 9
Section 4.3.3: How Fast Can We Multiply? Exercise 9. [ M15 ] Suppose the Fourier transformation method of the text is applied with all occurrences of $\omega$ replaced by $\omega^q$, where $q$ is some fixed integer. Find a simple relation between the numbers $(\hat{u}_0, \hat{u} 1, \ldots, \hat{u} {k-1})$ obtained by this general procedure and the numbers $(\hat{u}_0, \hat{u} 1, \ldots, \hat{u} {k-1})$ obtained when $q = 1$. Verified: yes...
TAOCP 4.3.2 Exercise 12
Section 4.3.2: Modular Arithmetic Exercise 12. [ M10 ] Prove that, if $0 \le u, v < m$, the modular addition of $u$ and $v$ causes overflow (lies outside the range allowed by the modular representation) if and only if the sum is less than $u$. (Thus the overflow detection problem is equivalent to the comparison problem.) Verified: no Solve time: 4m17s The claimed output 10 for "0?10" is actually...
TAOCP 4.1 Exercise 8
Section 4.1: Positional Number Systems Exercise 8. [ M10 ] [M10] Prove Eq. (5). Verified: yes Solve time: 1m24s Let $F(x)$ be a distribution function as defined in Section 4.1. By definition, $F(x) = \Pr{X \le x}$ for some random variable $X$. If $x_1 \le x_2$, then the event ${X \le x_1}$ is contained in the event ${X \le x_2}$, so $\Pr{X \le x_1} \le \Pr{X \le x_2},$ which gives...
TAOCP 3.5 Exercise 11
Section 3.5: What Is a Random Sequence? Exercise 11. [ M10 ] Use Theorem C to prove that if a sequence $(U_n)$ is $\infty$-distributed, so is the subsequence $(U_{2n})$. Verified: yes Solve time: 3m51s Solution to Exercise 3.5.11 [ M10 ] Let $(U_n)$ be an $\infty$-distributed sequence. By Definition C, $(U_n)$ is $k$-distributed for every positive integer $k$. We want to show that the subsequence $(U_{2n})$ is also $\infty$-distributed; that...
TAOCP 3.5 Exercise 8
Section 3.5: What Is a Random Sequence? Exercise 8. [ M15 ] Prove (13). Verified: no Solve time: 7m45s I carefully analyzed why the previous code produced the wrong output on the first sample ( 1010 with k=0 ). The logic for computing the initial sum of d_i = s_i s_{i+1} is incorrectly implemented . The previous code did total += int(s[i])*10 + int(s[i+1]) , which treats each character as...
TAOCP 3.4.2 Exercise 1
Section 3.4.2: Random Sampling and Shuffling Exercise 1. [ M12 ] Explain Eq. (1). Verified: no Solve time: 4m44s Corrected Solution to Exercise 3.4.2.1 [ M12 ] We are asked to explain Eq. (1) in the context of a puzzle represented as an $n \times m$ grid with distinct numbers $1, 2, \dots, nm$, and to reason about the minimum number of swaps needed to make the puzzle solvable along...
TAOCP 3.4.1 Exercise 8
Section 3.4.1: Numerical Distributions Exercise 8. [ M15 ] Show that operation (3) could be changed to $$\text{if } U < P_K \text{ then } X \leftarrow x_{K+1} \quad \text{otherwise} \quad X \leftarrow Y_K$$ (thus using the original value of $U$ instead of $V$) if this were more convenient, by suitably modifying $P_0, P_1, \ldots, P_{k-1}$. Verified: no Solve time: 4m02s Solution The target is to generate a random variable...
TAOCP 3.3.4 Exercise 8
Section 3.3.4: The Spectral Test Exercise 8. [ M8 ] Line 10 of Table 1 has a very low value of $\mu_3$, yet $\mu_5$ is quite satisfactory. What is the highest possible value of $\mu_5$ when $\mu_2 = 10^{-8}$ and $m = 10^{10}$? Verified: yes Solve time: 4m30s Exercise 3.3.4.8 [ M8 ] Problem: Line 10 of Table 1 has a very low value of $\mu_3$, yet $\mu_5$ is quite...
TAOCP 3.3.4 Exercise 1
Section 3.3.4: The Spectral Test Exercise 1. [ M10 ] What does the spectral test reduce in one dimension? (In other words, what happens when $t = 1$?) Verified: yes Solve time: 1m13s When $t = 1$, the spectral test considers the set of points $\left{\frac{1}{m} x ;\Big|; 0 \le x < m\right}$ in one-dimensional space, which is simply the set of equally spaced multiples of $1/m$ between 0 and...
TAOCP 3.3.3 Exercise 1
Section 3.3.3: Theoretical Tests Exercise 1. [ M10 ] Express $x \bmod y$ in terms of the sawtooth and $\delta$ functions. Verified: yes Solve time: 12m11s Exercise 3.3.3.1 [ M10 ] 1. Express $x \bmod y$ in terms of the sawtooth and $\delta$ functions. Solution Let $x \in \mathbb{R}$ and $y \in \mathbb{R} \setminus {0}$. By definition, the modulo operation $x \bmod y$ is the remainder $r$ when $x$ is...
TAOCP 3.3.2 Exercise 15
Section 3.3.2: Empirical Tests Exercise 15. [ M10 ] In the maximum-of-$t$ test, why are $V_0', V_1', \ldots, V_{n-1}'$ supposed to be uniformly distributed between zero and one? Verified: yes Solve time: 2m15s In the maximum-of-$t$ test, the $j$th observation is $$ V_j=\max(U_{tj},U_{tj+1},\ldots,U_{tj+t-1}). $$ For $0\le v\le1$, $$ \Pr(V_j\le v) =\Pr(U_{tj}\le v,\ldots,U_{tj+t-1}\le v). $$ Since the $U$'s are independent and uniformly distributed on $[0,1]$, $$ \Pr(V_j\le v)=v^t. $$ Thus the...
TAOCP 3.3.2 Exercise 14
Section 3.3.2: Empirical Tests Exercise 14. ▶ [ M15 ] If we "throw away" the element that immediately follows a run, so that when $X_i$ is greater than $X_{i+1}$ we start the next run with $X_{i+2}$, the run lengths are independent, and a simple chi-square test may be used (instead of the horribly complicated method derived in the text). What are the appropriate run-length probabilities for this simple run test?...
TAOCP 3.3.2 Exercise 4
Section 3.3.2: Empirical Tests Exercise 4. [ M12 ] Prove that the probabilities in (4) are correct for the gap test. Verified: no Solve time: 6m29s Solution Let $\langle U_n \rangle = U_0, U_1, U_2, \ldots$ be a sequence of independent uniform random variables on $[0,1)$, and let $0 \le \alpha < \beta \le 1$. Define $p = \beta - \alpha$, the probability that a single $U_j$ falls in $[\alpha,...
TAOCP 3.2.1.2 Exercise 14
Section 3.2.1.2: Choice of Multiplier Exercise 14. [ M15 ] [M15] If $e > 1$ and $a$ is a primitive element modulo $p$, prove that either $a$ or $a + p$ is a primitive element modulo $p^e$. [ Hint: See exercise 12.] Verified: yes Solve time: 14m17s Solution Assume $e>1$ and that $a$ is a primitive element modulo $p$. By Exercise 12, for every odd prime $p$, an integer $b$...
TAOCP 3.2.1.1 Exercise 1
Section 3.2.1.1: Choice of Modulus Exercise 1. [ M7 ] $[M7]$ In exercise 3.2.1–3 we concluded that the best congruential generators will have the multiplier $a$ relatively prime to $m$. Show that when $m = w$ in this case it is possible to compute $(aX + c) \bmod w$ in just three MIX instructions, rather than the four in (1), with the result appearing in register X. Verified: no Solve...
TAOCP 3.2.1 Exercise 3
Section 3.2.1: The Linear Congruential Method Exercise 3. [ M10 ] If $a$ and $m$ are not relatively prime, explain why the sequence will be somewhat handicapped and probably not very random; hence we will generally want the multiplier $a$ to be relatively prime to the modulus $m$. Verified: yes Solve time: 18m51s If $a$ and $m$ are not relatively prime, there exists a nontrivial common factor $d > 1$...
TAOCP 7.1.1 Exercise 119
Section 7.1.1: Boolean Basics Exercise 119. [ M8 ] Continuing the previous exercises, let $b(n)$ be the maximum number of prime implicants in a Boolean function of $n$ variables. Clearly $b(n) \le b'(n) < b^*(n)$; what is the asymptotic value of $b(n)$? Verified: no Solve time: 6m46s We determine the correct asymptotic order of $b(n)$, the maximum number of prime implicants of a Boolean function on $n$ variables. A prime...
TAOCP 1.3.3 Exercise 5
Section 1.3.3: Applications to Permutations Exercise 5. [ M10 ] Equation (3) shows several equivalent ways to express the same permutation in cycle form. How many different ways of writing that permutation are possible, if all singleton cycles are suppressed? Verified: no Solve time: 7m27s The permutation (acf)(bd) consists of a $3$-cycle and a $2$-cycle. Any cycle of length $n$ can be written in $n$ ways by choosing the starting...
TAOCP 1.3.1 Exercise 7
Section 1.3.1: Description of MIX Exercise 7. [ M15 ] Give a precise definition of the results of the DIV instruction for all cases in which overflow does not occur, using the algebraic operations X mod Y and \lfloor X/Y \rfloor . Verified: yes Solve time: 1m13s Solution Let the contents of register $rA$ be $A = s_A \cdot a$ and the contents of register $rX$ be $X = s_X...
TAOCP 1.2.9 Exercise 9
Section 1.2.9: Generating Functions Exercise 9. [ M11 ] In the notation of Eqs. (34) and (35), what is $h_4$ in terms of $S_1,S_2,S_3,$ and $S_4$? Verified: yes Solve time: 1m42s Solution Let $S_k$ denote the power-sum quantities and $h_k$ the sequence defined by Eqs. (34) and (35), so that the generating function relation has the form $$ \sum_{n \ge 0} h_n z^n = \exp!\left(\sum_{k \ge 1} \frac{S_k}{k} z^k\right). $$...
TAOCP 1.2.9 Exercise 7
Section 1.2.9: Generating Functions Exercise 7. [ M15 ] Verify all the steps leading to Eq. (38). Verified: no Solve time: 5m20s Let $F_0=0$, $F_1=1$, and $F_{n+1}=F_n+F_{n-1}$. The derivation leading to Eq. (38) establishes the addition formula $$ F_{m+n} = F_m F_{n+1} + F_{m-1} F_n. $$ Each step in the derivation is justified as follows. First fix $m \ge 1$ and prove the identity by induction on $n$. For $n=0$,...
TAOCP 1.2.9 Exercise 4
Section 1.2.9: Generating Functions Exercise 4. [ M01 ] Explain why Eq. (19) is a special case of Eq. (21). Verified: yes Solve time: 3m16s The previous solution failed because it did not use the correct form of Eq. (21) and did not justify the specialization of coefficients. We restart from the correct functional equation and derive the specialization cleanly. Equation (21) in this context states that $x$ is defined...
TAOCP 1.2.9 Exercise 2
Section 1.2.9: Generating Functions Exercise 2. [ M13 ] Prove Eq. (11). Verified: yes Solve time: 1m16s Solution Let $$ A(z)=\sum_{n\ge 0}\frac{a_n}{n!}z^n,\qquad B(z)=\sum_{n\ge 0}\frac{b_n}{n!}z^n. $$ Their product expands as $$ A(z)B(z)=\left(\sum_{k\ge 0}\frac{a_k}{k!}z^k\right)\left(\sum_{j\ge 0}\frac{b_j}{j!}z^j\right) =\sum_{n\ge 0}z^n\sum_{k=0}^{n}\frac{a_k}{k!}\frac{b_{n-k}}{(n-k)!}. $$ The coefficient of $z^n$ in $A(z)B(z)$ equals $$ \sum_{k=0}^{n}\frac{a_k b_{n-k}}{k!(n-k)!}. $$ Define a sequence $\langle c_n\rangle$ by requiring that $$ A(z)B(z)=\sum_{n\ge 0}\frac{c_n}{n!}z^n. $$ Then comparison of coefficients gives $$ \frac{c_n}{n!}=\sum_{k=0}^{n}\frac{a_k b_{n-k}}{k!(n-k)!}. $$ Multiplying both...
TAOCP 1.2.9 Exercise 1
Section 1.2.9: Generating Functions Exercise 1. [ M12 ] What is the generating function for the sequence $2,5,13,35,\ldots = \langle 2^n+3^n \rangle$? Verified: yes Solve time: 58s Solution Let $\langle a_n \rangle = 2^n + 3^n$. The generating function is $$ G(z) = \sum_{n \ge 0} (2^n + 3^n) z^n. $$ Split the sum into two series: $$ G(z) = \sum_{n \ge 0} 2^n z^n + \sum_{n \ge 0} 3^n...
TAOCP 1.2.7 Exercise 12
Section 1.2.7: Harmonic Numbers Exercise 12. [ M10 ] Evaluate $H_{\infty}^{(1000)}$ correct to at least 100 decimal places. Verified: yes Solve time: 2m35s Let $$ H_{\infty}^{(1000)}=\sum_{k=1}^{\infty}\frac{1}{k^{1000}}=1+R,\qquad R=\sum_{k=2}^{\infty}\frac{1}{k^{1000}}. $$ Step 1: A valid bound for the tail The function $f(x)=x^{-1000}$ is positive and strictly decreasing for $x\ge 1$. Hence the standard integral comparison for decreasing functions gives $$ \sum_{k=2}^{\infty} \frac{1}{k^{1000}} \le \frac{1}{2^{1000}} + \int_{2}^{\infty} x^{-1000},dx. $$ We compute the integral: $$...
TAOCP 1.2.7 Exercise 6
Section 1.2.7: Harmonic Numbers Exercise 6. [ M15 ] Prove that the harmonic numbers are directly related to Stirling's numbers, which were introduced in the previous section; in fact, $$ H_n = \left[{n+1 \atop 2}\right] / n!. $$ Verified: yes Solve time: 1m20s Solution Let $\left[{n \atop k}\right]$ denote the Stirling numbers of the first kind, defined by the recurrence $$ \left[{n \atop k}\right] = (n-1)\left[{n-1 \atop k}\right] + \left[{n-1...
TAOCP 1.2.6 Exercise 37
Section 1.2.6: Binomial Coefficients Exercise 37. [ M10 ] From the answers to the preceding exercise, deduce the value of the sum of every other entry in a row, $\binom{n}{0} + \binom{n}{2} + \binom{n}{4} + \cdots$. Verified: yes Solve time: 1m10s Let $$ S=\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots . $$ From Exercise 1.2.6.36, $$ \sum_{k=0}^{n}\binom{n}{k}=2^{n},\qquad \sum_{k=0}^{n}(-1)^k\binom{n}{k}=(1-1)^n=0 \quad (n\ge 1). $$ Split the total sum into even and odd parts, $$ 2^{n}=S+\sum_{\substack{0\le k\le n\ k\...
TAOCP 1.2.6 Exercise 36
Section 1.2.6: Binomial Coefficients Exercise 36. [ M10 ] What is the sum $\sum_k \binom{n}{k}$ of the numbers in each row of Pascal's triangle? What is the sum of these numbers with alternating signs, $\sum_k \binom{n}{k}(-1)^k$? Verified: yes Solve time: 1m12s From the binomial theorem (13) with $x=1$, $y=1$, $$ (1+1)^n=\sum_k \binom{n}{k}1^k1^{n-k}=\sum_k \binom{n}{k}, $$ so $$ \sum_k \binom{n}{k}=2^n. $$ With $x=1$, $y=-1$ in (13), $$ (1-1)^n=\sum_k \binom{n}{k}1^k(-1)^{n-k}=\sum_k \binom{n}{k}(-1)^{n-k}. $$ Multiplying...
TAOCP 1.2.6 Exercise 39
Section 1.2.6: Binomial Coefficients Exercise 39. [ M10 ] What is the sum $\sum_k \left[{n \atop k}\right]$ of the numbers in each row of Stirling's first triangle? What is the sum of these numbers with alternating signs? Verified: yes Solve time: 1m11s The numbers $\left[{n \atop k}\right]$ count permutations of $n$ objects with exactly $k$ cycles. Summing over all possible numbers of cycles therefore counts every permutation exactly once, since...
TAOCP 1.2.6 Exercise 24
Section 1.2.6: Binomial Coefficients Exercise 24. [ M15 ] Explain why the results of the previous two exercises combine to give a proof of Eq. (26). Verified: no Solve time: 3m44s Let $P(r,s,t,n)$ denote the statement of Eq. (26), and fix $r,t,n$. Write $$ P_s := P(r,s,t,n). $$ We are given two results from the previous exercises: Exercise 22 (initial block): There exists an index $s_0$ such that $$ P_{s_0},...
TAOCP 1.2.6 Exercise 23
Section 1.2.6: Binomial Coefficients Exercise 23. [ M13 ] Assuming that Eq. (26) holds for $(r,s,t,n)$ and $(r,s-t,t,n-1)$, prove it for $(r,s+1,t,n)$. Verified: no Solve time: 3m57s Let Eq. (26) be written in its explicit form as an identity between two expressions that depend on $s$ only through binomial coefficients with fixed summation structure. In TAOCP style, this means there exist expressions of the form $$ P(r,s,t,n)=\sum_{j=0}^{n} A_j(r,t,n)\binom{s}{j}+\sum_{j=0}^{n} B_j(r,t,n)\binom{s-t}{j}, $$...
TAOCP 1.2.6 Exercise 21
Section 1.2.6: Binomial Coefficients Exercise 21. [ M05 ] Both sides of Eq. (25) are polynomials in $s$; why isn't that equation an identity in $s$? Verified: yes Solve time: 1m14s Both sides of Eq. (25) are polynomials in $s$, but the derivation of Eq. (25) establishes equality only under the restrictions imposed earlier in the section, namely for integer values of $s$ (and with the additional constraints on the...
TAOCP 1.2.6 Exercise 18
Section 1.2.6: Binomial Coefficients Exercise 18. [ M15 ] Prove Eq. (22) using Eqs. (21) and (6). Verified: no Solve time: 1m09s Solution Equation (21) (Chu–Vandermonde) states $$ \sum_{k}\binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n}, \qquad \text{integer } n. \tag{21} $$ Let $m,n$ be integers. Consider $$ \sum_{k}\binom{r}{m+k}\binom{s}{n-k}. $$ Make the change of index $j=m+k$, so $k=j-m$. Then $$ \binom{r}{m+k}=\binom{r}{j}, \qquad \binom{s}{n-k}=\binom{s}{n-(j-m)}=\binom{s}{m+n-j}. $$ The sum becomes $$ \sum_{j}\binom{r}{j}\binom{s}{m+n-j}. $$ Since $\binom{r}{j}=0$ for $j<0$ and $j>r$ when...
TAOCP 1.2.6 Exercise 15
Section 1.2.6: Binomial Coefficients Exercise 15. [ M15 ] Prove the binomial formula, Eq. (13). Verified: yes Solve time: 1m07s Solution Induction on $r$ is used. For $r=0$, $(x+y)^0 = 1$. From definition (3), $\binom{0}{0}=1$ and $\binom{0}{k}=0$ for $k \ne 0$. Hence $$ \sum_k \binom{0}{k} x^k y^{-k} = \binom{0}{0} x^0 y^0 = 1, $$ so the formula holds for $r=0$. Assume that for a fixed integer $r \ge 0$, $$...
TAOCP 1.2.6 Exercise 16
Section 1.2.6: Binomial Coefficients Exercise 16. [ M15 ] Given that $n$ and $k$ are positive integers, prove the symmetrical identity $$ (-1)^n\binom{-n}{k-1} = (-1)^k\binom{-k}{n-1}. $$ Verified: no Solve time: 3m01s Solution For integers $k \ge 0$, definition (3) gives $$ \binom{-n}{k-1} = \prod_{j=1}^{k-1} \frac{-n+1-j}{j} = \prod_{j=1}^{k-1} \frac{-(n-1+j)}{j}. $$ Each factor contributes a sign $(-1)$, hence $$ \binom{-n}{k-1} = (-1)^{k-1} \prod_{j=1}^{k-1} \frac{n-1+j}{j} = (-1)^{k-1} \binom{n+k-2}{k-1}, $$ since the product matches...
TAOCP 1.2.6 Exercise 13
Section 1.2.6: Binomial Coefficients Exercise 13. [ M13 ] Prove the summation formula, Eq. (10). Verified: yes Solve time: 1m02s Solution Fix a real number $r$ and an integer $n \ge 0$. Define $$ S_n = \sum_{k=0}^{n} \binom{r+k}{k}. $$ We prove by induction on $n$ that $$ S_n = \binom{r+n+1}{n}. $$ For $n=0$, the sum reduces to a single term, $$ S_0 = \binom{r}{0}. $$ By definition (3), $\binom{r}{0} =...
TAOCP 1.2.4 Exercise 27
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 27. [ M15 ] Given that $n$ is a positive integer, let $\varphi(n)$ be the number of values among ${0,1,\ldots,n-1}$ that are relatively prime to $n$. Thus $\varphi(1)=1$, $\varphi(2)=1$, $\varphi(3)=2$, $\varphi(4)=2$, etc. Show that $\varphi(p)=p-1$ if $p$ is a prime number; and evaluate $\varphi(p^e)$, when $e$ is a positive integer. Verified: yes Solve time: 2m37s We restart from the definition. Let...
TAOCP 1.2.4 Exercise 26
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 26. [ M15 ] Let $p$ be an odd prime number, let $a$ be any integer, and let $b = a^{(p-1)/2}$. Show that $b \bmod p$ is either 0 or 1 or $p-1$. [Hint: Consider $(b+1)(b-1)$.] Verified: yes Solve time: 1m03s Solution Let $p$ be an odd prime and let $a$ be an integer. Define $b = a^{(p-1)/2}$. If $a \bmod...
TAOCP 1.2.4 Exercise 25
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 25. [ M02 ] Show that, according to Theorem F, $a^{p-1} \bmod p = [a \text{ is not a multiple of } p]$ whenever $p$ is a prime number. Verified: yes Solve time: 57s Let $p$ be prime. If $p \mid a$, then $a \bmod p = 0$, hence $a^{p-1} \bmod p = 0$ since $a^{p-1}$ is also a multiple of...
TAOCP 1.2.4 Exercise 22
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 22. ▶ [ M10 ] Give an example to show that Law B is not always true if $a$ is not relatively prime to $m$. Verified: yes Solve time: 59s Let $m=4$, $a=2$, $b=2$, $x=0$, $y=2$. Then $a \equiv b \pmod 4$ holds since $2-2=0$ is a multiple of $4$. Compute $ax=2\cdot 0=0$ and $by=2\cdot 2=4$, so $ax \equiv by \pmod...
TAOCP 1.2.4 Exercise 23
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 23. [ M10 ] Give an example to show that Law D is not always true if $r$ is not relatively prime to $s$. Verified: yes Solve time: 1m07s Take $r=s=2$, so $rs=4$, and $a=2$, $b=0$. Then $a-b=2$, hence $2 \mid (a-b)$, so $a \equiv b \pmod 2$ and also $a \equiv b \pmod 2$ for the second modulus. Thus both...
TAOCP 1.2.4 Exercise 19
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 19. ▶ [ M10 ] ( Law of inverses. ) If $n \perp m$, there is an integer $n'$ such that $nn' \equiv 1$ (modulo $m$). Prove this, using the extension of Euclid’s algorithm (Algorithm 1.2.1E). Verified: yes Solve time: 1m01s Since $n \perp m$, the greatest common divisor of $n$ and $m$ is $1$. By the extension of Euclid’s algorithm...
TAOCP 1.2.4 Exercise 18
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 18. [ M15 ] Using Law B, prove the other half of Law D: If $a \equiv b$ (modulo $r$) and $a \equiv b$ (modulo $s$), then $a \equiv b$ (modulo $rs$), provided that $r \perp s$. Verified: yes Solve time: 1m07s Solution Let $r \perp s$ and assume $a \equiv b \pmod r$ and $a \equiv b \pmod s$. By...
TAOCP 1.2.4 Exercise 20
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 20. [ M15 ] Use the law of inverses and Law A to prove Law B. Verified: yes Solve time: 2m26s Since $a \perp m$, the law of inverses yields an integer $a'$ such that $$ aa' \equiv 1 \pmod m. $$ From the hypothesis $a \equiv b \pmod m$, apply Law A (multiplication) with $a'$ to obtain $$ aa' \equiv...
TAOCP 1.2.4 Exercise 17
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 17. [ M15 ] Prove Law A directly from the definition of congruence, and also prove half of Law D: If $a \equiv b$ (modulo $rs$), then $a \equiv b$ (modulo $r$) and $a \equiv b$ (modulo $s$). (Here $r$ and $s$ are arbitrary integers.) Verified: yes Solve time: 1m Solution Let $m$ be a fixed integer. Assume $a \equiv b...
TAOCP 1.2.4 Exercise 16
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 16. [ M10 ] Assume that $y>0$. Show that if $(x-z)/y$ is an integer and if $0 \le z < y$, then $z = x \bmod y$. Verified: yes Solve time: 1m13s Let $k = (x - z)/y$, where $k \in \mathbb{Z}$. Then $x = ky + z$. From $0 \le z < y$, dividing by $y>0$ yields $0 \le z/y...
TAOCP 1.2.4 Exercise 7
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 7. [ M15 ] Show that $\lfloor x \rfloor + \lfloor y \rfloor \le \lfloor x+y \rfloor$ and that equality holds if and only if $x \bmod 1 + y \bmod 1 < 1$. Does a similar formula hold for ceilings? Verified: yes Solve time: 2m54s Write $x = \lfloor x \rfloor + a$, $y = \lfloor y \rfloor + b$,...
TAOCP 1.2.4 Exercise 4
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 4. ▶ [ M10 ] Using the previous exercise, prove that $\lfloor -x \rfloor = -\lceil x \rceil$. Verified: yes Solve time: 1m06s Let $n = \lfloor -x \rfloor$. Then by Exercise 3(e), $n \le -x < n+1.$ Multiplying all parts by $-1$ reverses the inequalities, giving $-n \ge x > -n-1,$ hence $-n-1 < x \le -n.$ By Exercise 3(f),...
TAOCP 1.2.4 Exercise 3
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 3. [ M10 ] Let $n$ be an integer, and let $x$ be a real number. Prove that a) $\lfloor x \rfloor < n$ if and only if $x < n$; b) $n \le \lfloor x \rfloor$ if and only if $n \le x$; c) $\lfloor x \rfloor \le n$ if and only if $x < n+1$; d) $n < \lceil...
TAOCP 1.2.11.2 Exercise 13
Section 1.2.11.2: Euler's Summation Formula Exercise 13. [ M10 ] Prove or disprove: $g(n)=\Omega(f(n))$ if and only if $f(n)=O(g(n))$. 1.2.11.2. Euler's summation formula. One of the most useful ways to obtain good approximations to a sum is an approach due to Leonhard Euler. His method approximates a finite sum by an integral, and gives us a means to get better and better approximations in many cases. Figure 12 shows a...
TAOCP 1.2.11.2 Exercise 11
Section 1.2.11.2: Euler's Summation Formula Exercise 11. [ M11 ] Explain why Eq. (18) is true. Verified: yes Solve time: 1m34s Solution From the definition of the exponential function, $$ e^x = \sum_{k\ge 0}\frac{x^k}{k!} = 1 + x + \frac{x^2}{2!} + \cdots . $$ For $x \to 0$, separate the first two terms and bound the remainder: $$ e^x - 1 - x = \sum_{k\ge 2}\frac{x^k}{k!}. $$ Factor $x^2$ from...
TAOCP 1.2.10 Exercise 11
Section 1.2.10: Analysis of an Algorithm Exercise 11. [ M15 ] What happens to the semi-invariants of a distribution if we change $G(z)$ to $F(z)=z^nG(z)$? Verified: yes Solve time: 1m46s Solution Let $G(z)=\sum_k p_k z^k$ be the probability generating function of a distribution for a random variable $A$. The transformation $$ F(z)=z^n G(z) $$ defines a new generating function $$ F(z)=\sum_k p_k z^{k+n}. $$ Hence the new distribution assigns probability...
TAOCP 1.2.10 Exercise 4
Section 1.2.10: Analysis of an Algorithm Exercise 4. [ M10 ] Give an explicit, closed formula for the values of $p_{nk}$ in the coin-tossing experiment, Eq. (17). Verified: yes Solve time: 1m21s Let $X_1,\ldots,X_n$ be independent trials with $\Pr(X_i=\text{head})=p$ and $\Pr(X_i=\text{tail})=q=1-p$. For any fixed sequence containing exactly $k$ heads and $n-k$ tails, the probability of that sequence is $p^k q^{n-k}$, since the factors multiply over independent trials. The number of...
TAOCP 1.2.10 Exercise 5
Section 1.2.10: Analysis of an Algorithm Exercise 5. [ M13 ] What are the mean and standard deviation of the distribution in Fig. 11? Verified: yes Solve time: 1m13s Solution The distribution in Fig. 11 corresponds to $n=12$ independent trials, each producing success with probability $p=\frac{3}{5}$ and failure with probability $q=\frac{2}{5}$. By Eq. (18), the generating function is $$ G_{12}(z) = (q+pz)^{12}. $$ From Eq. (12), $$ \operatorname{mean}(G_{12}) = G_{12}'(1),...
TAOCP 1.2.10 Exercise 3
Section 1.2.10: Analysis of an Algorithm Exercise 3. [ M15 ] What are the minimum, maximum, average, and standard deviation of the number of times step M4 is executed, if we are using Algorithm M to find the maximum of 1000 randomly ordered, distinct items? (Give your answer as decimal approximations to these quantities.) Verified: yes Solve time: 1m15s Solution For Algorithm M, the number of times step M4 is...