Number theory¶
This chapter describes functions that are of interest in number theory. These functions typically operate on integers. Some of these functions work quite slowly.
-
IsPrime
(n)¶ test for a prime number
- Param n
integer to test
-
IsComposite
(n)¶ test for a composite number
- Param n
positive integer
-
IsCoprime
(m, n)¶ test if integers are coprime
- Param m
positive integer
- Param n
positive integer
- Param list
list of positive integers
-
IsSquareFree
(n)¶ test for a square-free number
- Param n
positive integer
-
IsPrimePower
(n)¶ test for a power of a prime number
- Param n
integer to test
-
NextPrime
(i)¶ generate a prime following a number
- Param i
integer value
-
IsTwinPrime
(n)¶ test for a twin prime
- Param n
positive integer
-
IsIrregularPrime
(n)¶ test for an irregular prime
- Param n
positive integer
-
IsCarmichaelNumber
(n)¶ test for a Carmichael number
- Param n
positive integer
-
Factors
(x)¶ factorization
- Param x
integer or univariate polynomial
-
IsAmicablePair
(m, n)¶ test for a pair of amicable numbers
- Param m
positive integer
- Param n
positive integer
-
Factor
(x)¶ factorization, in pretty form
- Param x
integer or univariate polynomial
-
Divisors
(n)¶ number of divisors
- Param n
positive integer
-
DivisorsSum
(n)¶ the sum of divisors
- Param n
positive integer
-
ProperDivisors
(n)¶ the number of proper divisors
- Param n
positive integer
-
ProperDivisorsSum
(n)¶ the sum of proper divisors
- Param n
positive integer
-
Moebius
(n)¶ the Moebius function
- Param n
positive integer
-
CatalanNumber
(n)¶ return the
n
-th Catalan Number- Param n
positive integer
-
FermatNumber
(n)¶ return the
n
-th Fermat Number- Param n
positive integer
-
HarmonicNumber
(n)¶ return the
n
-th Harmonic Number- Param n
positive integer
- Param r
positive integer
-
StirlingNumber1
(n, m)¶ return the
n,m
-th Stirling Number of the first kind- Param n
positive integers
- Param m
positive integers
-
StirlingNumber1
(n, m) return the
n,m
-th Stirling Number of the second kind- Param n
positive integer
- Param m
positive integer
-
DivisorsList
(n)¶ the list of divisors
- Param n
positive integer
-
SquareFreeDivisorsList
(n)¶ the list of square-free divisors
- Param n
positive integer
-
MoebiusDivisorsList
(n)¶ the list of divisors and Moebius values
- Param n
positive integer
-
SumForDivisors
(var, n, expr)¶ loop over divisors
- Param var
atom, variable name
- Param n
positive integer
- Param expr
expression depending on
var
-
RamanujanSum
(k, n)¶ compute the Ramanujan’s sum
- Param k
positive integer
- Param n
positive integer
This function computes the Ramanujan’s sum, i.e. the sum of the
n
-th powers of thek
-th primitive roots of the unit:\[\sum_{l=1}^k\frac{\exp(2ln\pi\imath)}{k}\]where \(l\) runs thought the integers between 1 and
k-1
that are coprime to \(l\). The computation is done by using the formula in T. M. Apostol, <i>Introduction to Analytic Theory</i> (Springer-Verlag), Theorem 8.6.Todo
check the definition
-
PAdicExpand
(n, p)¶ p-adic expansion
- Param n
number or polynomial to expand
- Param p
base to expand in
-
IsQuadraticResidue
(m, n)¶ functions related to finite groups
- Param m
integer
- Param n
odd positive integer
-
GaussianFactors
(z)¶ factorization in Gaussian integers
- Param z
Gaussian integer
-
GaussianNorm
(z)¶ norm of a Gaussian integer
- Param z
Gaussian integer
-
IsGaussianUnit
(z)¶ test for a Gaussian unit
- Param z
a Gaussian integer
-
IsGaussianPrime
(z)¶ test for a Gaussian prime
- Param z
a complex or real number
-
GaussianGcd
(z, w)¶ greatest common divisor in Gaussian integers
- Param z
Gaussian integer
- Param w
Gaussian integer