Use arbitrary-precision integers for positions, avoiding overflow on infinite sequences:
type Seq a = a -> [Integer]

rep :: Eq a => [a] -> Seq a
rep xs v = [i | (i,x) <- zip [0..] xs, x == v]
The type synonym Seq a needs no equality constraint; the equality test is required specifically by rep. The list comprehension visits input positions in increasing order, so the output is an increasing list of precisely the matching positions. For finite inputs this includes a terminating empty list when the value is absent. Infinite inputs require the additional productivity distinctions discussed below. This is an occurrence-position representation of a sequence.
For the given sorted array, the complete lower-bound search behavior is for , for , for , and for . In particular, index is never the correct answer because the two equal entries share the same first insertion position.
These unit tests cover every value boundary, equality case and missing-value interval:
  • Below all entries, including the smallest machine integer: ternarySearch(a, Int.MinValue) == 0 and ternarySearch(a, 0) == 0.
  • Equality with the first entry: ternarySearch(a, 1) == 0.
  • Values in the first gap: ternarySearch(a, 2) == 1 and ternarySearch(a, 3) == 1.
  • Repeated equality must return the first duplicate: ternarySearch(a, 4) == 1.
  • Values in the second gap: ternarySearch(a, 5) == 3 and ternarySearch(a, 9) == 3.
  • Equality with the final entry: ternarySearch(a, 10) == 3.
  • Beyond the final entry: ternarySearch(a, 11) == 4 and ternarySearch(a, Int.MaxValue) == 4.
For every tested target, also assert that the array is unchanged, the result lies in , every entry before it is strictly smaller, and every entry from it onward is at least the target. These postconditions check the intended partition directly rather than merely accepting any equal occurrence.
The algorithmic intention is exponentiation by squaring to compute for . With exact arithmetic, its loop invariant is
Initially result = 1, y = x, and i = n. For an even integer , squaring y and replacing i by preserves the product. For an odd integer , first multiply result by y; then . The nonnegative loop variant i decreases by halving whenever positive. At exit , so the loop invariant yields result = x^n. There are multiplication steps.
Two qualifications are essential for the actual source. There is no requirement that n be nonnegative: for every n <= 0 the printed function simply returns 1.0. Also, var y = x infers Int, so y *= y uses wrapping integer arithmetic, while the accumulator uses floating-point arithmetic. For example, anotherfunc(50000, 2L) returns -1794967296.0, rather than 2500000000.0. An exact-power loop invariant cannot prove a false claim about that execution.
More precisely, for positive n, after iterations the remaining exponent is , and the Int base is the signed 32-bit representative of modulo . The accumulator multiplies those signed representatives for the set bits of n, in increasing bit order, with a floating-point rounding after each multiplication. This describes the actual code even when the intended power law fails. In an exact implementation, use a nonnegative-exponent precondition and arbitrary-precision integers, for example:
def powerExact(x: Int, n: Long): BigInt = {
  require(x > 0 && n >= 0)
  var result = BigInt(1)
  var y = BigInt(x)
  var i = n
  while (i > 0) {
    if (i % 2 == 1) result *= y
    y *= y
    i /= 2
  }
  result
}
The displayed loop invariant applies exactly to this version. It performs logarithmically many arbitrary-precision multiplications; their bit cost grows with operand size, so that statement is not an bit-complexity bound. Merely making the accumulator a Double does not widen the separate Int base variable.
Use parallel arrays for keys and their representative values, with only a prefix active:
override val capacity: Int = 1000
private val elements = new Array[Int](capacity)
private val representatives = new Array[Int](capacity)
private var used = 0
The chosen bound is an explicit implementation parameter of the abstract data type; another a-priori positive bound works identically. The initial map is empty because used == 0. Zero-filled unused cells are not members of the map, so zero and negative keys remain valid integers. Use DisjointSets consistently as the trait name; the source's prose variation DisjointSubsets does not change the declared interface.
The maximally variant safe declarations are:
trait Rel1[+X, +Y] { val pairs: List[(X, Y)] }
trait Rel2[-X, +Y] { def relatives(x: X): List[Y] }
trait Rel3[-X, -Y] { def related(x: X, y: Y): Boolean }
Leaving one or both parameters invariant is also legal but admits fewer subtyping conversions. These are type variance annotations.
For Rel1, both parameters occur only as outputs. Scala's immutable List and Tuple2 are covariant, so a list of pairs of narrower types can safely be read as pairs of broader types. Thus both may be covariant type parameters. A contravariant declaration would permit, for example, treating a Rel1[Any, Int] containing (7, 0) as a Rel1[String, Int], then reading its first component as a String. That would be unsound; the compiler rejects the negative annotation at this output position.
For Rel2, X occurs as a method argument and therefore may be a contravariant type parameter; Y is returned in an immutable list and may be a covariant type parameter. A function that accepts every Any is safe to use where only String queries are issued. The opposite direction would be unsafe: if X were covariant, the following hypothetical conversion could call a string-only implementation with an integer:
val strings: Rel2[String, Int] = new Rel2[String, Int] {
  def relatives(x: String): List[Int] = List(x.length)
}
// Unsafe if Rel2 were incorrectly covariant in X:
// val arbitrary: Rel2[Any, Int] = strings
// arbitrary.relatives(7)
Making Y contravariant would instead allow an integer-valued Rel2[String, Any] to be read as a string-valued Rel2[String, String], recreating the output error.
For Rel3, both generic values are consumed and only a Boolean function result is produced, so both may be contravariant type parameters. A predicate accepting all values of broad types can answer queries restricted to narrower types. Covariance in either parameter would allow passing an unsupported value to a specialized implementation. For example, treating a string-only first-argument predicate as accepting Any would permit related(7, y) even though its body might call x.length. These are applications of the variance-position rule: method inputs reverse variance, whereas immutable outputs preserve it.[ref]
Set and . If , the integrand is one and its integral is . If is a nonzero integer,
Thus
This is Fourier orthogonality in its unconjugated form. With a complex conjugate on the second exponential, the nonzero case would instead be .
Pell equation Created 2026-09-29 Updated 2026-11-05
For a nonsquare positive integer , the Pell equation is
Periodic continued fractions of produce infinitely many integer solutions.
Pentagonal number 2026-10-20
The th pentagonal number is for a positive integer , giving . A positive integer is pentagonal exactly when is a perfect square and is an integer, by the defining quadratic equation.
Perfect cube 2026-10-20
An integer equal to the third power of another integer, such as or .
Perfect number Created 2026-10-14 Updated 2026-10-14
A perfect number is a positive integer equal to the sum of all its positive proper divisors. The divisor itself is excluded: including it gives the equivalent condition for the sum-of-divisors function. The smallest examples are and .
For comparison, has proper divisors , whose sum is : it is a deficient number. The proper divisors of are , whose sum is : it is an abundant number. The proper-divisor sum classifies these examples with the same rule, and gives , so one is not a perfect number.
Figure 1. . Original exact proper-divisor sums for . Each bar is normalized by its candidate number, and its segments are labelled with the actual proper divisors. The dashed line at one marks equality with the candidate. These are finite arithmetic calculations, not empirical data. Details.
The interesting question is how such balances can be constructed without testing every smaller integer as a possible divisor. The Euclid-Euler theorem answers it for even integers: a Mersenne prime gives , and every even perfect number arises this way. For , this produces . The connection links divisor sums to primality testing for a particular family, while keeping the necessary hypotheses visible.[ref]
Euclid's Elements already gives the construction in Book IX, Proposition 36: add a succession of powers of two, and if their sum is prime, multiply by the final power of two. The modern finite geometric series makes the same pattern transparent. This original statement supplies the forward construction, rather than the converse classification of all even perfect numbers.[ref]
Perfect power Created 2026-09-24 Updated 2026-11-05
An integer is a perfect power if it can be written with integers and . In the common nontrivial positive version, both the value and the base exceed one. For example, qualifies, whereas twelve does not. The degenerate values , and are included or excluded according to the convention being used.
For a positive integer with prime factorization , the exact criterion is
If , every prime exponent is divisible by . Conversely, a common divisor lets one take . This gives a recognition test once the prime factorization is known; it does not imply that factorization is the fastest recognition algorithm.
A negative value requires an odd exponent. Thus is a perfect power, while is not: its absolute value has only powers of two as common divisors of its exponents. Perfect cubes are the special case , whereas a cube-full number imposes a different lower bound on each prime exponent.
Perfect square test 2026-10-20
For a nonnegative integer , compute its integer square root and accept exactly when . An approximate square root must be corrected with exact integer comparisons before this equality is tested. This procedure distinguishes a squareness test from merely approximating a square root.
For positive integers , partition the nonnegative integers by equality of and separately by equality of . The intersection of equivalence relations gives nonempty intersections of these consecutive blocks. Its boundaries occur at multiples of either or .
Let . Translating by increases the two floor quotients by the fixed integers and , so it preserves all within-block equalities and all block boundaries. Thus the refinement repeats in intervals of length . If lists the multiples of or within one period, its blocks are exactly for and . The pattern repeats, but blocks in different periods remain distinct equivalence classes.
Periodic continued fraction of a quadratic irrational Created 2026-09-24 Updated 2026-11-05
The simple continued fraction of a quadratic irrational is eventually periodic. For a nonsquare positive integer , the continued fraction of is periodic after its integer part.
Periodic extension Created 2026-10-20 Updated 2026-10-25
For , values of a function on a half-open interval determine its periodic extension to the real line: choose the unique integer with and set . The resulting periodic function has period . If the endpoint limits of differ, the extension has a jump discontinuity at every period boundary. Under the usual piecewise-smooth convergence hypotheses, its Fourier series takes the average of the two one-sided limits there; an assigned value at an isolated endpoint does not change the Fourier coefficients.
A block determines a repeating sequence by setting for every integer . The inverse discrete Fourier transform gives this extension because each discrete Fourier mode satisfies . The extension explains why circular convolution wraps indices around the block. It specifies values at discrete indices; a continuous curve between samples requires an additional choice of interpolation.
Periodicity Created 2026-10-25 Updated 2026-11-05
Periodicity is invariance of a function under a nonzero shift . Its domain of a function must be preserved by the shift and its inverse, and at every allowed function input. On the real line, both and have period .
For an angular coordinate on a full circle, single-valuedness requires -periodicity. For nonzero real , the functions and are -periodic precisely when is an integer: the phase must change by an integer multiple of . The zero-frequency case instead gives constant functions. Their Fourier series supply angular modes for the harmonic expansion on a disk.
Periodic modular exponentiation Created 2026-09-24 Updated 2026-11-05
For a unit modulo an integer modulus , the function , , is periodic. Negative exponents use the modular multiplicative inverse of .
If is the multiplicative order of , then
for every integer . It is the least positive period: any positive period gives , so . For example, powers of two modulo seven repeat , and fits the same cycle.
The unit hypothesis matters. Powers of two modulo eight start on nonnegative integers; this whole sequence has no positive period from its starting point, and negative powers are undefined. Euler's theorem guarantees a return exponent for units, while the multiplicative order identifies the smallest one.
If a periodic unimodular function and its inverse have absolutely summable Fourier coefficients, replacing by preserves the orthonormal integer-translate span and integrability of an integrable scaling function. In physical space this is an absolutely summable combination of integer function translations. The new MRA low-pass filter is . A rough phase can therefore preserve the multiresolution analysis while changing MRA low-pass filter regularity.
Periodic sequence Created 2026-10-14 Updated 2026-10-20
A sequence indexed from zero with an integer period satisfying the displayed identity for all . Repeating a finite cycle is an example. The Cesàro mean article explains why its cumulative averages approach the one-cycle arithmetic mean.