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
Parameters: n – integer to test
-
IsComposite
(n)¶ test for a composite number
Parameters: n – positive integer
-
IsCoprime
(m, n)¶ test if integers are coprime
Parameters: - m – positive integer
- n – positive integer
- list – list of positive integers
-
IsSquareFree
(n)¶ test for a square-free number
Parameters: n – positive integer
-
IsPrimePower
(n)¶ test for a power of a prime number
Parameters: n – integer to test
-
NextPrime
(i)¶ generate a prime following a number
Parameters: i – integer value
-
IsTwinPrime
(n)¶ test for a twin prime
Parameters: n – positive integer
-
IsIrregularPrime
(n)¶ test for an irregular prime
Parameters: n – positive integer
-
IsCarmichaelNumber
(n)¶ test for a Carmichael number
Parameters: n – positive integer
-
Factors
(x)¶ factorization
Parameters: x – integer or univariate polynomial
-
IsAmicablePair
(m, n)¶ test for a pair of amicable numbers
Parameters: - m – positive integer
- n – positive integer
-
Factor
(x)¶ factorization, in pretty form
Parameters: x – integer or univariate polynomial
-
Divisors
(n)¶ number of divisors
Parameters: n – positive integer
-
DivisorsSum
(n)¶ the sum of divisors
Parameters: n – positive integer
-
ProperDivisors
(n)¶ the number of proper divisors
Parameters: n – positive integer
-
ProperDivisorsSum
(n)¶ the sum of proper divisors
Parameters: n – positive integer
-
Moebius
(n)¶ the Moebius function
Parameters: n – positive integer
-
CatalanNumber
(n)¶ return the
n
-th Catalan NumberParameters: n – positive integer
-
FermatNumber
(n)¶ return the
n
-th Fermat NumberParameters: n – positive integer
-
HarmonicNumber
(n)¶ return the
n
-th Harmonic NumberParameters: - n – positive integer
- r – positive integer
-
StirlingNumber1
(n, m)¶ return the
n,m
-th Stirling Number of the first kindParameters: - n – positive integers
- m – positive integers
-
StirlingNumber1
(n, m) return the
n,m
-th Stirling Number of the second kindParameters: - n – positive integer
- m – positive integer
-
DivisorsList
(n)¶ the list of divisors
Parameters: n – positive integer
-
SquareFreeDivisorsList
(n)¶ the list of square-free divisors
Parameters: n – positive integer
-
MoebiusDivisorsList
(n)¶ the list of divisors and Moebius values
Parameters: n – positive integer
-
SumForDivisors
(var, n, expr)¶ loop over divisors
Parameters: - var – atom, variable name
- n – positive integer
- expr – expression depending on
var
-
RamanujanSum
(k, n)¶ compute the Ramanujan’s sum
Parameters: - k – positive integer
- 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
Parameters: - n – number or polynomial to expand
- p – base to expand in
-
IsQuadraticResidue
(m, n)¶ functions related to finite groups
Parameters: - m – integer
- n – odd positive integer
-
GaussianFactors
(z)¶ factorization in Gaussian integers
Parameters: z – Gaussian integer
-
GaussianNorm
(z)¶ norm of a Gaussian integer
Parameters: z – Gaussian integer
-
IsGaussianUnit
(z)¶ test for a Gaussian unit
Parameters: z – a Gaussian integer
-
IsGaussianPrime
(z)¶ test for a Gaussian prime
Parameters: z – a complex or real number
-
GaussianGcd
(z, w)¶ greatest common divisor in Gaussian integers
Parameters: - z – Gaussian integer
- w – Gaussian integer