Arithmetic Functions#
Each of the functions in this section may take an integer or the factorization of that integer.
- CarmichaelLambda(n): RngIntElt -> RngIntElt#
- CarmichaelLambda(Q): RngIntEltFact -> RngIntElt#
- CarmichaelLambda(Q): [Tup] -> RngIntElt#
The Carmichael function \(\lambda(n)\); its value equals the exponent of \({({{\mathbb{Z}}/n{\mathbb{Z}}})^*}\).
- DickmanRho(u): FldReElt -> FldReElt#
Computes \(\rho(u)\) where \(\rho\) is Dickman’s rho function.
- FactoredCarmichaelLambda(n): RngIntElt -> RngIntEltFact#
- FactoredCarmichaelLambda(Q): RngIntEltFact -> RngIntEltFact#
- FactoredCarmichaelLambda(Q): [Tup] -> RngIntEltFact#
The Carmichael function \(\lambda(n)\), returned as a factorization sequence.
- DivisorSigma(i, n): RngIntElt, RngIntElt -> RngIntElt#
- DivisorSigma(i, Q): RngIntElt, RngIntEltFact -> RngIntElt#
The divisor function \(\sigma_i(n)=\sum_{d\vert n}d^i\) for integer \(n\) and small non-negative integer \(i\).
- NumberOfDivisors(n): RngIntElt -> RngIntElt#
- NumberOfDivisors(Q): RngIntEltFact -> RngIntElt#
The number of divisors of the positive integer \(n\). This is a special case of
DivisorSigma.
- SumOfDivisors(n): RngIntElt -> RngIntElt#
- SumOfDivisors(Q): RngIntEltFact -> RngIntElt#
The sum of the divisors of the positive integer \(n\). This is a special case of
DivisorSigma.
- EulerPhi(n): RngIntElt -> RngIntElt#
- EulerPhi(Q): RngIntEltFact -> RngIntElt#
- EulerPhi(Q): [Tup] -> RngIntElt#
The Euler totient function \(\phi(n)\); its value equals the order of \({({{\mathbb{Z}}/n{\mathbb{Z}}})^*}\).
- FactoredEulerPhi(n): RngIntElt -> RngIntEltFact#
- FactoredEulerPhi(Q): RngIntEltFact -> RngIntEltFact#
- FactoredEulerPhi(Q): [Tup] -> RngIntEltFact#
The Euler totient function \(\phi(n)\), returned as a factorization sequence.
- EulerPhiInverse(m): RngIntElt -> RngIntElt#
- EulerPhiInverse(Q): RngIntEltFact -> RngIntElt#
The inverse of the Euler totient function \(\phi(n)\); that is, the sorted sequence of all integers \(n\) such that \(\phi(n)=m\).
- FactoredEulerPhiInverse(n): RngIntElt -> RngIntEltFact#
- FactoredEulerPhiInverse(Q): RngIntEltFact -> RngIntEltFact#
The factored inverse of the Euler totient function \(\phi(n)\); that is, the sorted sequence of the factorizations of all integers \(n\) such that \(\phi(n)=m\).
- LegendreSymbol(n, m): RngIntElt, RngIntElt -> RngIntElt#
The Legendre symbol \(\left({n\over m}\right)\): for prime \(m\) this checks whether or not \(n\) is a quadratic residue modulo \(m\). The function returns \(0\) if \(m\) divides \(n\), \(-1\) if \(n\) is not a quadratic residue, and \(1\) if \(n\) is a quadratic residue modulo \(m\). A fast probabilistic primality test is performed on \(m\). If \(m\) fails the test (and is therefore composite), an error results; if it passes the test the Jacobi symbol is computed.
- JacobiSymbol(n, m): RngIntElt, RngIntElt -> RngIntElt#
The Jacobi symbol \(\left({n\over m}\right)\). For odd \(m > 1\) this is defined (but not calculated!) as the product of the Legendre symbols \(\left({n\over p_i}\right)\), where the product is taken over all primes \(p_i\) dividing \(m\) including multiplicities. Quadratic reciprocity is used to calculate this symbol, which has the values \(-1\), \(0\) or \(1\).
- KroneckerSymbol(n, m): RngIntElt, RngIntElt -> RngIntElt#
The Kronecker symbol \(\left({n\over m}\right)\). This is the extension of the Jacobi symbol to all integers \(m\), by multiplicativity, and by defining \(\left({n\over 2}\right)=(-1)^{(n^2-1)/8}\) for odd \(n\) (and \(0\) for even \(n\)) and \(\left({n\over -1}\right)=\pm1\) according to the sign of \(n\) for \(n\neq 0\) (and \(1\) for \(n = 0\)).
- MoebiusMu(n): RngIntElt -> RngIntElt#
- MoebiusMu(Q): RngIntEltFact -> RngIntElt#
The Möbius function \(\mu(n)\). This is a multiplicative function characterized by \(\mu(1)=1\), \(\mu(p)=-1\), and \(\mu(p^k)=0\) for \(k \geq 2\), where \(p\) is a prime number.
- Example: Amicable (ex-233f46)#
A pair of positive integers \((m, n)\) is called amicable if the sum of the proper divisors (that is: excluding \(m\) itself) of \(m\) equals \(n\), and vice versa. The following function finds such pairs. Note that it also finds perfect numbers: amicable pairs of the form \((m, m)\).
> d := func< m | DivisorSigma(1, m)-m >; > z := func< m | d(d(m)) eq m >; > for m := 2 to 10000 do > if z(m) then > m, d(m); > end if; > end for; 6 6 28 28 220 284 284 220 496 496 1184 1210 1210 1184 2620 2924 2924 2620 5020 5564 5564 5020 6232 6368 6368 6232 8128 8128