numtheor.spad line 182 [edit on github]
This package provides various number theoretic functions on the integers.
bernoulli(n) returns the nth Bernoulli number. this is B(n, 0), where B(n, x) is the nth Bernoulli polynomial.
carmichaelLambda(n) returns exponent of the multiplicative group of integers modulo n, that is smallest positive integer k such that i^k rem n = 1 for all i relatively prime to n.
chineseRemainder(x1, m1, x2, m2) returns w, where w is such that w = x1 mod m1 and w = x2 mod m2. Note: m1 and m2 must be relatively prime.
divisors(n) returns a list of the divisors of n.
euler(n) returns the nth Euler number. This is 2^n E(n, 1/2), where E(n, x) is the nth Euler polynomial.
eulerPhi(n) returns the number of integers between 1 and n (including 1) which are relatively prime to n. This is the Euler phi function phi(n) is also called the totient function.
fibonacci(n) returns the nth Fibonacci number, F[n]. The Fibonacci numbers are defined by F[0] = 0, F[1] = 1 and F[n] = F[n-1] + F[n-2]. The algorithm has running time O(log(n)^3). Reference: Knuth, The Art of Computer Programming Vol 2, Semi-Numerical Algorithms.
harmonic(n) returns the nth harmonic number. This is H[n] = sum(1/k, k=1..n).
jacobi(a, b) returns the Jacobi symbol J(a/b). When b is odd, J(a/b) = product(L(a/p) for p in factor b ). Note: by convention, 0 is returned if gcd(a, b) ~= 1. Iterative O(log(b)^2) version coded by Michael Monagan June 1987.
legendre(a, p) returns the Legendre symbol L(a/p). L(a/p) = (-1)^((p-1)/2) mod p (p prime), which is 0 if a is 0, 1 if a is a quadratic residue mod p and -1 otherwise. Note: because the primality test is expensive, if it is known that p is prime then use jacobi(a, p).
moebiusMu(n) returns the Moebius function mu(n). mu(n) is either -1, 0 or 1 as follows: mu(n) = 0 if n is divisible by a square > 1, mu(n) = (-1)^k if n is square-free and has k distinct prime divisors.
numberOfDivisors(n) returns the number of integers between 1 and n (inclusive) which divide n. The number of divisors of n is often denoted by tau(n).
sumOfDivisors(n) returns the sum of the integers between 1 and n (inclusive) which divide n. The sum of the divisors of n is often denoted by sigma(n).
sumOfKthPowerDivisors(n, k) returns the sum of the kth powers of the integers between 1 and n (inclusive) which divide n. the sum of the kth powers of the divisors of n is often denoted by sigma_k(n).