Skip to main content

Number Theory

The functions in this section provide tools for number-theoretic computations:
prime numbers and integer factorization, divisor functions, partitions, polygonal numbers, perfect/happy numbers, and special combinatorial counts (Eulerian, Stirling).

Function Definitions

Totient(n: integer) -> integer

Returns Euler’s totient function

φ(n)

: the number of integers

1 \leq k \leq n

that are coprime to

n

.

This function counts how many integers up to $n$ share no common factors with $n$ other than 1. For example, for $n=9$ , the integers coprime to 9 are 1, 2, 4, 5, 7, and 8, so $φ(9) = 6$ .

See also: Euler's totient function - Wikipedia

["Totient", 9]
// ➔ 6

Sigma0(n: integer) -> integer

Returns the number of positive divisors of

n

.

This function counts how many positive integers divide $n$ without a remainder. For example, for $n=6$ , the divisors are 1, 2, 3, and 6, so the count is 4.

See also: Divisor function - Wikipedia

["Sigma0", 6]
// ➔ 4

Sigma1(n: integer) -> integer

Returns the sum of positive divisors of

n

.

This function sums all positive divisors of $n$ . For example, for $n=6$ , the divisors are 1, 2, 3, and 6, and their sum is 12.

See also: Divisor function - Wikipedia

["Sigma1", 6]
// ➔ 12

SigmaMinus1(n: integer) -> number

Returns the sum of reciprocals of the positive divisors of

n

.

This function sums the reciprocals of all positive divisors of $n$ . For example, for $n=6$ , the divisors are 1, 2, 3, and 6, and the sum of reciprocals is 1 + 1/2 + 1/3 + 1/6 = 2.333...

See also: Divisor function - Wikipedia

["SigmaMinus1", 6]
// ➔ 2.333...

NthPrime(n: integer) -> integer

Returns the

n

th prime number (1-based): NthPrime(1) is 2, NthPrime(2) is 3, and so on.

For example, the 10th prime number is 29.

The function is named NthPrime rather than Prime because Prime denotes derivative notation (such as $f'$ ) in the Compute Engine. PrimeNumber is accepted as an alias and canonicalizes to NthPrime.

See also: Prime number - Wikipedia

["NthPrime", 10]
// ➔ 29

NextPrime(n: integer) -> integer

NextPrime(n: integer, k: integer) -> integer

Returns the smallest prime number greater than

n

.

With a second argument $k$ , returns the $k$ th prime after $n$ . A negative $k$ returns the $|k|$ th prime before $n$ , so NextPrime(n, -1) is the largest prime less than $n$ .

See also: Prime number - Wikipedia

["NextPrime", 10]
// ➔ 11

["NextPrime", 10, 3]
// ➔ 17

["NextPrime", 10, -1]
// ➔ 7

FactorInteger(n: integer) -> list<tuple<integer, integer>>

Returns the prime factorization of

n

as a list of [prime, exponent] tuples, ordered by ascending prime.

For example, $360 = 2^3 \times 3^2 \times 5$ , so the factorization is the list of tuples $(2, 3)$ , $(3, 2)$ , and $(5, 1)$ . The sign of a negative $n$ is carried in a leading $(-1, 1)$ tuple.

See also: Integer factorization - Wikipedia

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

Divisors(n: integer) -> list<integer>

Returns the sorted list of positive divisors of

n

.

For example, the divisors of 12 are 1, 2, 3, 4, 6, and 12. The sign of $n$ is ignored; Divisors(0) is left unevaluated since 0 has infinitely many divisors.

See also: Divisor - Wikipedia

["Divisors", 12]
// ➔ [1, 2, 3, 4, 6, 12]

PrimeFactors(n: integer) -> list<integer>

Returns the sorted list of distinct prime factors of

n

.

The sign of $n$ is ignored; PrimeFactors(1) is the empty list.

["PrimeFactors", 360]
// ➔ [2, 3, 5]

Radical(n: integer) -> integer

Returns the radical of

n

(its square-free kernel): the product of its distinct prime factors.

["Radical", 360]
// ➔ 30

PrimeNu(n: integer) -> integer

Returns

ω(n)

, the number of distinct prime factors of

n

.

See also: Prime omega function - Wikipedia

["PrimeNu", 360]
// ➔ 3

PrimeOmega(n: integer) -> integer

Returns

Ω(n)

, the number of prime factors of

n

counted with multiplicity.

See also: Prime omega function - Wikipedia

["PrimeOmega", 360]
// ➔ 6

MoebiusMu(n: integer) -> integer

Returns the Möbius function

μ(n)

: 0 if

n

is divisible by a perfect square greater than 1, otherwise

(-1)^k

where

k

is the number of distinct prime factors.

See also: Möbius function - Wikipedia

["MoebiusMu", 30]
// ➔ -1

IsSquareFree(n: integer) -> boolean

Returns "True" if

n

is square-free, i.e. not divisible by any perfect square greater than 1.

["IsSquareFree", 30]
// ➔ "True"

IsPerfectPower(n: integer) -> boolean

Returns "True" if

n

is a perfect power

a^b

for integers

a

and

b \geq 2

. A negative

n

requires an odd exponent; the smallest perfect power is 4.

See also: Perfect power - Wikipedia

["IsPerfectPower", 64]
// ➔ "True"

PrimePi(n: real) -> integer

Returns

π(n)

, the prime-counting function: the number of primes less than or equal to

n

.

See also: Prime-counting function - Wikipedia

["PrimePi", 10]
// ➔ 4

RandomPrime(n: integer) -> integer

RandomPrime(m: integer, n: integer) -> integer

Returns a random prime. RandomPrime(n) draws a prime in the interval

[2, n]

; RandomPrime(m, n) draws a prime in

[m, n]

. Undefined if the range contains no prime.

["RandomPrime", 100]
// ➔ 47 (for example)

PowerMod(a: integer, b: integer, m: integer) -> integer

Returns

a^b \bmod m

(modular exponentiation), in the range

[0, m)

.

A negative exponent $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).

See also: Modular exponentiation - Wikipedia

["PowerMod", 2, 10, 1000]
// ➔ 24

ExtendedGCD(a: integer, b: integer) -> tuple<integer, integer, integer>

Returns the extended GCD of

a

and

b

as a tuple

(g, x, y)

, where

g = \gcd(a, b)

is non-negative and

a\cdotx + b\cdoty = g

(the Bézout coefficients).

See also: Extended Euclidean algorithm - Wikipedia

["ExtendedGCD", 12, 18]
// ➔ (6, -1, 1)

ChineseRemainder(residues: collection, moduli: collection) -> integer

Returns the smallest non-negative integer

x

such that

x ≡ \mathrm{residues}_i \pmod{\mathrm{moduli}_i}

for every

i

. The moduli need not be coprime. Undefined if the system is inconsistent or the two lists differ in length.

See also: Chinese remainder theorem - Wikipedia

["ChineseRemainder", [2, 3, 2], [3, 5, 7]]
// ➔ 23

IntegerSqrt(n: integer) -> integer

Returns the integer square root of

n

: the largest integer

m

such that

m^2 \leq n

. Undefined for negative

n

.

See also: Integer square root - Wikipedia

["IntegerSqrt", 17]
// ➔ 4

CarmichaelLambda(n: integer) -> integer

Returns the Carmichael function

λ(n)

(the reduced totient): the smallest positive integer

m

such that

a^m ≡ 1 \pmod n

for every

a

coprime to

n

. Defined for

n \geq 1

.

See also: Carmichael function - Wikipedia

["CarmichaelLambda", 15]
// ➔ 4

LucasL(n: integer) -> integer

Returns the

n

th Lucas number: LucasL(0) is 2, LucasL(1) is 1, and

L_n = L_{n-1} + L_{n-2}

. Negative indices follow

L_{-n} = (-1)^n L_n

.

See also: Lucas number - Wikipedia

["LucasL", 10]
// ➔ 123

CatalanNumber(n: integer) -> integer

Returns the

n

th Catalan number

C_n = \frac{(2n)!}{(n+1)!\,n!}

: 1, 1, 2, 5, 14, 42, … Defined for

n \geq 0

.

See also: Catalan number - Wikipedia

["CatalanNumber", 5]
// ➔ 42

BernoulliB(n: integer) -> rational

Returns the

n

th Bernoulli number

B_n

as an exact rational, using the convention

B_1 = -\frac{1}{2}

. Odd

n > 1

give 0.

See also: Bernoulli number - Wikipedia

["BernoulliB", 12]
// ➔ -691/2730

ContinuedFraction(x: number) -> list<integer>

ContinuedFraction(x: number, n: integer) -> list<integer>

Returns the continued-fraction expansion of

x

as a list of integer terms

[a_0, a_1, \dots]

.

An exact rational is expanded fully. For an inexact value the expansion is truncated to the optional $n$ terms (default 20); note that floating-point round-off can introduce spurious large terms in the tail.

See also: Continued fraction - Wikipedia

["ContinuedFraction", ["Rational", 43, 19]]
// ➔ [2, 3, 1, 4]

FromContinuedFraction(terms: collection) -> number

Reconstructs the (rational) value of a continued fraction from its list of integer terms

[a_0, a_1, \dots]

.

["FromContinuedFraction", [2, 3, 1, 4]]
// ➔ 43/19

IntegerDigits(n: integer) -> list<integer>

IntegerDigits(n: integer, base: integer) -> list<integer>

IntegerDigits(n: integer, base: integer, length: integer) -> list<integer>

Returns 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]

DigitCount(n: integer, base: integer) -> list<integer>

DigitCount(n: integer, base: integer, digit: integer) -> integer

Counts digits of

n

in the given base (default 10); the sign of

n

is ignored.

With a third argument digit, returns how many times that digit occurs. Otherwise returns a list [count of 1, count of 2, …, count of base-1, count of 0].

["DigitCount", 122, 10, 2]
// ➔ 2

FromDigits(digits: collection) -> integer

FromDigits(digits: collection, base: integer) -> integer

Reconstructs 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), so FromDigits is well-defined for any integer terms.

["FromDigits", [1, 2, 3, 4]]
// ➔ 1234

DigitSum(n: integer) -> integer

DigitSum(n: integer, base: integer) -> integer

Returns the sum of the digits of

n

in the given base (default 10). The sign of

n

is ignored.

["DigitSum", 1234]
// ➔ 10

DivisorSigma(k: integer, n: integer) -> integer

Returns the divisor function

σ_k(n) = \sum_{d \mid n} d^k

over the positive divisors of

n

.

σ_0

counts divisors (like Sigma0) and

σ_1

sums them (like Sigma1). Defined for

n \geq 1

.

See also: Divisor function - Wikipedia

["DivisorSigma", 2, 6]
// ➔ 50

JacobiSymbol(a: integer, n: integer) -> integer

Returns the Jacobi symbol

\left(\frac{a}{n}\right)

for an odd

n > 0

, with value -1, 0, or 1. Undefined when

n

is even or non-positive.

See also: Jacobi symbol - Wikipedia

["JacobiSymbol", 5, 21]
// ➔ 1

LegendreSymbol(a: integer, p: integer) -> integer

Returns the Legendre symbol

\left(\frac{a}{p}\right)

for an odd prime

p

, with value -1, 0, or 1. Undefined when

p

is not an odd prime.

See also: Legendre symbol - Wikipedia

["LegendreSymbol", 3, 7]
// ➔ -1

MultiplicativeOrder(a: integer, n: integer) -> integer

Returns the multiplicative order of

a

modulo

n

: the smallest

k > 0

such that

a^k ≡ 1 \pmod n

. Undefined unless

a

and

n

are coprime.

See also: Multiplicative order - Wikipedia

["MultiplicativeOrder", 2, 7]
// ➔ 3

PrimitiveRoot(n: integer) -> integer

Returns 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^k

, or

2p^k

for an odd prime

p

.

See also: Primitive root modulo n - Wikipedia

["PrimitiveRoot", 7]
// ➔ 3

Eulerian(n: integer, m: integer) -> integer

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

Eulerian numbers count the permutations of the numbers 1 through $n$ that have exactly $m$ ascents (positions where the next number is greater than the previous one). For example, for $n=4$ and $m=2$ , there are 11 such permutations.

See also: Eulerian number - Wikipedia

["Eulerian", 4, 2]
// ➔ 11

Stirling(n: integer, m: integer) -> integer

Returns the Stirling number of the second kind

S(n, m)

, counting the number of ways to partition

n

elements into

m

non-empty subsets.

Stirling numbers of the second kind count how many ways to split a set of $n$ objects into $m$ groups, none empty. For example, with $n=5$ and $m=2$ , there are 15 ways.

See also: Stirling number of the second kind - Wikipedia

["Stirling", 5, 2]
// ➔ 15

NPartition(n: integer) -> integer

Returns the number of integer partitions of

n

.

This function counts how many ways $n$ can be expressed as a sum of positive integers, disregarding order. For example, 5 can be partitioned into 7 distinct sums: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, and 1+1+1+1+1.

See also: Partition function (number theory) - Wikipedia

["NPartition", 5]
// ➔ 7

IsTriangular(n: integer) -> boolean

Returns "True" if

n

is a triangular number.

Triangular numbers count objects arranged in an equilateral triangle. The $k$ th triangular number is $k(k+1)/2$ . For example, 15 is triangular because $5 \times 6 / 2 = 15$ .

See also: Triangular number - Wikipedia

["IsTriangular", 15]
// ➔ "True"

IsSquare(n: integer) -> boolean

Returns "True" if

n

is a perfect square.

A perfect square is an integer that is the square of another integer. For example, 16 is a perfect square since $4^2 = 16$ .

See also: Square number - Wikipedia

["IsSquare", 16]
// ➔ "True"

IsPentagonal(n: integer) -> boolean

Returns "True" if

n

is a pentagonal number.

Pentagonal numbers represent dots forming a pentagon. The $k$ th pentagonal number is given by $k(3k-1)/2$ . For example, 22 is pentagonal because it matches the formula for some integer $k$ .

See also: Pentagonal number - Wikipedia

["IsPentagonal", 22]
// ➔ "True"

IsOctahedral(n: integer) -> boolean

Returns "True" if

n

is an octahedral number.

Octahedral numbers count objects arranged in an octahedron shape. The $k$ th octahedral number is given by $k(2k^2 + 1)/3$ . For example, 19 is not octahedral.

See also: Octahedral number - Wikipedia

["IsOctahedral", 19]
// ➔ "False"

IsCenteredSquare(n: integer) -> boolean

Returns "True" if

n

is a centered square number.

Centered square numbers count dots arranged in a square with a dot in the center. The $k$ th centered square number is $(2k+1)^2$ . For example, 25 is centered square as it equals $5^2$ .

See also: Centered square number - OEIS A001844

["IsCenteredSquare", 25]
// ➔ "True"

IsPerfect(n: integer) -> boolean

Returns "True" if

n

is a perfect number.

A perfect number is one that equals the sum of its positive divisors excluding itself. For example, 28 is perfect since 1 + 2 + 4 + 7 + 14 = 28.

See also: Perfect number - Wikipedia

["IsPerfect", 28]
// ➔ "True"

IsHappy(n: integer) -> boolean

Returns "True" if

n

is a happy number.

A happy number is defined by iterating the sum of the squares of its digits; if this process eventually reaches 1, the number is happy. For example, 19 is happy because: 1²+9²=82; 8²+2²=68; 6²+8²=100; 1²+0²+0²=1.

See also: Happy number - Wikipedia

["IsHappy", 19]
// ➔ "True"

IsAbundant(n: integer) -> boolean

Returns "True" if

n

is an abundant number.

An abundant number is one where the sum of its proper divisors exceeds the number itself. For example, 12 is abundant since 1 + 2 + 3 + 4 + 6 = 16 > 12.

See also: Abundant number - Wikipedia

["IsAbundant", 12]