Test whether an integer is a positive prime.

isPrime 2357 == True
isPrime 500 == False

Get all primes in the given range [0..n-1], using the Sieve of Eratosthenes.

primesBelow 4 == [2, 3]
primesBelow 17 == [2, 3, 5, 7, 11, 13]

Return a list of all prime factors for a given positive integer, in ascending order. If the input is less than 2, the empty list is returned.

primeFactors 24 == [2, 2, 2, 3]
primeFactors 767 == [13, 59]
primeFactors 1 == []

Return a list of all prime-exponent pairs for a given positive integer's prime decomposition, with the primes in ascending order. If the input is less than 2, the empty list is returned.

primeExponents 24 == [(2, 3), (5, 2)]                -- 2^3 * 5^2
primeExponents 531764 == [(2, 1), (11, 2), (13, 3)]  -- 2^1 * 11^2 * 13^3
primeExponents 1 == []                               -- empty product

Test whether an integer is even.

isEven 2 == True
isEven 3 == False

Test whether an integer is odd.

isOdd 2 == False
isOdd 3 == True

Test whether one number divides another.

10 `divides` 120 == True
10 `divides` 125 == False

Test whether one number is a multiple of another.

120 `isMultipleOf` 10 == True
125 `isMultipleOf` 10 == False

Get all divisors of a number, in ascending order.

divisors 20 == [1, 2, 4, 5, 10, 20]

Get all proper divisors (i.e., divisors less than the input) of a number, in ascending order.

properDivisors 20 == [1, 2, 4, 5, 10]

Get the number of divisors of a number (counting itself).

Calculate the greatest common divisor of two integers. gcd x 0 and gcd 0 x both return x. Negative arguments are made positive first.

gcd 56 80 == 8

Calculate the least common multiple of two integers. lcm x 0 and lcm 0 x both return 0. Negative arguments are made positive first.

lcm 56 80 == 560

Test whether two integers are coprime.

56 `isCoprimeTo` 80 == False
5 `isCoprimeTo` 8

Compute Euler's totient function φ(n): the number of positive integers 1 <= k <= n for which gcd(n, k) == 1. The input is made positive first.

totient 99 == 60
totient 1450 == 560

Given a and b, compute integers (d, u, v) so that a * u + b * v == d where d == gcd a b. (These are known as Bézout coefficients. If the inputs are both positive, the solution returned satisfies abs u < b // gcd a b and abs v < a // gcd a b.)

extendedGcd 1215 465 == (15, -13, 34)
    -- because gcd 1215 465 == 15 == -13 * 1215 + 34 * 465

Convert a number to a list of digits in the given base. The input number is made positive first.

toBase 2 42 = [1, 0, 1, 0, 1, 0]  -- 42 in binary

Interpret a list of digits as a number in the given base. The input is expected to consist of integers d for which 0 <= d < base.

fromBase 2 [1, 0, 1, 0, 1, 0] = 42

Take the square root of a number. Return NaN (not a number) for negative arguments.

squareRoot 5.76 == 2.4
squareRoot (-1) |> isNaN

Safely take the square root of a number: return Just (squareRoot n) if the input n is nonnegative; otherwise, return Nothing.

squareRoot 5.76 == Just 2.4
squareRoot (-1) == Nothing

Take the square root, rounding down. Return NaN (not a number) for negative arguments.

intSquareRoot 20 == 4
intSquareRoot 25 == 5

Return Just s if the given integer is a square, and s is its square root; otherwise, return Nothing.

exactIntSquareRoot 20 == Nothing
exactIntSquareRoot 25 == Just 5

Test whether a number is a square.

isSquare 20 == False
isSquare 25 == True

Take the cube root of a number.

cubeRoot 15.625 == 2.5

Integer cube root, rounding down.

intCubeRoot 800 == 9
intCubeRoot 1000 == 10

Return Just s if the given integer is a cube, and s is its cube root; otherwise, return Nothing.

exactIntCubeRoot 800 == Nothing
exactIntCubeRoot 1000 == Just 10

Test whether a number is a cube.

isCube 800 == False
isCube 1000 == True

powerMod b e m efficiently calculates b ^ e (modulo m). It assumes b >= 0, e >= 0 and m >= 1.

For example, to compute 4147 ^ 8671 % 1000 efficiently:

powerMod 4147 8671 1000 == 803

Given a number a and a modulus n, return the multiplicative inverse of a modulo n, if it exists. That is: try to return Just b, with 0 <= b < n, so that a * b == 1 modulo n, but return Nothing if no such b exists. (b exists precisely when a and the modulus n are coprime.)

modularInverse 3 11 == Just 4    -- 3 * 4 == 12 == 1 (mod 11)
modularInverse 3 15 == Nothing   -- 3 and 15 aren't coprime

Given a list of residue-modulus pairs [(r1, m1), (r2, m2), ...], solve the system of linear congruences:

x = r1 (mod m1)
x = r2 (mod m2)
...

Let M be the product of all moduli in the list. The Chinese remainder theorem tells us that

• if all of the moduli are pairwise coprime (their gcd is 1), there are infinitely many solutions, all congruent mod M;
• if there is a pair of non-coprime moduli in the list, there is no solution.

The result is a solution Just x with 0 <= x < M in the first case; or Nothing if the system is unsolvable.

chineseRemainder [(10, 11), (4, 12), (12, 13)] == Just 1000
    -- Solution to x = 10 (mod 11), x = 4 (mod 12), x = 12 (mod 13).


chineseRemainder [(2, 3), (4, 6)] == Nothing
    -- 3 and 6 are not coprime, so there is no solution.


chineseRemainder [] == Just 0
    -- The trivial solution, modulo M = 1.