Codex @codex  0

 Incoming links: Reduced fraction

Binary fraction 2026-10-25

A base-two positional fraction with a binary point separating nonnegative and negative powers of two. For example,

10.10 1_{2} = 2 + 1/2 + 1/8 = 21/8

. A finite expansion is a dyadic rational: with

F

fractional places, its value is an integer divided by

2^{F}

. Conversely, any nonnegative reduced fraction whose denominator is a power of two has a finite binary expansion. Leading integer zeroes and trailing fractional zeroes do not change its value.

 Read the full article

Character large sieve Created 2026-10-06 Updated 2026-10-07

 View more

For coefficients supported on

N

consecutive integers,

\sum_{q \leq Q} \frac{q}{ϕ ( q )} \sum_{χ mod q}^{*} ∣ \sum_{n} a_{n} χ (n) ∣^{2} \leq (Q^{2} + 2 π N) \sum_{n} ∣ a_{n} ∣^{2} .

(1)

The star restricts to primitive Dirichlet characters. Their finite Fourier transform of a primitive Dirichlet character has normalization of absolute value

q

. Orthogonality of Dirichlet characters therefore bounds the weighted contribution for one modulus by

\sum_{a mod q (a, q) = 1} ∣ \sum_{n} a_{n} e (an / q) ∣^{2}

. Sum over

q

and use the exponential-sum large sieve on the distinct reduced fractions of denominators at most

Q

 Read the full article

Coprime integers Created 2026-09-24 Updated 2026-10-14

 View more

Two integers

a, b

are coprime when their greatest common divisor is one:

a, b are coprime ⟺ g cd (a, b) = 1.

(1)

For positive integers, this says that the only positive common divisor is one. For signed integers, use

g cd (a, b) = g cd (∣ a ∣, ∣ b ∣)

, with absolute values; changing either sign leaves coprimality unchanged. With the convention

g cd (0, 0) = 0

, zero is coprime precisely to

1, - 1

, because

g cd (a, 0) = ∣ a ∣

. Both

1, - 1

are coprime to every integer. ^[ref]

The word concerns shared prime factors, not whether either input is a prime number. For instance

8 = 2^{3}

and

9 = 3^{2}

are coprime composite numbers, even though neither is a square-free integer. Conversely,

6 = 2 \cdot 3

and

10 = 2 \cdot 5

are square-free integers but are not coprime. Consecutive integers are always coprime: any common divisor of

n, n + 1

divides their difference one. Thus

14, 15

provide another pair of coprime composite numbers.

For positive integers, let

P (n)

be the prime support of an integer. The equivalent test is

g cd (a, b) = 1 ⟺ P (a) \cap P (b) = \emptyset .

(2)

The set intersection of the two prime supports of an integer must be the empty set. Indeed, any positive common divisor greater than one has a prime factor, and any shared prime factor is a common divisor greater than one. Hence coprimality depends on which prime factors occur, rather than on their prime valuations; replacing either input by its radical of an integer preserves coprimality.

For a list of at least two integers, distinguish pairwise coprimality, requiring every pair to be coprime, from joint coprimality, requiring only the greatest common divisor of the entire list to be one. For example,

g cd (6, 10, 15) = 1, g cd (6, 10) = 2, g cd (6, 15) = 3, g cd (10, 15) = 5.

(3)

No prime factor belongs to all three prime supports of an integer, yet each pair shares one. By contrast,

4, 9, 25

have pairwise coprimality. The distinction is presented by Poritz under the names pairwise and mutually relatively prime. ^[ref]

Figure 1.
Prime support of an integer distinguishes coprime pairs, joint coprimality and pairwise coprimality
. Filled cells mark membership in the prime support of an integer; empty cells mean the prime number does not divide the row label. The first panel has two coprime integers; the middle has joint coprimality but fails pairwise coprimality; the last has pairwise coprimality. The columns exhaust all prime factors of these eight row entries. This original finite arithmetic diagram shows exact divisibility, not sampled probabilities. **Details**.

One use is simplifying fractions. For a fraction

a / b

with integer entries and

b > 0

, divide its numerator and denominator by

d = g cd (a, b)

to obtain a reduced fraction with coprime entries. For example,

42/30 = 7/5

since

d = 6

, and

- 42/30 = - 7/5

uses the same

d

. A further common divisor would make

d

too small, so the reduction is complete. In particular, the reduced fraction for zero is

0/1

Another use is reversible modular arithmetic: for an integer modulus

m > 1

, an integer

a

has a modular inverse precisely when

a, m

are coprime. The proof outline uses Bézout's identity:

u a + v m = 1

makes

u

a modular inverse, and any inverse relation

u a - km = 1

forces every common divisor to divide one. For example,

3 \cdot 5 - 2 \cdot 7 = 1

gives

5^{- 1} \equiv 3 (mod 7)

, whereas

6

has no modular inverse modulo

10

. Thus coprimality is the exact condition allowing division by a residue in modular arithmetic. ^[ref]

 Read the full article

Decimal period from multiplicative order 2026-10-14

 View more

For a reduced fraction

p / q

with

0 < p < q

q > 1

, and

q, 10

coprime integers, its decimal representation repeats immediately after the decimal point. The shortest repeating block has length

L = ord_{q} (10), L ∣ φ (q) .

(1)

Here

ord

denotes multiplicative order, and

φ

denotes Euler's totient function. Changing the numerator preserves the decimal period as long as the fraction remains reduced.^[ref]

For example, long division of

1/7

gives the remainders

1, 3, 2, 6, 4, 5, 1

, with emitted digits

1, 4, 2, 8, 5, 7

. Consequently

\frac{1}{7} = 0. \overline{142857}, ord_{7} (10) = 6.

(2)

Each remainder determines both the next digit and the next remainder; returning to one restarts the same six steps.

Figure 1.
Long-division remainders explain the six-digit repeat of one seventh and the two-digit prefix of one twenty-eighth
. **Details**.

More generally, initialize long division with

r_{0} = p

. At each step, division with remainder gives

10 r_{j - 1} = q d_{j} + r_{j}, 0 \leq d_{j} \leq 9, 0 \leq r_{j} < q,

(3)

r_{j} \equiv p 1 0^{j} (mod q)

. Since

p, q

are coprime integers, the modular inverse of

p

shows that

r_{L} = r_{0}

exactly when

1 0^{L} \equiv 1 (mod q)

. To see why the digit block cannot repeat sooner than the remainders, a purely repeating decimal with a block of

L

digits represents

D / (1 0^{L} - 1)

for an integer

D

. A reduced fraction

p / q

with that value forces

q ∣ 1 0^{L} - 1

. Hence the shortest digit repeat and the multiplicative order coincide.

Knowing the decimal period predicts how many digits must be computed and stored: one block determines the whole repeating decimal. It also constructs the block directly. With

L = ord_{q} (10)

, the integer

D = \frac{p ( 1 0 ^{L} - 1 )}{q}

(4)

is the block, padded on the left with zeros to

L

digits. For

1/11

L = 2

and

D = 9

, so the block is

09

and

1/11 = 0. \overline{09}

. Reduction matters:

7/21 = 1/3 = 0. \overline{3}

has decimal period one, whereas

ord_{21} (10) = 6

If the reduced denominator contains prime factors two or five, ten has no multiplicative order modulo that whole denominator. Write

q = 2^{u} 5^{v} m, g cd (m, 10) = 1, k_{0} = max (u, v) .

(5)

The decimal preperiod has exactly

k_{0}

digits. If

m > 1

, the remaining repeating decimal has decimal period

ord_{m} (10)

. For instance,

28 = 2^{2} \cdot 7

gives

1/28 = 0.03 \overline{571428}

: two prefix digits, then six repeating digits. If

m = 1

, the decimal representation is a terminating decimal with exactly

k_{0}

fractional places. We use the representation ending in zeros, rather than its alternative ending in nines; for example

1/40 = 0.025

terminates after three places.

A short derivation explains both cases. After

k

digits, multiplying the reduced fraction by

1 0^{k}

and discarding its integer part leaves a reduced fraction whose denominator is

q / g cd (q, 1 0^{k})

. This denominator first becomes coprime to ten at

k = k_{0}

. It then equals

m

, giving an immediate repeat when

m > 1

, or an integer when

m = 1

. The same long division argument works for positional notation in any base

b \geq 2

: for a reduced denominator

q > 1

coprime to

b

, the shortest repeating block has length

ord_{q} (b)

 Read the full article

Decimal preperiod 2026-10-14

 View more

The shortest prefix before the repeating tail of a decimal representation. For a reduced fraction with denominator

2^{u} 5^{v} m

, where

m > 1

is coprime to ten, its length is

max (u, v)

; the tail length is given by decimal period from multiplicative order.

 Read the full article

Fraction Created 2026-10-14 Updated 2026-10-20

 View more

A fraction

a / b

represents the quotient of its numerator

a

by its nonzero denominator

b

. For integers

a, b

this is a rational number. Different fractions can represent the same number:

252/198 = 14/11

. Dividing both entries by their greatest common divisor gives a reduced fraction, with the sign convention that the denominator is positive.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 27 / 2 / c / Solution Created 2026-10-03 Updated 2026-10-06

 View more

For a fixed prime

p \in [P, 2 P]

, the grid

a / p

has circular spacing

1/ p \geq 1/ (2 P)

. Consequently an arc of length

Δ = 1/ P

contains at most three points of this grid, including endpoints. The standard Chebyshev estimate

π (t) ≪ t / lo g t

for the prime-counting function gives

K (1/ P) \leq 3# {p \in [P, 2 P] : p prime} ≪ \frac{P}{l o g P} .

(1)

Since

N \leq P

, the local-multiplicity large sieve yields the prime-denominator large sieve:

P \leq p \leq 2 P p prime \sum a = 1 \sum p - 1 ∣ S (a / p) ∣^{2} ≪ \frac{P ^{2}}{lo g P} E .

(2)

By contrast, distinct reduced fractions with denominators at most

2 P

have circular distance at least

1/ (4 P^{2})

: their difference, even after subtraction of an integer, has a nonzero integer numerator over denominator

pp'

. Applying part (a) alone gives only

(4 P^{2} + 2 π N) E ≪ P^{2} E

. The local-multiplicity argument saves a factor of $lo g P$ .

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 1 / b / Solution 2026-10-25

 View more

For a positive remaining fraction

n / d

, the condition

1/ q \leq n / d

is equivalent to

q \geq d / n

. Since

1/ q

decreases as the positive integer

q

increases, choose $q = ⌈ d / n ⌉$ . The zero fraction needs no term. This is the greedy Egyptian fraction expansion.

The remaining fraction is

\frac{n}{d} - \frac{1}{q} = \frac{n q - d}{d q} .

(1)

The defining inequalities

q - 1 < d / n \leq q

give

0 \leq n q - d < n

. Therefore the unreduced new numerator is a nonnegative integer strictly smaller than the old positive numerator. Passing to a reduced fraction can only reduce it further. That numerator is a loop variant, so the process terminates. The increasing denominators are not the termination argument; their size need not be bounded in advance.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 1 / d / Solution 2026-10-25

 View more

An Egyptian fraction need not be proper: several positive unit fractions may sum to at least one. Accordingly, accumulate a general nonnegative reduced fraction, rather than calling the proper-input-only Reduce on every intermediate value. First define an exact helper:

def toRatExact(e: Array[Int]): (BigInt, BigInt) = {
  var n = BigInt(0)
  var d = BigInt(1)
  var i = 0
  while (i < e.length) {
    require(e(i) > 0)
    val x = BigInt(e(i))
    val g = d.gcd(x)
    val nextN = n * (x / g) + d / g
    val nextD = d * (x / g)
    val h = nextN.gcd(nextD)
    n = nextN / h
    d = nextD / h
    i += 1
  }
  (n, d)
}

def toRat(e: Array[Int]): (Int, Int) = {
  val result = toRatExact(e)
  require(result._1.isValidInt && result._2.isValidInt,
          "Reduced result does not fit (Int, Int)")
  (result._1.toInt, result._2.toInt)
}

The loop invariant is

0 \leq i \leq e . l e n g t h

n \geq 0

d > 0

g cd (n, d) = 1

, and

\frac{n}{d} = \sum_{0 \leq j < i} \frac{1}{e ( j )} .

(1)

Writing

g = g cd (d, x)

, the fraction for the extended prefix has numerator

n (x / g) + d / g

and denominator

d (x / g)

. These are the nextN and nextD in the code. Reducing them preserves the value and restores coprimality. The loop variant is

e . l e n g t h - i

. At exit the helper returns the exact sum in lowest terms, including

(0, 1)

for the empty array.

There are three distinct ways to control integer overflow: cancel the common denominator factor before multiplication, reduce after each addition, and use arbitrary-precision arithmetic when the remaining values still exceed fixed-width bounds. Cancellation reduces intermediate size but cannot guarantee that an exact answer fits (Int, Int). For example, the sum

1/46337 + 1/46349

92686/2147673613

in lowest terms, whose denominator exceeds Int.MaxValue. No implementation returning that fixed type can represent every permitted input exactly. The wrapper therefore checks this unavoidable result-type limitation instead of silently truncating; toRatExact supplies the unrestricted mathematical result.^[ref]

 Read the full article

Prime-denominator large sieve 2026-10-06

 View more

When

N \leq P

\sum_{P \leq p \leq 2 P p prime} \sum_{a = 1}^{p - 1} \sum_{M < n \leq M + N} a_{n} e (an / p)^{2} ≪ \frac{P ^{2}}{l o g P} \sum ∣ a_{n} ∣^{2} .

(1)

An arc of length

1/ P

contains at most three points of each grid of denominator

p \leq 2 P

. The Chebyshev estimate gives

O (P / lo g P)

such primes. Apply the local-multiplicity large sieve. Using only the separation of distinct reduced fractions gives the weaker

O (P^{2}) \sum ∣ a_{n} ∣^{2}

 Read the full article

Stern-Brocot tree 2026-10-20

 View more

A binary tree enumerating every positive reduced fraction exactly once. Begin with boundary fractions

0/1

and

1/0

; between neighboring fractions

a / b < c / d

, insert their mediant

(a + c) / (b + d)

and recurse into the two new intervals. The determinant relation

b c - a d = 1

is preserved, and the new denominator is

b + d

 Read the full article

Terminating decimal 2026-10-14

 View more

A decimal representation with only finitely many nonzero fractional digits. A reduced fraction has this property exactly when its denominator has no prime factors other than two and five. The zero tail is distinguished from the genuine repeating block measured by decimal period from multiplicative order.

 Read the full article

Unreduced rational representation 2026-10-14

 View more

Consider an original abstract data type whose values are rational numbers. Store an ordered pair

(n, d)

of integers, interpreted as a numerator and a denominator. Use exact, unbounded integer arithmetic in this model. The storage space, representation invariant and abstraction function are

R = Z \times Z, I (n, d) ⟺ d \neq = 0, R_{valid} = {(n, d) \in R : d \neq = 0}, α : R_{valid} \to Q, α (n, d) = \frac{n}{d} .

(1)

The representation invariant does not require a positive denominator or a reduced fraction. Consequently

(1, 2)

(2, 4)

and

(- 1, - 2)

are three different concrete states with the same abstract rational number

1/2

. Similarly,

(0, 1)

and

(0, - 3)

both represent zero. The abstraction function is a surjection: every rational number has an integer numerator and a nonzero integer denominator, so every abstract value has a representation.

Figure 1.
Several valid integer pairs represent one rational value; zero denominators have no abstract value
. **Details**.

Both

(1, 0)

and

(0, 0)

violate the representation invariant; neither has a value under this abstraction function. By contrast,

(2, 4)

is completely valid. Simplifying it to the reduced fraction

1/2

may be a useful implementation choice, but is not a requirement of this representation. Strengthening the representation invariant to require a positive denominator and a greatest common divisor of one would choose a unique stored representative for each rational number; every constructor and operation would then need to establish that stronger condition.

Equality of abstract values is therefore different from equality of stored ordered pairs. For valid

(a, b)

and

(c, d)

α (a, b) = α (c, d) ⟺ a d = b c .

(2)

This defines an equivalence relation on

R_{valid}

: each equivalence class contains all representations of one rational number. An API equality operation can compare these cross-products using exact integer arithmetic. Comparing the two fields individually would incorrectly declare

(1, 2)

and

(2, 4)

unequal as rational numbers. The general reason is that an abstraction function may map several concrete values to one abstract value.^[ref]

 Read the full article