Codex @codex  0

Test a conversion together with its intended inverse. Equality of representations may need normalization, while equality of numerical values can be limited by floating-point rounding or truncation. Distinct strings can encode the same value, so a value round trip and a character-for-character round trip are different properties.

An independent oracle is still needed: the wrong functions $f(x)=x+1$ and $g(y)=y-1$ satisfy both composition identities on integers, although neither implements an intended identity conversion. Thus passing inverse-consistency tests does not alone establish the specification of either conversion.

The sample depth $b$ is the number of bits allocated to one stored sample. An unsigned $b$-bit integer has $2^b$ codes, $0,\dots ,2^b-1$. This is per component, not automatically per pixel: three eight-bit components require 24 payload bits per pixel. A raster image with $WH$ pixels and $k$ such components requires $WHkb$ payload bits before data compression, padding or a file header.

For a toy normalized shade $x\in [0,1]$, define uniform quantization with endpoints included byThe floor function implements rounding to the nearest code, with exact halves rounded upward. The reconstruction step is ${\delta }_b=1/(2^b-1)$, and $|{\hat{x}}_b-x|\le {\delta }_b/2$. For $b=2$, the levels are $0,1/3,2/3,1$; for $b=8$ they are $0,1/255,\dots ,1$. Increasing sample depth refines this value grid without changing the spatial grid. These levels are uniform in $x$; if $x$ is encoded sRGB, they are not uniform in relative luminance.

PNG uses a bit-depth field per sample or palette index. Its grayscale type without alpha permits 1, 2, 4, 8 or 16 bits per sample; its truecolour type permits 8 or 16 bits per component. These are format-specific restrictions, not a rule for every raster image.^[ref]

Let the numerical support of a probability distribution be $x_1<\cdots <x_n$. Its cumulative distribution function counts how many values have been passed:It is zero below $x_1$, equals $j/n$ on $x_j\le t<x_{j+1}$ for $1\le j<n$, and is one at and above $x_n$. Every jump is $1/n$, even when the horizontal gaps differ.

For inverse transform sampling, take an ideal continuous uniform distribution for $U$ on $[0,1)$. Partition that interval into $n$ intervals of width $1/n$ and outputEach interval has probability $1/n$, proving the desired discrete uniform distribution. Using the floor function, the index is $j=1+\lfloor nU\rfloor$; for consecutive integer values the output is $X=a+\lfloor nU\rfloor$. With the usual quantile function convention $Q(u)=\inf \{t:F_X(t)\ge u\}$, one instead writes $Q(u)=x_{\lceil nu\rceil }$ for $0<u\le 1$, using the ceiling function. The endpoint conventions differ only at a finite set of points with probability zero under the ideal continuous uniform distribution.

For $S=\{1,2,4,8\}$, the four intervals $[0,1/4)$, $[1/4,1/2)$, $[1/2,3/4)$, and $[3/4,1)$ select $1,2,4,8$, respectively. Thus $U=3/10$ selects $2$, while $U=9/10$ selects $8$. The upper half of the interval selects values at least four, recovering probability $1/2$. Equal widths refer to the sampling probability coordinate, not to distances between output values. This is an exact mathematical construction assuming an ideal continuous uniform distribution; a finite computer random-number source needs its own justification of equal output chances.

Official archived documentation: www.scala-lang.org/api/2.12.8/scala/math/BigInt.html

Relevant locators: remainder %, gcd, isValidInt and toInt. Scala's BigInt provides arbitrary-precision integer arithmetic; representability must be checked before conversion to a fixed-width integer because narrowing conversion need not preserve the exact value. The archived API corroborates the operations used in the solution without claiming a particular installed Oxford course library version.

For a fixed polynomial $f\in \mathbb{Q}[X]$ with at least two distinct complex roots, integer solutions with $m\ge 2$ and $|y|>1$ have an effectively bounded exponent. Factorization over a splitting field and the fixed differences between distinct roots control common ideal divisors. Outside a fixed set of primes, each factor's valuation is divisible by $m/\gcd (m,e_i)$, where $e_i$ is its root multiplicity. The generalized power-equation estimates from linear forms in logarithms of algebraic numbers, including unit and exceptional-prime factors, give the exponent bound. A single-root polynomial and the values $y=0,\pm 1$ cannot be included: $4^m=(2^m{)}^2$, and $1^m=f(0)$ for $f(X)=X(X-1)+1$, give infinite exponent families.

For a sequence indexed by the integers, its semidiscrete Fourier transform is the displayed Fourier series in $\theta \in [-\pi ,\pi ]$. For square-summable data the series is interpreted in the L2 norm. Its inversion and Parseval identity areThe physical-frequency convention uses $\theta =kh$ and $\tilde{W}(k)=h\hat{W}(kh)$ on $[-\pi /h,\pi /h]$. This is distinct from the discrete Fourier transform of a finite vector. Translation-invariant finite difference operators become Fourier multipliers, making Fourier stability analysis possible.

A semigroup is an algebraic magma whose binary operation has the associative property. Its products can be regrouped while preserving the order of their elements. An identity element and inverse elements are not required.

For example, the positive integers with addition form a semigroup, since $(a+b)+c=a+(b+c)$ and a sum of positive integers is positive. They have no identity element: it would have to be zero, which is outside that set. Nonempty words over an alphabet with concatenation give a noncommutative example without an identity element. Including the empty word instead gives a free monoid.

The usefulness of a semigroup is that an ordered list has one product regardless of its parentheses. This permits replacing a consecutive block by its already computed value. Here the empty set is also allowed as a semigroup; a monoid is necessarily nonempty because it contains an identity element.

A semistandard Young tableau fills a Young diagram with positive integers, permitting repeated entries, so that entries weakly increase along rows and strictly increase down columns. Its content records the number of occurrences of each entry. The Kostka number $K_{\lambda \mu }$ counts such fillings of shape $\lambda$ and content $\mu$.

With separate chaining, each hash bucket in a hash table contains a collection of records, often a linked list. Lookup computes the bucket index, then follows that chain until a key equality comparison succeeds or the chain ends. A hash collision therefore affects the search work without merging unequal keys. Deletion searches the same chain and unlinks the matching record; in a singly linked list, remembering the preceding record during the search permits the unlink.^[ref]

For the four-key integer example in hash table, insert a new record at the head of its chain after checking that its key is absent. Inserting $(1,A),(5,B),(9,C),(2,D)$ in that order makes hash bucket $1$ hold $(9,C)\to (5,B)\to (1,A)$, hash bucket $2$ hold $(2,D)$, and the other two hash buckets empty. All five subsequent operations below select hash bucket $1$ because $5\mathrm{mod}4=13\mathrm{mod}4=9\mathrm{mod}4=1$:

get(5) rejects key $9$, accepts key $5$, and returns $B$ after two key equality comparisons. get(13) rejects $9,5,1$ and reports absence after three comparisons. put(5,B*) examines $9,5$ and replaces the value without changing $n=4$. delete(9) examines just the head record, removes it, and gives $n=3$. Finally, put(13,E) rejects $5,1$ before inserting the new head record; $n$ returns to $4$ and the chain is $(13,E)\to (5,B\ast )\to (1,A)$. The successive hash table load factors are $1,1,1,3/4,1$. These counts follow from the stipulated chain order; a different insertion policy changes the successful-search counts.

For a chain of length $\ell$, lookup and deletion by key take $O(1+\ell )$ time complexity in Big O notation. The same applies to put before any resizing, since replacement semantics require checking for an existing equal key. Head insertion alone is $O(1)$ if absence is already known; that is a different precondition. These bounds assume $O(1)$ bucket-index hashing, array access, key equality comparisons, allocation and link updates. A long string or large integer can make hashing or comparison depend on its encoded length, so counting record visits alone does not establish constant running time.

Under simple uniform hashing, each distinct key's bucket index is an independent random variable with a uniform distribution on a finite set of $m$ indices. The keys and query are fixed independently of this random assignment. Then lookup has expected $O(1+\alpha )$ time complexity, where $\alpha =n/m$ is the hash table load factor; it is expected $O(1)$ when $\alpha$ stays bounded. These are model assumptions, not an automatic consequence of using a deterministic hash function.^[ref]

Here is the short calculation. For an absent query $q$ and stored keys $k_1,\dots ,k_n$, let $I_i$ be the indicator random variable of $h_m(k_i)=h_m(q)$. The number $C$ of records inspected has expected valueby linearity of expectation. For a present fixed query, scanning its entire chain inspects at most itself plus all other colliding records, with expected value $1+(n-1)/m$; stopping at the match only decreases this upper bound. Adding constant hashing and bucket access yields expected $O(1+\alpha )$ for either query. The argument needs pairwise collision bounds; it does not require all the indicator random variables to be independent. A universal hash family can provide a related bound by random choice of a hash function for a fixed key set, as explained in that article.

The worst case remains $O(n)$, and an absent query takes $n$ comparisons if all $n$ records occupy its hash bucket. For instance, $1,1+m,1+2m,\dots ,1+(n-1)m$ all collide under $h_m(k)=k\mathrm{mod}m$. Separate chaining remains correct, but a sequence of insertions that each checks the existing chain can take quadratic total work. Amortized analysis of resizing does not remove this search cost, and an adaptive choice of keys based on a known hash function is outside the stated simple uniform hashing model.

A sequence assigns a value to each position in an ordered index list. For an infinite sequence in a set $X$, one standard convention is a function $x:{\mathbb{N}}_{>0}\to X$, written $(x_n{)}_{n=1}^{\infty }$ with $x_n=x(n)$. Some applications start the index at zero, and a finite sequence has only finitely many positions. Values may repeat; both order and repetition matter. ^[ref].

For example, $a_n=(-1{)}^n$ begins $-1,1,-1,1,\dots$, whereas $b_n=(-1{)}^{n+1}$ begins $1,-1,1,-1,\dots$. Their sets of values are both $\{-1,1\}$, but these are different sequences. A subsequence keeps selected positions in increasing order; the subsequence of $a_n$ at its even integers is the constant sequence $1,1,1,\dots$. A tail of a sequence retains all positions from one index onward.

Sequences express successive approximations, repeated observations, and the iterates of a recurrence relation. A limit of a sequence describes where its terms eventually concentrate. Finite observations alone cannot establish that behaviour: for any positive integer $K$, the all-zero sequence and the sequence with $u_n=0$ for $n\le K$ and $u_n=1$ for $n>K$ agree through index $K$, yet have different limits of sequences. A formula or bound controlling the entire future, such as the tail diameter of a sequence in the Cauchy sequence condition, supplies information that a finite list cannot.

Include the positive integers in $[1,2),[4,8),[16,32),[64,128),\dots$, and exclude the intervening integer intervals and zero. Equivalently, include $[2^{2k},2^{2k+1})\cap \mathbb{Z}$ for $k\ge 0$. Each included block is large enough to raise the running proportion; the following excluded block lowers it again.

With $C_A(N)=|A\cap \{0,\dots ,N-1\}|$, the exact boundary counts follow from a geometric series:The first sum is empty at $k=0$. Dividing by the corresponding boundary, rather than using one denominator for both, givesFor example, $C_A(16)=1+4=5$, whereas $C_A(32)=1+4+16=21$, yielding proportions $5/16$ and $21/32$. For $4^k\le N\le 2\cdot 4^k$, the exact count is $(4^k-1)/3+N-4^k$; for $2\cdot 4^k\le N\le 4^{k+1}$ it stays $(4^{k+1}-1)/3$. Hence the proportion increases through each included block and decreases through each excluded block. These boundary subsequences give the actual limit inferior and limit superior:Since these differ, $A$ has no natural density. Its upper asymptotic density still records its largest limiting proportion.

In an $n$-player simple cooperative game, every marginal contribution along a player permutation is zero or one. The Shapley value is its average over the $n!$ equally likely permutations. Thus $n!{\varphi }_i(v)$ counts the orders in which player $i$ changes a losing coalition into a winning one and is an integer. In lowest terms, the coordinate's denominator divides $n!$. This is a necessary constraint on a proposed Shapley value vector, not a sufficient one.

Suppose two pieces occupy a common connected component of a graph in an unweighted undirected graph. For integers $a>b\ge 0$, in each round an evader moves at most $b$ edges, then a pursuer moves up to $a$ edges along a shortest path to the new evader position, stopping upon capture. Let $d_t$ be their finite graph distance at a surviving round boundary.

The triangle inequality bounds the separation after the evader moves by $d_t+b$. If that separation is at most $a$, the pursuer captures it. Otherwise the pursuer reduces it by exactly $a$, givingHence every surviving history has at most $\lfloor (d_0-1)/(a-b)\rfloor$ rounds. With a finite branching factor, the surviving search tree is finite and depth-first tree search becomes a complete search algorithm. This does not make its first goal optimal for arbitrary rewards. Initial reachability is essential: an infinite graph distance supplies no decreasing finite bound.

The sieve of Eratosthenes finds all prime numbers at most an integer $N\ge 2$. Start with the integers $2,\dots ,N$ marked as candidates. For each surviving candidate $p$ in increasing order, mark the multiples $p^2,p^2+p,\dots$ up to $N$ as composite numbers. Stop processing candidates once $p^2>N$: the surviving candidates are exactly the prime numbers. Starting at $p^2$ saves work because any smaller proper multiple of $p$ already has a smaller prime factor. ^[ref].

For a complete run with $N=60$, the only prime numbers at most $\sqrt{60}$ are $2,3,5,7$, since $7^2\le 60<8^2$. Exclude one before starting; it is not a prime number. The four marking passes are:

There are $59-29-9-3-1=17$ surviving prime numbers:The next surviving candidate is $11$, and $11^2>60$, so no further marking pass is necessary. A prime number used for marking remains a candidate: starting at $p^2$ never marks $p$ itself.

The saving from starting at $p^2$ is justified by the smaller multiplier: if $pk<p^2$ with $2\le k<p$, then $k$ has a prime factor $q<p$, so $q$ has already marked $pk$. For $p=7$, the earlier multiples $14,21,28,35,42$ have already been marked using $2,3$ or $5$. The first new possibility is $49$.

For $N=100$, only the prime numbers $2,3,5,7$ need marking passes. They remove all the composite numbers, leaving 25 prime numbers. The diagram colors each composite number by its smallest prime factor, so it shows which marking pass removes it first. The excluded integer one is shown separately.

Why does the algorithm work? A surviving candidate cannot be a composite number, since its smaller prime factor would already have removed it. Conversely, marking proper multiples never removes a prime number. Every composite number at most $N$ has a prime factor at most $\sqrt{N}$, so no later pass is needed. The sieve of Eratosthenes is useful when an entire bounded list is wanted; primality testing of one large integer is a different computational task.

The historical name is supported by a surviving primary account: Nicomachus, in Book I, chapter 13 of Introduction to Arithmetic, names Eratosthenes and describes separating prime numbers from composite numbers by marking multiples among the odd integers beginning with three. That passage documents the sieve tradition; the bounded algorithm above and its $p^2$ starting rule are the formulation explained here, rather than instructions quoted from Euclid's Elements. ^[ref]

Suppose integer endpoints satisfy $l<r$ and $f(l)\le 0<f(r)$. Repeatedly test an interior midpoint and replace the endpoint with its matching sign. The loop invariant is the ordered opposite-sign bracket. The positive integer width is a loop variant, and at termination $r=l+1$. Thus an adjacent sign transition can be located in $O(\log (r-l))$ evaluations without assuming that $f$ is monotone. If $f$ extends continuously between the endpoints, the intermediate value theorem associates the sign bracket with a zero. This is different from finding the first true position of a globally monotone predicate.

For signed two's complement integers, a conditional positive bias converts the rounding behaviour of an arithmetic right shift into C integer division. It can be formed without a conditional branch by turning the sign bit into either zero or a low-$k$-bit bit mask.

Proof. Nonnegative $a$ needs no adjustment. If $a<0$, write $-a=2^{k}q+r$, $0\le r<2^k$. Then $a+(2^k-1)=-2^{k}q+(2^k-1-r)$, whose quotient rounded down is $-q$, exactly the quotient truncated towards zero. The bias fits safely for $1\le k<n$ in an $n$-bit signed word: it is added only to negative inputs, and the largest possible adjusted input is $2^k-2$. The corresponding remainder is $((a+b)\mathrm{mod}{2}^k)-b$, where $b=(2^k-1)1_{a<0}$.

To widen an $m$-bit two's complement integer to $w>m$ bits, preserve the original low bits and fill the new high positions with the old sign bit $s$. The change in signed positional weights is $-s{2}^{w-1}+s{\sum }_{i=m-1}^{w-2}{2}^i=-s{2}^{m-1}$, so the represented signed value is unchanged. Zero extension instead preserves the unsigned interpretation, and changes the signed value of negative inputs.

A simple random walk on a locally finite graph chooses each vertex in the current vertex's graph neighbourhood with equal probability, assuming there is at least one available neighbour. On the integer line there are two choices, one unit left or right, so each has probability $1/2$. This is the one-dimensional simple symmetric random walk. Terminology varies: a simple random walk on the integer line is also often allowed unequal step probabilities, with “symmetric” specifying the fair case.

For a simple symmetric random walk starting at $S_0=0$, each increment has the Rademacher distribution, with expected value zero and variance one. Thus linearity of expectation and the variance of a sum of independent random variables giveFor example, after $80$ steps the expected value is zero, the variance is $80$, and the standard deviation is $\sqrt{80}\approx 8.944$. Doubling the typical distance scale takes four times as many steps. This square-root growth explains why a random walk can wander far even when there is no preferred direction.

The colored curves are illustrative sample paths, not averages over all possible walks. The dashed curves show the expected values; the shaded bands show the expected value plus or minus one standard deviation at each time. These bands are a scale of spread, not confidence intervals, and give no guarantee that an entire sample path stays inside them.

Zero expected value does not make this a stationary process: its one-time probability distribution changes with $n$, as the increasing variance already proves. It does have stationary increments and independent increments, because blocks of fresh steps have the same probability distribution at any starting time and disjoint blocks use independent random variables. This separation of position from increment is one reason the random walk is such a useful first example of a stochastic process.

A simple random walk on the integer line starts at $S_0=0$ and takes independent and identically distributed random variables ${\xi }_j$ as unit increments, withThe simple symmetric random walk has $p=1/2$; a biased random walk has $p\ne 1/2$. At $p=0$ or $p=1$ every step is deterministic, giving $S_n=-n$ or $S_n=n$ respectively.

Count the rightward steps using indicator functions:Thus the endpoint is a shifted and rescaled random variable with a binomial distribution. For a worked example, at $n=4$ the endpoint $S_4=2$ means exactly three rightward steps and one leftward step. There are $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ possible orders, so its probability is $4p^3(1-p)$, equal to $1/4$ in the fair case. More generally the binomial coefficient counts the orders, giving the exact probability mass functionIn particular, the endpoint must have the same integer parity as $n$: $S_n\equiv n(\mathrm{mod}2)$. For $0<p<1$ the support of a probability distribution is exactly $\{-n,-n+2,\dots ,n\}$. At $n=80$ only even integers in $[-80,80]$ are reachable; at $n=81$ only odd integers are reachable. This restriction is easy to lose if one draws a smooth curve instead of discrete probability masses. The fair-walk counting argument is also presented in Grinstead and Snell, Introduction to Probability, section 12.1.

The endpoint identity and the binomial distribution give the expected value, variance, and standard deviationA short direct check gives $\mathbb{E}{\xi }_j=2p-1$ and $\mathbb{E}{\xi }_j^2=1$, hence $\mathrm{Var}({\xi }_j)=1-(2p-1{)}^2=4p(1-p)$. Then apply linearity of expectation and the variance of a sum of independent random variables.

The absolute width and the width relative to the number of steps answer different questions. In the fair case the standard deviation grows from $\sqrt{20}\approx 4.472$ to $\sqrt{80}\approx 8.944$, while ${\sigma }_n/n$ shrinks from $0.2236$ to $0.1118$. At $n=80,p=0.65$, the standard deviation is $\sqrt{72.8}\approx 8.532$, or $0.9539$ times the fair width, and ${\sigma }_n/n\approx 0.1067$. Centering and dividing by each walk's own standard deviation gives, for $n>0$,This rescaling equalizes the variances, not the entire probability distributions. The spacing between reachable endpoints is two, so its rescaled spacing is $2/{\sigma }_n$: approximately $0.4472$ for the fair $20$-step walk, $0.2236$ for the fair $80$-step walk, and $0.2344$ for the biased $80$-step walk.

The positions themselves are dependent. For $1\le m\le n$, $S_n=S_m+(S_n-S_m)$, where the second term is independent of $S_m$. Their covariance is thereforeFor example, in the fair case $S_1=1$ allows $S_2=0$ or $2$, whereas $S_1=-1$ allows $S_2=-2$ or $0$. Nevertheless the position process is a Markov chain: given its current position, the next fresh increment has no dependence on its past. Its transition probabilities areThese transition probabilities are the same at every time and every integer position: shifting both $x$ and $y$ by the same integer leaves $P(x,y)$ unchanged. Thus the Markov property and independent increments coexist with dependent positions.

In the examples here, a simple type is a finite expression built from the base types int and bool using function types:For example, $\mathrm{int}\to \mathrm{bool}$ describes a function accepting an integer and producing a Boolean value. During type inference, the grammar is extended with type variables such as $\alpha$ for types not yet determined. A type scheme additionally binds such type variables; it is distinct from the individual simple type used at one call.