Skip to main content

Number theory

The 60 definitions of the number theory library, each with its Epsil spelling, its MathJSON name, its signature and its full description.

Each definition is listed under its Epsil spelling (the MathJSON name when it has none), with its signature in the engine's type syntax. The Standard Library page is the one-page index of every category.

Definitions​

bernoulliB​

MathJSON BernoulliB · (integer) -> rational

Return the nth Bernoulli number Bₙ as an exact rational, using the convention B₁ = -1/2. Odd n > 1 give 0.

bernoulliB(2)
// ➔ 1/6

carmichaelLambda​

MathJSON CarmichaelLambda · (integer) -> integer

Return the Carmichael function λ(n) (the reduced totient): the smallest positive integer m such that a^m ≡ 1 (mod n) for every a coprime to n. Defined for n ≥ 1.

carmichaelLambda(15)
// ➔ 4

catalanNumber​

MathJSON CatalanNumber · (integer) -> integer

Return the nth Catalan number C(n) = (2n)! / ((n+1)! · n!): 1, 1, 2, 5, 14, 42, … Defined for n ≥ 0.

catalanNumber(5)
// ➔ 42

chineseRemainder​

MathJSON ChineseRemainder · (collection<any>, collection<any>) -> integer

Solve a system of simultaneous congruences: return the smallest non-negative integer x such that x ≡ residues[i] (mod moduli[i]) for every i. Undefined if the system is inconsistent or the two lists differ in length.

chineseRemainder([2, 3, 2], [3, 5, 7])
// ➔ 23

continuedFraction​

MathJSON ContinuedFraction · (real, integer?) -> list<integer>

Return the continued-fraction expansion of x as a list of integer terms [a0, a1, …]. An exact rational is expanded fully; an inexact value is expanded as its best rational approximation at working precision (see Rationalize), truncated to the optional n terms (default 20).

continuedFraction(43/19)
// ➔ [2,3,1,4]

digitCount​

MathJSON DigitCount · (integer, integer?, integer?) -> integer | list<integer>

Count digits of n in the given base (default 10); the sign of n is ignored. With a third argument digit, return how many times that digit occurs. Otherwise return a list [count of 1, count of 2, …, count of base-1, count of 0].

digitCount(122, 10, 2)
// ➔ 2

digitSum​

MathJSON DigitSum · (integer, integer?) -> integer

Return the sum of the digits of n in the given base (default 10). The sign of n is ignored.

digitSum(1234)
// ➔ 10

dirichletCharacter​

MathJSON DirichletCharacter · (integer, integer, integer) -> number

The Dirichlet character χ_j(n) modulo k, the j-th of the φ(k) characters (Wolfram's indexing, j = 1 the principal character). Zero where gcd(n, k) > 1; otherwise a root of unity.

dirichletCharacter(5, 2, 2)
// ➔ i
dirichletCharacter(7, 3, 3)
// ➔ e^(2/3i * pi)

dirichletL​

MathJSON DirichletL · (integer, integer, number) -> number

The Dirichlet L-function L(s, χ) = Σ χ(n)/nˢ (n ≥ 1) of the character χ_j modulo k (DirichletCharacter(k, j, ·)): k^(−s) Σ_{r=1}^{k} χ(r) ζ(s, r/k). Entire for a non-principal character; the principal one is ζ(s) Π_{p|k} (1 − p^(−s)).

dirichletL(1, 1, 2)
// ➔ 1/6 * pi^2
dirichletL(3, 2, -2)
// ➔ -2/9
dirichletL(5, 2, 0)
// ➔ (3/5 + 1/5i)

divides​

MathJSON Divides · (integer, integer) -> boolean

Divides(a, b) returns True if a divides b (i.e. b is an integer multiple of a), corresponding to the notation a ∣ b. Both operands are integers; a symbolic operand keeps the relation unevaluated.

divides(3, 12)
// ➔ "True"

divisorSigma​

MathJSON DivisorSigma · (integer, integer) -> integer

The divisor function σ_k(n) = Σ_{d | n} dᵏ over the positive divisors of n. σ₀ counts divisors, σ₁ sums them. Defined for n ≥ 1.

divisorSigma(2, 6)
// ➔ 50

divisors​

MathJSON Divisors · (integer) -> list<integer>

Return the sorted list of positive divisors of an integer n. The sign of n is ignored.

divisors(12)
// ➔ [1,2,3,4,6,12]

eulerPhi​

MathJSON EulerPhi · (integer) -> integer

EulerPhi is an alias for Totient, which is the preferred name. Euler's totient function φ(n): count of positive integers ≤ n that are coprime to n, for n ≥ 1; φ(0) = 0 and φ(−n) = φ(n).

eulerPhi(12)
// ➔ 4

eulerian​

MathJSON Eulerian · (integer, integer) -> integer

Eulerian number A(n, m): number of permutations of {1..n} with exactly m ascents.

extendedGCD​

MathJSON ExtendedGCD · (integer, integer) -> tuple<integer, integer, integer>

Return the extended GCD of a and b as a tuple (g, x, y) where g = gcd(a, b) is non-negative and a·x + b·y = g (Bézout coefficients).

extendedGCD(12, 18)
// ➔ (6, -1, 1)

factorInteger​

MathJSON FactorInteger · (integer) -> list<tuple<integer, integer>>

Return the prime factorization of an integer n as a list of [prime, exponent] tuples, ordered by ascending prime. For a negative n, a leading [-1, 1] tuple carries the sign.

factorInteger(360)
// ➔ [(2, 3),(3, 2),(5, 1)]

fromContinuedFraction​

MathJSON FromContinuedFraction · (collection<any>) -> number

Reconstruct the (rational) value of a continued fraction given its list of integer terms [a0, a1, …].

fromContinuedFraction([2, 3, 1, 4])
// ➔ 43/19

fromDigits​

MathJSON FromDigits · (collection<any>, integer?) -> integer

Reconstruct an integer from its list of digits (most-significant first) in the given base (default 10). The inverse of IntegerDigits. Digits outside [0, base) are combined positionally (Horner evaluation).

fromDigits([1, 2, 3, 4])
// ➔ 1234

integerDigits​

MathJSON IntegerDigits · (integer, integer?, integer?) -> list<integer>

Return the digits of n in the given base (default 10), most-significant first. The sign of n is ignored. With a third argument length, the result is zero-padded on the left (or truncated to its least-significant digits) to that length.

integerDigits(255, 16)
// ➔ [15,15]

integerSqrt​

MathJSON IntegerSqrt · (integer) -> integer

Return the integer square root of n, i.e. the largest integer m such that m² ≤ n. Undefined for negative n.

integerSqrt(17)
// ➔ 4

isAbundant​

MathJSON IsAbundant · (integer) -> boolean

True if n is an abundant number (sum of divisors > 2n).

isCenteredSquare​

MathJSON IsCenteredSquare · (integer) -> boolean

True if n is a centered square number.

isHappy​

MathJSON IsHappy · (integer) -> boolean

True if n is a happy number, a number which eventually reaches 1 when the number is replaced by the sum of the square of each digit

isOctahedral​

MathJSON IsOctahedral · (integer) -> boolean

True if n is an octahedral number.

isPerfect​

MathJSON IsPerfect · (integer) -> boolean

Returns "True" if n is a perfect number, a positive integer which equals the sum of all its divisors.

isPerfectPower​

MathJSON IsPerfectPower · (integer) -> boolean

Return "True" if n is a perfect power a^b for integers a and b ≥ 2 (a negative n requires an odd exponent). The smallest perfect power is 4.

isPerfectPower(64)
// ➔ "True"

isSquare​

MathJSON IsSquare · (integer) -> boolean

True if n is a perfect square.

isSquareFree​

MathJSON IsSquareFree · (integer) -> boolean

Return "True" if n is square-free (not divisible by any perfect square > 1). The sign of n is ignored.

isSquareFree(30)
// ➔ "True"

isTriangular​

MathJSON IsTriangular · (integer) -> boolean

True if n is a triangular number.

jacobiSymbol​

MathJSON JacobiSymbol · (integer, integer) -> integer

The Jacobi symbol (a/n) for an odd n > 0. Returns -1, 0, or 1. Undefined when n is even or non-positive.

jacobiSymbol(5, 21)
// ➔ 1

legendreSymbol​

MathJSON LegendreSymbol · (integer, integer) -> integer

The Legendre symbol (a/p) for an odd prime p. Returns -1, 0, or 1. Undefined when p is not an odd prime.

legendreSymbol(3, 7)
// ➔ -1

lucas​

MathJSON Lucas · (integer) -> integer

Lucas is an alias for LucasL, which is the preferred name. Returns the nth Lucas number.

lucasL​

MathJSON LucasL · (integer) -> integer

Return the nth Lucas number: LucasL(0) is 2, LucasL(1) is 1, and LucasL(n) = LucasL(n-1) + LucasL(n-2). Negative indices follow LucasL(-n) = (-1)^n · LucasL(n).

lucasL(10)
// ➔ 123

modularInverse​

MathJSON ModularInverse · (integer, integer) -> integer

Return the modular multiplicative inverse of a modulo m: the integer x with a·x ≡ 1 (mod m). The sign of x follows the sign of m (the same floored-division convention as Mod). Undefined when a and m are not coprime.

modularInverse(3, 7)
// ➔ 5
modularInverse(3, -7)
// ➔ -2

moebiusMu​

MathJSON MoebiusMu · (integer) -> integer

Return the Möbius function μ(n): 0 if n is divisible by a perfect square > 1, otherwise (-1) raised to the number of distinct prime factors. The sign of n is ignored.

moebiusMu(30)
// ➔ -1

multiplicativeOrder​

MathJSON MultiplicativeOrder · (integer, integer, list<integer>?) -> integer

The multiplicative order of a modulo n: the smallest k > 0 such that a^k ≡ 1 (mod n). Undefined unless a and n are coprime. With a list of residues, MultiplicativeOrder(a, n, [r1, r2, …]) is the smallest k > 0 such that a^k ≡ r_i (mod n) for some i (a discrete logarithm), and is undefined when no r_i is a power of a. The sign of n is ignored. Undefined for n = 0.

multiplicativeOrder(2, 7)
// ➔ 3
multiplicativeOrder(5, 7, [3, 11])
// ➔ 2

nPartition​

MathJSON NPartition · (integer) -> integer

Number of integer partitions of n, for n ≥ 0; it is 0 for n < 0.

nextPrime​

MathJSON NextPrime · (integer, integer?) -> integer

Return the smallest prime greater than n. With a second argument k, return the kth prime after n (k < 0 returns the |k|th prime before n).

nextPrime(10)
// ➔ 11
nextPrime(10, -1)
// ➔ 7

notDivides​

MathJSON NotDivides · (integer, integer) -> boolean

NotDivides(a, b) returns True if a does not divide b, corresponding to the notation a ∤ b.

nthPrime​

MathJSON NthPrime · (integer) -> integer

Return the nth prime number (1-based): NthPrime(1) is 2, NthPrime(2) is 3, …

nthPrime(10)
// ➔ 29

partitionsP​

MathJSON PartitionsP · (integer) -> integer

PartitionsP is an alias for NPartition, which is the preferred name. Number of integer partitions of n, for n ≥ 0; it is 0 for n < 0.

partitionsP(5)
// ➔ 7

powerMod​

MathJSON PowerMod · (integer, rational, integer) -> integer

Return a^b mod m (modular exponentiation). A negative b uses the modular inverse of a; the result is undefined when that inverse does not exist (i.e. when a and m are not coprime). The result is in the range [0, m). A rational exponent s/r gives the least x with x^r ≡ a^s (mod m), the first entry of PowerModList(a, s/r, m). It is undefined when there is none, when m cannot be factored, or when there are too many roots to list and none of them is less than 100000.

powerMod(2, 10, 1000)
// ➔ 24
powerMod(4, 1/2, 7)
// ➔ 2

powerModList​

MathJSON PowerModList · (integer, rational, integer) -> list<integer>

Return the sorted list of every x in [0, m) with x^r ≡ a^s (mod m), for the exponent s/r. An integer exponent gives the single value a^s mod m, a negative one using the modular inverse of a. The list is empty when a^s is not an r-th power mod m. Undefined for a modulus m < 1, when the inverse of a does not exist, or when m cannot be factored or there are too many roots to list.

powerModList(3, 1/2, 11)
// ➔ [5,6]
powerModList(1, 1/3, 7)
// ➔ [1,2,4]

primeFactors​

MathJSON PrimeFactors · (integer) -> list<integer>

Return the sorted list of distinct prime factors of an integer n. The sign of n is ignored; PrimeFactors(1) is the empty list.

primeFactors(360)
// ➔ [2,3,5]

primeNu​

MathJSON PrimeNu · (integer) -> integer

Return ω(n), the number of distinct prime factors of n. The sign of n is ignored; PrimeNu(1) is 0.

primeNu(360)
// ➔ 3

primeNumber​

MathJSON PrimeNumber · (integer) -> integer

The nth prime number. PrimeNumber is an alias for NthPrime, which is the preferred name.

primeOmega​

MathJSON PrimeOmega · (integer) -> integer

Return Ω(n), the number of prime factors of n counted with multiplicity. The sign of n is ignored; PrimeOmega(1) is 0.

primeOmega(360)
// ➔ 6

primePi​

MathJSON PrimePi · (real) -> integer

Return π(n), the prime-counting function: the number of primes less than or equal to n.

primePi(10)
// ➔ 4

primitiveRoot​

MathJSON PrimitiveRoot · (integer) -> integer

The smallest primitive root modulo n (a generator of the multiplicative group of integers mod n), or undefined if none exists (which happens unless n is 1, 2, 4, pᵏ, or 2pᵏ for an odd prime p). The sign of n is ignored, and PrimitiveRoot(1) is 0. Undefined for n = 0.

primitiveRoot(7)
// ➔ 3

primitiveRootList​

MathJSON PrimitiveRootList · (integer) -> list<integer>

The sorted list of all primitive roots modulo n: the generators of the multiplicative group of integers mod n. The list is empty when there is none (unless n is 1, 2, 4, pᵏ, or 2pᵏ for an odd prime p), and for n = 0. PrimitiveRootList(1) is [0], as PrimitiveRoot(1) is 0. The sign of n is ignored. Undefined when n cannot be factored or there are too many roots to list.

primitiveRootList(7)
// ➔ [3,5]
primitiveRootList(8)
// ➔ []

radical​

MathJSON Radical · (integer) -> integer

Return the radical of n (its square-free kernel): the product of its distinct prime factors. The sign of n is ignored; Radical(1) is 1.

radical(360)
// ➔ 30

randomPrime​

MathJSON RandomPrime · (integer, integer?) random -> integer

Return a random prime. RandomPrime(n) draws a prime in [2, n]; RandomPrime(m, n) draws a prime in [m, n]. Undefined if the range contains no prime.

randomPrime(100)

rationalReconstruction​

MathJSON RationalReconstruction · (integer, integer) -> rational

The rational p/q with p ≡ a·q (mod m) and |p|, q ≤ ⌊√((m − 1)/2)⌋, the unique such fraction in lowest terms when it exists (Wang's algorithm). Undefined for m < 1 or when there is none.

rationalReconstruction(6, 11)
// ➔ 1/2

sigma0​

MathJSON Sigma0 · (integer) -> integer

Number of positive divisors of n.

sigma1​

MathJSON Sigma1 · (integer) -> integer

Sum of positive divisors of n.

sigmaMinus1​

MathJSON SigmaMinus1 · (integer) -> rational

Sum of reciprocals of positive divisors of n.

stirling​

MathJSON Stirling · (integer, integer) -> integer

Stirling number of the second kind S(n, m): ways to partition n elements into m non-empty subsets.

stirlingS1​

MathJSON StirlingS1 · (integer, integer) -> integer

Signed Stirling number of the first kind s(n, m): the coefficient of x^m in the falling factorial x(x−1)…(x−n+1). Its absolute value counts the permutations of n elements with exactly m disjoint cycles.

stirlingS1(5, 2)
// ➔ -50

stirlingS2​

MathJSON StirlingS2 · (integer, integer) -> integer

StirlingS2 is an alias for Stirling, which is the preferred name. Returns the Stirling number of the second kind S(n, k).

stirlingS2(6, 3)
// ➔ 90

totient​

MathJSON Totient · (integer) -> integer

Euler's totient function φ(n): count of positive integers ≤ n that are coprime to n, for n ≥ 1; φ(0) = 0 and φ(−n) = φ(n).