TAOCP 3.3.3: Theoretical Tests
Section 3.3.3 exercises: 28/28 solved.
Section 3.3.3. Theoretical Tests
Exercises from TAOCP Volume 1 Section 3.3.3: 28/28 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M10] | math-simple | verified | 12m11s |
| 2 | [HM22] | hm-medium | solved | 5m01s |
| 3 | [M23] | math-medium | solved | 9m16s |
| 4 | ▶ [M19] | math-medium | verified | 2m01s |
| 5 | [M21] | math-medium | solved | 2m14s |
| 6 | [M17] | math-medium | solved | 3m15s |
| 7 | ▶ [M34] | math-hard | verified | 1m13s |
| 8 | ▶ [M34] | math-hard | verified | 4m30s |
| 9 | [M40] | math-project | solved | 4m02s |
| 10 | [M20] | math-medium | verified | 15m12s |
| 11 | [M30] | math-hard | solved | 23m23s |
| 12 | [M24] | math-medium | verified | 10m14s |
| 13 | [M24] | math-medium | verified | 14m46s |
| 14 | ▶ [M20] | math-medium | verified | 1m24s |
| 15 | [M22] | math-medium | solved | 9m42s |
| 16 | [M24] | math-medium | solved | 4m34s |
| 17 | [M22] | math-medium | solved | 16m30s |
| 18 | ▶ [M23] | math-medium | solved | 6m23s |
| 19 | ▶ [M29] | math-hard | verified | 4m55s |
| 20 | [M29] | math-hard | solved | 4m59s |
| 21 | ▶ [HM23] | hm-medium | verified | 4m33s |
| 22 | [M22] | math-medium | solved | 1m23s |
| 23 | [M28] | math-hard | verified | 5m20s |
| 24 | [M20] | math-medium | solved | 11m26s |
| 25 | [M25] | math-medium | solved | 15m51s |
| 26 | [M91] | math-research | solved | 4m46s |
| 27 | [M32] | math-hard | verified | 19m07s |
| 28 | [M35] | math-hard | solved | 7m46s |
TAOCP 3.3.3 Exercise 1
**Exercise 3.
TAOCP 3.3.3 Exercise 2
The function $((x))$ is $1$-periodic and defined on $0 \le x < 1$ by $((x)) = x - \frac12,$ since $\lfloor x \rfloor = 0$ and $\lceil x \rceil = 1$ for $0 < x < 1$ in (7).
TAOCP 3.3.3 Exercise 3
Hmm.
TAOCP 3.3.3 Exercise 4
The problem asks for the maximum possible value of $d$ in the notation of Theorem P, given that $m = 10^{10}$ and the potency of the generator is 10.
TAOCP 3.3.3 Exercise 5
From Eq.
TAOCP 3.3.3 Exercise 6
Let $h h' + k k' = 1$.
TAOCP 3.3.3 Exercise 7
Let $h,k$ be positive integers with $\gcd(h,k)=1$.
TAOCP 3.3.3 Exercise 8
Let D(a,b;c)=\sum_{j=0}^{c-1} \left(\!
TAOCP 3.3.3 Exercise 9
Hmm.
TAOCP 3.3.3 Exercise 10
Let $\sigma(h,k,c)$ be the sawtooth sum used in the TAOCP context, where the key structure is a sum over a complete residue system modulo $k$ of a shifted sawtooth expression of the form \sigma(h,k,c)...
TAOCP 3.3.3 Exercise 11
Let (x)=x-\lfloor x\rfloor-\tfrac12 be the centered sawtooth function and
TAOCP 3.3.3 Exercise 12
The issue is not with the core idea of sweeping and using endpoint extrema per color.
TAOCP 3.3.3 Exercise 13
Equation (28) in Section 3.
TAOCP 3.3.3 Exercise 14
We are asked to determine the serial correlation coefficient $C$ of the linear congruential generator $X_{n+1} = (a X_n + c) \bmod m$ with parameters $m = 2^{35}, \quad a = 2^{17} + 1, \quad c = 1,$ o...
TAOCP 3.3.3 Exercise 15
We are asked to generalize Lemma B to all real values of $c$, $0\le c<k$.
TAOCP 3.3.3 Exercise 16
We are asked to prove the identity \sum_{j=1}^{t} (-1)^{j+1} \frac{c_j^2}{m_j m_{j+1}} = \frac{1}{m_1} \sum_{j=1}^{t} (-1)^{j+1} b_j (c_j + c_{j+1}) p_{j-1}, where the sequences $(m_j)$ and $(p_j)$ co...
TAOCP 3.3.3 Exercise 17
The previous solution does not solve the exercise that was asked.
TAOCP 3.3.3 Exercise 18
Let S(h,k,c,z)=\sum_{0\le j<z}\left(\!
TAOCP 3.3.3 Exercise 19
Let X_{n+1}\equiv aX_n+c \pmod m, and assume that the generator has full period $m$.
TAOCP 3.3.3 Exercise 20
Let $X_n$ be a linear congruential sequence X_{n+1} \equiv a X_n + c \pmod m, \quad 0 \le X_n < m, and define the iterates
TAOCP 3.3.3 Exercise 21
C=\frac{\displaystyle \int_0^1 x\,\{ax+\theta\}\,dx-\left(\int_0^1x\,dx\right)^2} {\displaystyle \int_0^1x^2\,dx-\left(\int_0^1x\,dx\right)^2}, \qquad 0\le \theta<1, where $a$ is a positive integer an...
TAOCP 3.3.3 Exercise 22
Let $s(x)=\{ax+\theta\}, \qquad 0\le \theta<1,$ where $a$ is an integer and $x$ is uniformly distributed on $[0,1)$.
TAOCP 3.3.3 Exercise 23
The flawed solution fails at a structural point: it tries to import permutation symmetry of the joint vector $(U_n,U_{n+1},U_{n+2})$, which does not exist for a deterministic dynamical system.
TAOCP 3.3.3 Exercise 24
Let $s(x)=\{ax\}, \qquad a\in \mathbb Z,\ a\ge 1,$ and let $U_{n+1}=s(U_n)=\{aU_n\},$ with $U_n$ uniformly distributed on $[0,1)$.
TAOCP 3.3.3 Exercise 25
We are asked to compute the probability that a uniformly distributed real number $x \in [0,1)$ satisfies both $\alpha \le x < \beta$ and $\alpha' \le s(x) < \beta'$, under the assumptions of Exercise...
TAOCP 3.3.3 Exercise 26
We are asked to consider the Fibonacci generator U_{n+1} = \{ U_n + U_{n-1} \}, \quad n \ge 2, with $U_1, U_2$ independently uniform on $[0,1)$, and to compute the probabilities of the six possible st...