TAOCP 3.2.1.2: Choice of Multiplier
Section 3.2.1.2 exercises: 14 solved.
Section 3.2.1.2. Choice of Multiplier
Exercises from TAOCP Volume 2 Section 3.2.1.2: 14 solved.
| # | Rating | Category | Status | Time |
|---|
TAOCP 3.2.1.2 Exercise 1
The modulus $m = 10^{10}$ factors as $2^{10} \cdot 5^{10}$.
TAOCP 3.2.1.2 Exercise 2
Let $m = 2^e$, where $e \ge 1$.
TAOCP 3.2.1.2 Exercise 3
Let $m = 10^e$ with $e \ge 2$, and let $c$ be odd and not a multiple of 5.
TAOCP 3.2.1.2 Exercise 4
We are given a linear congruential sequence $X_{n+1} = (a X_n + c) \bmod 2^e$ with $X_0 = 0$, and where $a$ and $c$ satisfy the conditions of Theorem A.
TAOCP 3.2.1.2 Exercise 5
We are asked to find all multipliers $a$ that satisfy the conditions of Theorem A when $m = 2^{35} + 1$.
TAOCP 3.2.1.2 Exercise 6
From Table 3.
TAOCP 3.2.1.2 Exercise 7
Let X_{n+1}\equiv aX_n+c \pmod m,\qquad m=\prod_{j=1}^t p_j^{e_j}, and let $X_n^{(j)}$ denote the corresponding sequence modulo $p_j^{e_j}$.
TAOCP 3.2.1.2 Exercise 8
**Exercise 3.
TAOCP 3.2.1.2 Exercise 9
Assume $m = 2^e \ge 16$ and $c = 0$.
TAOCP 3.2.1.2 Exercise 10
From (9), $\lambda(m)=\varphi(m)$ holds for odd prime powers $p^e$, since $\lambda(p^e)=p^{e-1}(p-1)=\varphi(p^e), \qquad p>2.$ For powers of $2$, $\lambda(2)=1=\varphi(2),\qquad \lambda(4)=2=\varphi(...
TAOCP 3.2.1.2 Exercise 11
**Exercise 3.
TAOCP 3.2.1.2 Exercise 12
**Solution.