#math-research
TAOCP 3.3.4 Exercise 31
Section 3.3.4: The Spectral Test Exercise 31. [ M48 ] (I. Borosh and H. Niederreiter.) Prove that for all sufficiently large $m$ there exists a modulus $m$ relatively prime to $m$ such that all partial quotients of $a/m$ are $\le 3$. Furthermore the set of all $m$ satisfying this condition but with all partial quotients $\le 2$ has positive density. Verified: yes Solve time: 4m56s Exercise 3.3.4.31 [M48] Let $$...
TAOCP 3.3.4 Exercise 22
Section 3.3.4: The Spectral Test Exercise 22. [ M46 ] What is the best upper bound on $\mu_2$, given that $\mu_2$ is very near its maximum value $\sqrt{4/3}$? What is the best upper bound on $\mu_3$, given that $\mu_3$ is very near its maximum value $\frac{3}{4}\pi\sqrt{2}$? Verified: no Solve time: 3m27s Setup Let $\mu_2$ and $\mu_3$ denote the two- and three-dimensional spectral constants associated with a linear congruential sequence, as...
TAOCP 2.2.3 Exercise 13
Section 2.2.3: Linked Allocation Exercise 13. [ M48 ] How many ways are there to arrange the $2^n$ subsets described in exercise 12 into topological order? (Give the answer as a function of $n$.) Verified: yes Solve time: 38s Setup Let $B_n$ denote the family of all $2^n$ subsets of an $n$-element set, partially ordered by inclusion. A topological order of $B_n$ is a linear ordering of all subsets such...
TAOCP 2.2.1 Exercise 13
Section 2.2.1: Stacks, Queues, and Deques Exercise 13. [ M48 ] How many permutations of $n$ elements are obtainable with the use of a general deque? [See Rosenstiehl and Tarjan, J. Algorithms 5 (1984), 389-390, for an algorithm that decides in $O(n)$ steps whether or not a given permutation is obtainable.] Verified: no Solve time: - Setup Let $d_n$ denote the number of permutations of ${1,2,\ldots,n}$ that can be obtained...