IntegerNumberTheoryFunctions

numtheor.spad line 182 [edit on github]

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, 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: 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).