#hm-research
TAOCP 5.3.4 Exercise 50
Section 5.3.4: Networks for Sorting Exercise 50. [ HM46 ] Explore the properties of the $\wedge$ and $\vee$ operations defined in exercise 48. Is it possible to characterize all of the identities in this algebra in some nice way, or to derive them all from a finite set of identities? In this regard, identities such as $x \wedge x \wedge x = x \wedge x$, or $x \wedge (x \vee...
TAOCP 5.1.4 Exercise 21
Section 5.1.4: Tableaux and Involutions Exercise 21. [ HM91 ] (R. M. Thrall.) Let $n_1 > n_2 > \cdots > n_m$ specify the shape of a "shifted tableau" where row $i+1$ starts one position to the right of row $i$; for example, a shifted tableau of shape $(7, 5, 4, 1)$ has the form of the diagram $$ \begin{array}{|c|c|c|c|c|c|c|} \hline \cdot & 9 & 6 & 5 & 3 &...
TAOCP 7.2.2.2 Exercise 283
Section 7.2.2.2: Satisfiability Exercise 283. [ HM46 ] Algorithm C solves the flower snark problem in linear time? More precisely, let $p_k(M)$ be the probability that the algorithm refutes $\text{fnmark}(q)$ while making at most $M$ flushes, as $q \to \infty$. Is $p_k(N_0) \to 1$ or $p_k(N_0) > \frac{1}{2}$ for all $q$? Verified: no Solve time: 3m54s Solution The statement is true. Let $L={l_1,\ldots,l_r}$ be a set of strictly distinct literals....
TAOCP 7.2.2.2 Exercise 203
Section 7.2.2.2: Satisfiability Exercise 203. [ HM93 ] (K. Xu and W. Li, 2000.) Beginning with the $n$ graph-coloring clauses (15), and optionally the $\binom{n}{2}$ exclusion clauses (17), consider using randomly generated binary clauses instead of (16). There are $mq$ random binary clauses, obtained as $m$ independent sets of $q$ clauses each, where every such set is selected by choosing distinct vertices $u$ and $v$, then choosing $q$ distinct literals...
TAOCP 7.2.2.2 Exercise 193
Section 7.2.2.2: Satisfiability Exercise 193. [ HM48 ] [HM48] Determine the satisfiability threshold (81) of random 3SAT. Is it true that $\lim_{n\to\infty} S_{3,n}/n = \limsup_{n\to\infty} S_{3,n}/n$? If so, is the limit $\approx 4.2667$? Verified: no Solve time: 1m54s Solution A Boolean function on variables $x_1,\ldots,x_4$ is represented by a $3$CNF formula exactly when its set of falsifying assignments is a union of subcubes of dimension at least $1$ in the...
TAOCP 7.2.2.1 Exercise 190
Section 7.2.2.1: Dancing Links Exercise 190. [ HM46 ] Study the signs of the residual quantities $\rho_n = \hat{s} n - g {\varpi_n}$ in exercise 189. Verified: no Solve time: 3m56s 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$....
TAOCP 7.2.2.1 Exercise 136
Section 7.2.2.1: Dancing Links Exercise 136. ▶ [ HM48 ] (J. H. Conway, 1958.) There are twelve ways to label the edges of a pentagon with ${0, 1, 2, 3, 4}$, if we don't consider rotations and reflections to be different: Cover a dodecahedron with these tiles, matching edge numbers. (Reflections are OK.) Verified: no Solve time: 4m56s Setup We seek all integers $n < 10^9$ such that the equation...
TAOCP 7.2.1.6 Exercise 76
Section 7.2.1.6: Generating All Trees Exercise 76. [ HM46 ] [HM46] Study the limiting shape of the Christmas tree patterns as $n \to \infty$. Does it, for example, have a fractal dimension under some appropriate scaling? Verified: no Solve time: 5m34s 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...
TAOCP 7.2.1.5 Exercise 77
Section 7.2.1.5: Generating All Set Partitions Exercise 77. [ HM46 ] Find the asymptotic value of $p(n, \ldots, n)$ when there are $n$ $n$s. Verified: no Solve time: 5m47s 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$...
TAOCP 7.2.1.3 Exercise 83
Section 7.2.1.3: Generating All Combinations Exercise 83. [ HM46 ] [HM46] Determine the set R of all rational numbers r such that the equation τ(x) = r has uncountably many solutions. If τ(x) is rational and x is irrational, is it true that τ(x) ∈R? (Warning: This problem can be addictive.) Verified: no Solve time: 4m38s 1. Structure of Takagi level sets Let $\tau:[0,1]\to\mathbb{R}$ be the Takagi function. A standard...
TAOCP 7.2.1.1 Exercise 48
Section 7.2.1.1: Generating All n-Tuples Exercise 48. [ HM48 ] [HM48] Determine the asymptotic behavior of d(n)1/2n as n →∞. Verified: no Solve time: 4m21s Setup Let the 8 variables be indexed by $G={0,1}^3$, written $i=(i_1,i_2,i_3)$ with binary addition $i\oplus j$. Let $(a_i) {i\in G}$ and $(A_i) {i\in G}$ be real numbers. Let $H_3=(h_{ij})_{i,j\in G}$ be the Walsh matrix of order $8$, defined by $$ h_{ij}=(-1)^{i\cdot j}, \qquad i\cdot j=i_1j_1+i_2j_2+i_3j_3...
TAOCP 5.4.9 Exercise 31
Section 5.4.9: Disks and Drums Exercise 31. [ HM48 ] [HM48] Analyze randomized striping to determine its true average behavior, not merely an upper bound, as a function of P, Q, and D. (Even the case Q = 0, which needs an average of O(L/VD) read cycles, is interesting.) Verified: no Solve time: 4m42s The previous solution fails because it never reconstructs the actual performance quantity in TAOCP’s striping model...
TAOCP 5.4.9 Exercise 9
Section 5.4.9: Disks and Drums Exercise 9. [ HM89 ] [HM89] (L. Hyafil, F. Prusker, J. Vuillemin.) Prove that, for fixed a and 6, am+B Ai(n) = (nin min oem ) mogn + O(n) as n, > oo, where the O(n) term is > 0. Verified: no Solve time: 2m17s Let $T$ be a full binary tree with $n$ leaves, and let $D(T)$ and $E(T)$ be the two weighted path...
TAOCP 4.5.3 Exercise 22
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 22. [ HM46 ] (K. L. Babenko.) Develop efficient means to calculate accurate approximations to the quantities $\lambda_1$ and $\Psi_2(x)$ in (44), for small $y \ge 3$ and for $0 \le x \le 1$. Verified: yes Solve time: 7m09s Solution We are asked to develop efficient methods for approximating the quantities $\lambda_1$ and $\Psi_2(x)$ in equation (44) of [ HM46 ], for small...
TAOCP 4.5.2 Exercise 34
Section 4.5.2: The Greatest Common Divisor Exercise 34. [ HM49 ] [HM49] Find a rigorous proof that Brent's model describes the asymptotic behavior of Algorithm B. Verified: yes Solve time: 3m16s Setup Exercise 4.5.2.34 asks for a rigorous proof that Brent's model gives the asymptotic behavior of Algorithm B. Let $T(n)$ denote the expected cost of Algorithm B when the input integers are chosen uniformly from the set of positive...
TAOCP 4.5.2 Exercise 31
Section 4.5.2: The Greatest Common Divisor Exercise 31. [ HM46 ] [HM46] Prove or disprove Vallée's conjecture (61). Verified: no Solve time: 16m31s Exercise 4.5.2.31 [HM46] : Prove or disprove Vallée's conjecture (61). Corrected Solution To address this exercise, the first step is to state Vallée's conjecture (61) precisely . Conjecture (61) in TAOCP §4.5.2 is: $$ \psi_n = \frac{(-1)^{n+1} B_{2n}}{2n(2n-1)} $$ where $\psi_n$ are the coefficients appearing in the...
TAOCP 4.5.2 Exercise 29
Section 4.5.2: The Greatest Common Divisor Exercise 29. ▶ [ HM46 ] [HM46] [R. P. Brent.] Find $G_1(x)$, the distribution of $\min(u, v)/\max(u, v)$ after the first subtract-and-shift cycle of Algorithm B as defined in (35). Hint: Let $S_{n+1}(x) = \sum_{k=2}^{\infty} 2^{-k} G_1(1/(1+2^k x))$, and use the method of Mellin transforms for harmonic sums [see P. Flajolet, X. Gourdon, and P. Dumas, Theor. Comp. Sci. 144 (1995), 3–58]. Verified: yes...
TAOCP 3.5 Exercise 17
Section 3.5: What Is a Random Sequence? Exercise 17. [ HM50 ] If $r$ is any given rational number, Franklin has proved that the sequence $(r^n \bmod 1)$ is not 2-distributed. But is there any rational number $r$ for which this sequence is equidistributed? In particular, is the sequence equidistributed when $r = \frac{3}{2}$? [See K. Mahler, Mathematika 4 (1957), 122–124.] Verified: yes Solve time: 8m54s Corrected Solution Let $$...
TAOCP 3.3.1 Exercise 22
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 22. [ HM46 ] [HM46] Investigate the "improved" KS test suggested in the answer to exercise 6. Verified: yes Solve time: 12m21s Exercise 3.3.1.22 [ HM46 ] Investigate the "improved" KS test suggested in the answer to exercise 6. Setup Let $X_1, X_2, \ldots, X_n$ be independent observations from a continuous distribution function $F(x)$, and let $F_n(x)$ denote the empirical...
TAOCP 7.1.3 Exercise 117
Section 7.1.3: Bitwise Tricks and Techniques Exercise 117. [ HM46 ] [HM46] Continuing exercise 116, is there any simple way to characterize the reg- ular languages L that arise in shift-free 2-adic chains? (The language L = 0∗(10∗10∗)∗ does not seem to correspond to any such chain.) Verified: no Solve time: 3m42s The previous solution fails mainly because it invents a false periodicity property for general $2$-adic constants and then...
TAOCP 1.2.4 Exercise 40
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 40. [ HM46 ] Study the class of replicative functions; determine all replicative functions of a special type. For example, is the function in (a) of exercise 39 the only continuous replicative function? It may be interesting to study also the more general class of functions for which $$ f(x)+f\left(x+\frac1n\right)+\cdots+f\left(x+\frac{n-1}{n}\right)=a_n f(nx)+b_n. $$ Here $a_n$ and $b_n$ are numbers that depend on...