use math/integergcd ( a b → n )Returns the greatest common divisor of a and b, that is, the largest number that is a factor of both.
lcm ( a b → n )Returns the least common multiple of a and b, that is, the smallest number that divides evenly by both a and b.
See Also: gcd
%** ( b e m → x )Integer power (b**e) modulo m.
Handles error cases as follows:
e < 0 and b == 0.m is <= 0log_ ( a b → l ).
root_ ( x n → r )Computes floored integer root n of x (e.g. n = 2 gives sqrt, n=3 gives cbrt).
That is, computes largest integer r such that r**n <= x.
n must be a positive integer.
Returns undefined if result could not be computed.
modinv ( a b → i )Integer modular inverse 1/a modulo b. Edge cases: if a is 0 or m <= 0, returns 0.
log2_ ( x → y )Integer log base 2.
sqrt_ ( x → y )Integer square root.
!% ( n m → x )Factorial of n modulo m. Returns undefined on overflow.
NOTE: can be slow for n > 4096 especially if m only has large prime factors.
prime? ( n → p )Returns true if n is prime. For n < 1.5 million, uses brute-force divisibilty testing;
after that, uses the Miller-Rabin test,
which, being probablilistic, may be incorrect, especially for n > 2^64.
nextprime ( n → m )Returns the smallest prime number greater than n.
prevprime ( n → m )Returns the largest prime number less than n, or undefined if there is no smaller prime.
ppow ( n → e )Returns the highest possible exponent if the number is a perfect power (>= 2), or 1 if not.
E.g. if n is 8, returns 3 because 2^3 is 8, if n is 10 returns 1.
smallestfactor ( n → f )Returns smallest prime factor of n, or 0 if factorizing it takes too long.
Can usually find the product of two 32-bit primes relatively quickly.
NOTE: factorization is most difficult when n is a product of two different large primes.
pfactors ( n → a )Returns an array of all the prime factors of n, repeating factors as many times as necessary.
E.g. if n is 4294967296 (2^32), returns a list containg 32 2’s. Returns an empty list if the number could not be factored.
See Also: primepoly
primepoly ( n → a )Returns an array of pairs, where the first element of each pair os the prime factor of n and the second
is its exponent.
E.g. if n is 324 (2^2*3^4), returns [ [2, 2], [3, 4] ]. Returns an empty list if the number could not be factored.
See Also: pfactors
multiplicativeorder ( a m → r )Returns smallest positive integer r such that a**r = 1 (mod m).
This is a special case of discretelog, where b == 1, but computed in a different way.
.
discretelog ( a b m → r )Computes r such that a**r = b (mod m).
This problem is of similar computational difficulty as integer factorization.
If b is 1, computes multiplicativeorder: r such that a**r = 1 (mod m).
Returns undefined if it’s known there is no result, -1 if it failed to compute (took too long).
totient ( n → x )Euler’s totient function: counts amount of positive integers <= n that are relatively prime to n.
residue ( n p → r )Tonelli–Shanks algorithm for quadratic residue (square root of n modulo p). p must be prime.
nCk ( n k → x )The binomial coefficient, also known as n-choose-k or combinations.
docs@04547c7