IntegerNumberTheoryFunctionsΒΆ

numtheor.spad line 182

This package provides various number theoretic functions on the integers.

bernoulli: Integer -> Fraction Integer
bernoulli(n) returns the nth Bernoulli number. this is B(n, 0), where B(n, x) is the nth Bernoulli polynomial.
carmichaelLambda: Integer -> Integer
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: (Integer, Integer, Integer, Integer) -> Integer
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: Integer -> List Integer
divisors(n) returns a list of the divisors of n.
euler: Integer -> Integer
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: Integer -> Integer
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: Integer -> Integer
fibonacci(n) returns the nth Fibonacci number. the Fibonacci numbers F[n] are defined by F[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: Integer -> Fraction Integer
harmonic(n) returns the nth harmonic number. This is H[n] = sum(1/k, k=1..n).
jacobi: (Integer, Integer) -> Integer
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: (Integer, Integer) -> Integer
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: Integer -> Integer
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: Integer -> Integer
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: Integer -> Integer
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: (Integer, NonNegativeInteger) -> Integer
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).