factorial
n! -- the product of every whole number from 1 to n. Works up to n = 1000 (the same for n!).
n(number) -- a non-negative whole number
Number Theory
nCr
The number of ways to choose r items from n, order not mattering (n choose r). Works while k * d^2 is at most 1800000000, where k is the smaller of r and n - r and d the digits of the answer: nCr(3400, 1700) and nCr(10^12, 260) are inside it.
n(number) -- total itemsr(number) -- items chosen
nPr
The number of ways to arrange r items from n, order mattering (n permute r). Works while r * d^2 is at most 5500000000, where d is the digits of the answer: nPr(1650, 825) and nPr(10^12, 330) are inside it.
n(number) -- total itemsr(number) -- items arranged
catalan
The nth Catalan number -- counts things like balanced bracket sequences and binary tree shapes. Works up to n = 1700.
n(number) -- index, starting at 0
fibonacci
The nth Fibonacci number (0, 1, 1, 2, 3, 5, 8, ...). Works up to n = 4500.
n(number) -- a non-negative index; fibonacci(0) = 0
gcd
The greatest common divisor of a and b. Works at any size (past 10^38 through big integers).
a(number) --b(number) --
lcm
The least common multiple of a and b. Works at any size (past 10^38 through big integers).
a(number) --b(number) --
divides
True if a evenly divides b (b is a multiple of a).
a(number) -- the divisorb(number) -- the number being divided
quotient
The quotient q of the division algorithm a = b*q + r with 0 <= r < |b|, exact at any size. For a positive b it is floor(a/b); quotient(-17, 5) is -4 and quotient(17, -5) is -3.
a(integer) -- the number divided; the index of a sum may stand in itb(integer) -- not 0
remainder
The remainder r of the division algorithm a = b*q + r with 0 <= r < |b|: never negative, exact at any size. The same as a % b when b is positive; remainder(-17, 5) is 3 and remainder(17, -5) is 2 (17 % -5 is -3). Given a list where a number goes, it works item by item (as do modPow and the other functions of whole numbers), and it works inside a rule: g(n) = remainder(n, 4) + 1.
a(integer) --b(integer) -- not 0
mod
a mod b, the same as a % b: the remainder with the sign of b (floored), so mod(23, 4) is 3 and mod(-7, 3) is 2. A calculator function, so it works in any expression and in a rule; with a list it works item by item.
a(number) --b(number) -- not 0
divmod
Quotient and remainder together, as {quotient, remainder}, from the division algorithm a = b*q + r with 0 <= r < |b|. Read them with r.quotient and r.remainder.
a(integer) --b(integer) -- not 0
sumDivisors
The sum of all positive divisors of n, including 1 and n itself.
n(number) --
countDivisors
How many positive divisors n has, including 1 and n itself.
n(number) --
mulmod
(a * b) mod m, after first reducing a and b modulo m so their full product is never formed. Works at any size (past 10^38 through big integers).
a(number) --b(number) --m(number) -- the modulus
modPow
base^exp mod m, computed efficiently (fast exponentiation) without ever forming the full power. Works at any size (past 10^38 through big integers).
base(number) --exp(number) --m(number) -- the modulus
truthTable
The truth table of a statement in quotes: variables (the letters in alphabetical order), rows (every assignment, all true first), result. Statements read not ! ~, and &, or |, xor, implies ->, iff <->, tightest first; implies groups from the right. Up to 16 letters.
statement(text) --
isTautology
Whether a statement in quotes is true under every assignment.
statement(text) --
logicallyEquivalent
Whether two statements in quotes have the same value under every assignment.
a(text) --b(text) --
stirling2
The Stirling number of the second kind S(n, k): ways to split n things into k non-empty groups.
n(number) --k(number) --
stirling1
The unsigned Stirling number of the first kind c(n, k): permutations of n things with k cycles. The signed number is (-1)^(n-k) times this.
n(number) --k(number) --
bellNumber
The Bell number B(n): all ways to split n things into groups.
n(number) --
partitionCount
p(n): how many ways n is written as a sum of positive whole numbers, order ignored.
n(number) --
inclusionExclusion
The size of a union from S1, S2, ...: the sums of the sizes of the intersections of 1, 2, ... sets. S1 - S2 + S3 - ...
sums(array) --
recurrenceTerm
Term n of a(n) = c1 a(n-1) + ... + ck a(n-k), counted from a(0), exact. Works while n * d^2 is at most 1700000000, where d is n * log10(g) and g the sum of the coefficients' sizes (at least 2; a non-whole coefficient c counts as |c| + 1/|c|): the Fibonacci coefficients reach n = 2650.
coefficients(array) -- c1, ..., ckinitial(array) -- a(0), ..., a(k-1)n(number) --
solveRecurrence
The closed form in n of the same recurrence, from its characteristic roots, exact, repeated roots included. Refused when a root is not real or cannot be written exactly, or is 0.
coefficients(array) -- c1, ..., ckinitial(array) -- a(0), ..., a(k-1)
eulerPhi
Euler's phi: how many of 1..n are coprime to n, from the prime factorization, so any n of up to 38 digits: eulerPhi(2^61 - 1) is 2^61 - 2.
n(number) -- a positive whole number
mobius
The Mobius function: 0 if a square above 1 divides n, otherwise 1 or -1 for an even or odd number of prime factors.
n(number) -- a positive whole number
multiplicativeOrder
The order of a mod n: the least k >= 1 with a^k = 1 (mod n). Says so when a and n share a factor, as there is then none.
a(number) --n(number) --
primitiveRoot
The smallest primitive root of n, or a sentence saying n has none. n up to 10 million.
n(number) --
primitiveRoots
Every primitive root of n, smallest first; an empty list when n has none.
n(number) --
discreteLog
The discrete logarithm, or index: the least x >= 0 with a^x = b (mod n), or a sentence if no power gives b. It goes through the powers in turn, so n is limited to 10 million.
a(number) --b(number) --n(number) --
legendreSymbol
The Legendre symbol (a/p) for an odd prime p: 1 if a is a nonzero square mod p, -1 if not, 0 if p divides a. (legendre is another function: the Legendre polynomials.)
a(number) --p(number) -- an odd prime
jacobiSymbol
The Jacobi symbol (a/n) for an odd positive n. For a composite n, 1 does not mean that a is a square mod n. (jacobi is another function.)
a(number) --n(number) -- odd and positive
chineseRemainder
Solves x = residues[i] (mod moduli[i]) together, the moduli need not be coprime. Gives x (the least >= 0) and modulus, or a sentence when the congruences conflict.
residues(array) --moduli(array) --
diophantine
All integer solutions of a x + b y = c: x = x0 + dx t, y = y0 + dy t for whole t (fields x0, y0, dx, dy; x0 the least x >= 0 when b is not 0), or a sentence when there are none.
a(number) --b(number) --c(number) --
continuedFraction
The terms [a0, a1, ...] of the continued fraction of a fraction.
x(number) -- a fraction or whole number
continuedFractionSqrt
The continued fraction of sqrt(n): whole and the repeating period (empty for a perfect square).
n(number) --
convergents
The convergents of a continued fraction given by its terms, as exact fractions.
terms(array) --
pell
The fundamental (least) solution x, y of Pell's equation x^2 - d y^2 = 1, d not a perfect square. An error if it is too large for the engine's whole numbers.
d(number) --
primitiveTriples
Every primitive Pythagorean triple with c up to a limit, as records a, b, c, smallest c first. Works up to a limit of 1500000.
limit(number) --
sumOfTwoSquares
Every way of writing n as a^2 + b^2 with 0 <= a <= b, as records a, b; an empty list when there is none.
n(number) --
modInv
The modular inverse of a mod m -- the value x where (a*x) mod m == 1. Returns explanatory text ('no inverse exists') when a and m share a common factor.
a(number) --m(number) -- the modulus
solveCongruence
Finds one solution to the linear congruence a*x = b (mod m). Returns explanatory text ('no solution exists') when none exists.
a(number) --b(number) --m(number) -- the modulus
fermatCheck
Checks whether a^(p-1) = 1 (mod p). A false result proves p is composite; a true result does not prove p is prime.
a(number) -- the base to test withp(number) -- the candidate prime
isPrime
True if n is a prime number: trial division up to a million, then the deterministic Miller-Rabin test (exact for every n below 3.3*10^24, a probable-prime test with 13 witnesses above). Works at any size (past 10^38 through big integers). Inside a sum it counts: sum(isPrime(quotient(10^k - 1, 9)), k, 2, 25) is 3, the repunit primes of up to 25 ones.
n(number) -- a whole number of any size
nextPrime
The smallest prime strictly greater than n, by the same test as isPrime. Works at any size (past 10^38 through big integers).
n(number) -- a whole number of any size
triangular
The nth triangular number, 1 + 2 + ... + n. Works at any size (past 10^38 through big integers).
n(number) --
isTriangular
True if n is a triangular number (1, 3, 6, 10, 15, ...).
n(number) --
piNaive
pi(n) -- the count of primes less than or equal to n, computed by direct trial (simple, fine for small n).
n(number) --
piSieve
pi(n) -- the count of primes less than or equal to n, computed via a sieve (fast for larger n).
n(number) --
nthPrime
The nth prime number (nthPrime(1) = 2, nthPrime(2) = 3, ...).
n(number) -- 1-indexed position
isSquareFree
True if no prime's square divides n -- n has no repeated prime factor. Any n of up to 38 digits: isSquareFree(2^64 + 1) is true.
n(number) -- a whole number of up to 38 digits
isPerfectPower
True if positive integer n can be written as m^k for integers m and k >= 2 (e.g. 8 = 2^3, 9 = 3^2).
n(number) -- a whole number of up to 38 digits
extendedGcd
x, y and gcd(a, b) with a*x + b*y = gcd(a, b) (extended Euclidean algorithm).
a(integer) --b(integer) --
twinPrimes
All twin prime pairs (p, p + 2) up to n. Works up to n = 20000000.
n(integer) --
cousinPrimes
All cousin prime pairs (p, p + 4), both prime, up to n. Works up to n = 20000000.
n(integer) --
sexyPrimes
All sexy prime pairs (p, p + 6), both prime, up to n. Works up to n = 20000000.
n(integer) --
primePairs
All pairs (p, p + d) with both prime, up to n.
d(integer) --n(integer) --
consecutivePrimePairs
Consecutive primes exactly gap apart, up to n (prime gaps). Works up to n = 30000000.
gap(integer) --n(integer) --
maxPrimeGap
The largest gap between consecutive primes up to n.
n(integer) --
isMersennePrime
True if 2^p - 1 is prime (Lucas-Lehmer). Works up to p = 8800.
p(integer) --
primeWithDigits
The smallest prime with the given number of digits (10^(d-1) rounded up to a prime). Works up to 200 digits.
digits(integer) --
digitCount
The number of decimal digits of a whole number of any size.
n(integer) --
toBase
A whole number written in base 2 to 36, as text.
n(integer) --base(integer) -- 2 to 36
fromBase
The number a base-2..36 string spells.
text(string) -- quoted, e.g. "ff"base(integer) -- 2 to 36
toHex
A whole number in hexadecimal.
n(integer) --
fromHex
The number a hexadecimal string spells.
text(string) -- quoted, e.g. "ff"