brain

**Exercise 4.

Let $D$ be a set of $b$ integers such that for each residue $j$ modulo $b$, there exists exactly one element $a \in D$ with a \equiv j \pmod{b}, \quad 0 \le j < b.

Let $\beta = i + 1$.

Let $B = i - 1$ denote the base of the number system under consideration.

Let (a_n a_{n-1} \ldots a_1 a_0)_{i-1} = \sum_{j=0}^{n} a_j (i-1)^j be a number in the $(i-1)$-ary system, where each digit satisfies

We correct the missing justification by giving a fully constructive expansion algorithm for the negative decimal system and then completing the standard argument for the quater-imaginary system.

Let the base be $2i$, as in the quater-imaginary system.

We are given an even number of arrays, each array is a permutation of numbers from 1 to some common length $n$. The key operation allowed on any array is a cyclic rotation, where the last element moves to the front.

Let $(a_n \ldots a_1 a_0)_{-2}$ and $(b_n \ldots b_1 b_0)_{-2}$ be given, where each digit $a_i, b_i \in {0,1}$.

Let the negadecimal base be $\beta = -10$ and digits be $0,1,\dots,9$.

A signed magnitude binary number $\pm(a_n \ldots a_1 a_0)_2$ represents an integer $N$ obtained by first forming the binary value A = \sum_{i=0}^{n} a_i 2^i and then setting $N = A$ if the sign is $+$...

To convert an octal number to hexadecimal, we first expand each octal digit into a 3-bit binary block, concatenate all the blocks, and then regroup the resulting binary string into 4-bit blocks to obt...

Let a number be represented in _mixed-radix_ notation, that is, by a sequence of digits $(d_0, d_1, \ldots, d_{n-1})$ associated with radices $(b_0, b_1, \ldots, b_{n-1})$, where each $d_i$ satisfies...

Let $F(x)$ be a distribution function as defined in Section 4.

For integers represented in $n$ digits in base $10$, ten’s complement is defined modulo $10^n$.

Let $p$ denote the total number of bits.

We are asked to determine the position of the radix point in registers A and X after executing two sequences of MIX instructions, given that the operands in memory locations A and B have the radix poi...

Let $x$ be a nonnegative integer written with $n$ decimal digits.

**Exercise 4.

In signed magnitude representation, one digit records the sign and the remaining digits represent the magnitude in ordinary binary.

The correct approach is to treat `ran_array` as a black-box generator that produces a fresh block of $1009$ random integers each time it is called, while internally maintaining its own state.

We are asked to represent each integer in the range from $-10$ to $10$ using the numeral system with radix $-2$.

Let X_n=(X_{n-37}+X_{n-100})\bmod 2 and define

The runtime error `ValueError: min() arg is empty` comes from trying to compute `min(arr)` when `arr` is empty.

The machine performs integer arithmetic only in the range $[-32768,.,.,32767]$, which corresponds to a word size of $2^{16}$.

The failure in the previous solution is that it reconstructs a plausible subtractive generator, but it does not faithfully translate the _actual control structure of the C `run_start`_, in particular...

The previous solution failed because it replaced the actual structure of **run_array** with an unmotivated generic LFSR model.

Let $S = 2^{-30} = 1/m$, where $m = 2^{30} = \text{MM}$.

The original proposal correctly identified a sensible three-layer testing strategy, but it relied on an incorrect and oversimplified description of LCG period behavior.

Let X_{n+1} \equiv aX_n + c \pmod{2^{35}}, \qquad 0 \le X_n < 2^{35}, and the observed data be

This exercise is intentionally open-ended.

The exercise requires a concrete implementation that plays **two games**, uses a **specific random number generator**, shuffles a deck of cards, and prints all results in the indicated form.

A proper response to this exercise is necessarily organizational and empirical rather than purely mathematical, since it concerns existing implementations in a real subroutine library.

We simulate the game commonly known as _craps_.

Lady Lovelace's statement is correct in the limited sense that a machine executes rules supplied by its designer.

The runtime error in the previous testing framework occurs because the `solve()` function is defined in the global scope, but the `run()` helper function tries to call it inside a new `io.

Method (1) of Section 3.

We are given a set of boxes, each containing some number of candies.

Let $X_1, \ldots, X_n$ be random variables with \mu = \mathrm{E}X_j, \qquad \sigma^2 = \mathrm{E}X_j^2 - (\mathrm{E}X_j)^2 \quad (1 \le j \le n), and assume that for $i \ne j$,

\textbf{Let }p_j=P(A,H_j)\qquad(0\le j\le N), where $H_j$ is the hybrid source whose first $j$ bits come from $S$ and whose remaining $N-j$ bits are independent unbiased bits.

We restart from the actual content of the exercise: this is a counting problem in algorithmic (Kolmogorov) randomness, not a string manipulation task.

We are asked to simulate a dynamic seating scenario.

Let $(X_n)$ be a binary sequence that is random according to Definition R6.

Let $(X_n)$ be a binary sequence that is random according to Definition R6.

The original argument fails because it treats sparsity as if it were automatically invisible to selection rules, and it treats adaptive selection as probabilistic.

Let ${U_n}$ be an infinite sequence, and let ${r_n}$ and ${s_n}$ be strictly increasing sequences of integers with no common elements, so that the subsequences ${U_{r_n}}$ and ${U_{s_n}}$ are disjoint...

Exercise 31 shows that Definition R5 does not imply Definition R1.

We are asked to construct arrays called beautiful arrays.

Let $\langle X_n \rangle$ be a $b$-ary sequence that is random according to Definition R5.

Let $X_0, X_1, X_2, \ldots$ be a $(2k)$-distributed binary sequence.

The failure of the previous solution comes from trying to _infer 3-distribution from digitwise uniformity of a single sequence_.

The proposed solution does address the actual exercise and identifies the key idea: each pair $(U_{2n-1},U_{2n})$ is transformed by either keeping it unchanged or swapping coordinates, depending on wh...

Let $B_n$ be the indicator of the event $V_n \ge \tfrac12$.

Let $(U_n)$ be a $[0,1)$ sequence.

Let $(U_n)$ be a $\{0,1\}$-valued sequence that is equidistributed in $[0,1)$.

Part (a) asks for a characterization of equidistribution in terms of the difference sequences $V_n^{(k)}=(U_{n+k}-U_n)\bmod 1,\qquad k>0.$ The statement to be proved is that $(U_n)$ is equidistributed...

Let $Y_n = (U_n, U_{n+1}, \ldots, U_{n+k-1}) \in [0,1)^k.$ By Definition B in Section 3.

Let $U_0, U_1, \ldots$ be an infinite sequence of real numbers in $[0,1)$.

Let l_n^{(1)} \ge l_n^{(2)} \ge \cdots \ge l_n^{(n)} denote the lengths of the $n$ subintervals determined by the first $n$ points

**Solution to Exercise 3.

Let V_n=\frac{\lfloor nU_n\rfloor}{n}.

Let U_n = r^n \bmod 1, \qquad n \ge 0, where $r$ is a rational number.

Let $\langle U_n \rangle$ be an $\infty$-distributed sequence.

Let Y_i=X_{f(n-1)+i}\qquad (i\ge 1).

Let $(U_n)$ be a $k$-distributed sequence.

Let $A_n=\{\alpha \le U_n < \beta\},\qquad p=\beta-\alpha.$ Since $(U_n)$ is $\infty$-distributed, it is $k$-distributed for every positive integer $k$.

**Solution to Exercise 3.

The proof of Theorem C uses the hypothesis \(m \mid q\) at the point where one must show that the residue classes \[ 0,\; m,\; 2m,\; \ldots,\; \left(\frac{q}{m}-1\right)m \] are distinct modulo \(q\).

Lemma E states that if \lim_{n\to\infty}\frac1n\sum_{j=1}^n y_{jn}=a, \qquad \lim_{n\to\infty}\frac1n\sum_{j=1}^n y_{jn}^2=a^2,

The answer is **No**.

I carefully analyzed why the previous code produced the wrong output on the first sample (`1010` with `k=0`).

I analyzed the original solution carefully and identified the root cause of the wrong output.

We are given a binary string of length $n$ and we want to minimize a sum computed from all consecutive pairs of digits.

Let A(n) = S(n) \land T(n), \qquad B(n) = S(n) \lor T(n), and, for $N \ge 1$, let

Let the ternary sequence be periodic with period $P$.

Let ${q_1, \ldots, q_N}$ be defined by $q_k = U_k / w_k$, where $U_1, \ldots, U_N$ are independent uniform $(0,1)$ random variables, and let $r$ be the $n$th smallest element of ${q_1, \ldots, q_N}$.

No.

Let a file of $N$ items be given, with positive weights $w_1, \ldots, w_N$.

**Corrected Solution for Exercise 3.

The rejection method in the proposed solution does not satisfy the required expected $O(n)$ time bound when $n$ is comparable to $N$.

The key fact is the following characterization.

We are asked to simulate **the effect of Algorithm P truncated at $j = t-n$**, using only $O(n)$ memory.

**Exercise 3.

Let $N$ be the total number of records in the input file.

The proposed solution answers the exercise that was actually asked.

We apply **Algorithm R** with reservoir size $n=3$ to a file containing 20 records numbered $1$ through $20$.

Algorithm R uses the reservoir only because the final sample must ultimately be written in the same order as the corresponding records appeared in the input file.

Let $T$ be the value of $t$ when Algorithm S terminates.

Let $S$ be any fixed subset of $n$ records chosen from the $N$ available records.

Let $X$ denote the number of input records skipped before the first selection in Algorithm S.

We are asked to determine if an array of integers is 3SUM-closed, which means that for every triple of distinct elements in the array, the sum of those three elements is itself present somewhere in th...

Let $p(m,t)$ denote the probability that exactly $m$ items are selected from among the first $t$ in Algorithm S, where $0 \le t \le N$.

Let $T$ denote the value of $t$ when Algorithm S terminates.

Algorithm S proceeds by examining the input file sequentially, maintaining two counters: $t$, the number of records remaining in the input file, and $n$, the number of additional records still to be s...

We are asked to **explain Eq.

Let $N(0,1)$ denote the normal distribution with mean $0$ and variance $1$.

Algorithms P, M, F, and R generate a normal deviate by reading a sequence of independent uniform random variables U_1,U_2,U_3,\ldots, stopping after a random number of them has been examined.

**Problem.

Let $\mu > 0$ be a given constant.

We seek $n$ random variables $X_1, \ldots, X_n$ satisfying $0 \le X_1 \le \cdots \le X_n \le 1$, such that the joint distribution is uniform over all nondecreasing sequences in $[0,1]^n$.