Function whose domain is the positive integers
This article uses technical mathematical notation for logarithms. All instances of
log(x ) without a subscript base should be interpreted as a
natural logarithm , also commonly written as
ln(x ) or
loge x ) .
Innumber theory , anarithmetic ,arithmetical , ornumber-theoretic function [ 1] [ 2] function whosedomain is the set ofpositive integers and whose range is asubset of thecomplex numbers .[ 3] [ 4] [ 5] n ".[ 6] prime-counting functions . This article provides links to functions of both classes.
An example of an arithmetic function is thedivisor function whose value at a positive integern is equal to the number of divisors ofn .
Arithmetic functions are often extremely irregular (seetable ), but some of them have series expansions in terms ofRamanujan's sum .
Multiplicative and additive functions [ edit ] An arithmetic functiona is
Two whole numbersm andn are calledcoprime if theirgreatest common divisor is 1, that is, if there is noprime number that divides both of them.
Then an arithmetic functiona is
additive a (mn ) =a (m ) +a (n ) for all coprime natural numbersm andn ;multiplicative a (1) = 1 anda (mn ) =a (m )a (n ) for all coprime natural numbersm andn .In this article,∑ p f ( p ) {\textstyle \sum _{p}f(p)} ∏ p f ( p ) {\textstyle \prod _{p}f(p)} prime numbers :∑ p f ( p ) = f ( 2 ) + f ( 3 ) + f ( 5 ) + ⋯ {\displaystyle \sum _{p}f(p)=f(2)+f(3)+f(5)+\cdots } ∏ p f ( p ) = f ( 2 ) f ( 3 ) f ( 5 ) ⋯ . {\displaystyle \prod _{p}f(p)=f(2)f(3)f(5)\cdots .} ∑ p k f ( p k ) {\textstyle \sum _{p^{k}}f(p^{k})} ∏ p k f ( p k ) {\textstyle \prod _{p^{k}}f(p^{k})} prime powers with strictly positive exponent (sok = 0∑ p k f ( p k ) = ∑ p ∑ k > 0 f ( p k ) = f ( 2 ) + f ( 3 ) + f ( 4 ) + f ( 5 ) + f ( 7 ) + f ( 8 ) + f ( 9 ) + ⋯ . {\displaystyle \sum _{p^{k}}f(p^{k})=\sum _{p}\sum _{k>0}f(p^{k})=f(2)+f(3)+f(4)+f(5)+f(7)+f(8)+f(9)+\cdots .}
The notations∑ d ∣ n f ( d ) {\textstyle \sum _{d\mid n}f(d)} ∏ d ∣ n f ( d ) {\textstyle \prod _{d\mid n}f(d)} n , including 1 andn . For example, ifn = 12∏ d ∣ 12 f ( d ) = f ( 1 ) f ( 2 ) f ( 3 ) f ( 4 ) f ( 6 ) f ( 12 ) . {\displaystyle \prod _{d\mid 12}f(d)=f(1)f(2)f(3)f(4)f(6)f(12).}
The notations can be combined:∑ p ∣ n f ( p ) {\textstyle \sum _{p\mid n}f(p)} ∏ p ∣ n f ( p ) {\textstyle \prod _{p\mid n}f(p)} n . For example, ifn = 18, then∑ p ∣ 18 f ( p ) = f ( 2 ) + f ( 3 ) , {\displaystyle \sum _{p\mid 18}f(p)=f(2)+f(3),} ∑ p k ∣ n f ( p k ) {\textstyle \sum _{p^{k}\mid n}f(p^{k})} ∏ p k ∣ n f ( p k ) {\textstyle \prod _{p^{k}\mid n}f(p^{k})} n . For example, ifn = 24, then∏ p k ∣ 24 f ( p k ) = f ( 2 ) f ( 3 ) f ( 4 ) f ( 8 ) . {\displaystyle \prod _{p^{k}\mid 24}f(p^{k})=f(2)f(3)f(4)f(8).}
n ),ω (n ),ν p n ) – prime power decomposition[ edit ] Thefundamental theorem of arithmetic states that any positive integern can be represented uniquely as a product of powers of primes:n = p 1 a 1 ⋯ p k a k {\displaystyle n=p_{1}^{a_{1}}\cdots p_{k}^{a_{k}}} p 1 <p 2 < ... <p k aj are positive integers. (1 is given by the empty product.)
It is often convenient to write this as an infinite product over all the primes, where all but a finite number have a zero exponent. Define thep -adic valuationνp n ) to be the exponent of the highest power of the primep that dividesn . That is, ifp is one of thep i ν p n ) =a i n = ∏ p p ν p ( n ) . {\displaystyle n=\prod _{p}p^{\nu _{p}(n)}.}
In terms of the above theprime omega functions ω and Ω are defined by
ω (n ) =k ,
Ω(n ) =a 1 +a 2 + ... +a k
To avoid repetition, formulas for the functions listed in this article are, whenever possible, given in terms ofn and the correspondingp i a i ω , and Ω.
Multiplicative functions [ edit ] σ k n ),τ (n ),d (n ) – divisor sums[ edit ] σk n ) k th powers of the positive divisors ofn , including 1 andn , wherek is a complex number.
σ 1 (n )n , is usually denoted byσ (n )
Since a positive number to the zero power is one,σ 0 (n )n ; it is usually denoted byd (n )τ (n )Teiler = divisors).
σ k ( n ) = ∏ i = 1 ω ( n ) p i ( a i + 1 ) k − 1 p i k − 1 = ∏ i = 1 ω ( n ) ( 1 + p i k + p i 2 k + ⋯ + p i a i k ) . {\displaystyle \sigma _{k}(n)=\prod _{i=1}^{\omega (n)}{\frac {p_{i}^{(a_{i}+1)k}-1}{p_{i}^{k}-1}}=\prod _{i=1}^{\omega (n)}\left(1+p_{i}^{k}+p_{i}^{2k}+\cdots +p_{i}^{a_{i}k}\right).}
Settingk = 0 in the second product givesτ ( n ) = d ( n ) = ( 1 + a 1 ) ( 1 + a 2 ) ⋯ ( 1 + a ω ( n ) ) . {\displaystyle \tau (n)=d(n)=(1+a_{1})(1+a_{2})\cdots (1+a_{\omega (n)}).}
φ (n ) – Euler totient function[ edit ] φ (n )n that are coprime ton .φ ( n ) = n ∏ p ∣ n ( 1 − 1 p ) = n ( p 1 − 1 p 1 ) ( p 2 − 1 p 2 ) ⋯ ( p ω ( n ) − 1 p ω ( n ) ) . {\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)=n\left({\frac {p_{1}-1}{p_{1}}}\right)\left({\frac {p_{2}-1}{p_{2}}}\right)\cdots \left({\frac {p_{\omega (n)}-1}{p_{\omega (n)}}}\right).}
J k n ) – Jordan totient function[ edit ] J k n )k -tuples of positive integers all less than or equal ton that form a coprime (k + 1)-tuple together withn . It is a generalization of Euler's totient,φ (n ) =J 1 (n )J k ( n ) = n k ∏ p ∣ n ( 1 − 1 p k ) = n k ( p 1 k − 1 p 1 k ) ( p 2 k − 1 p 2 k ) ⋯ ( p ω ( n ) k − 1 p ω ( n ) k ) . {\displaystyle J_{k}(n)=n^{k}\prod _{p\mid n}\left(1-{\frac {1}{p^{k}}}\right)=n^{k}\left({\frac {p_{1}^{k}-1}{p_{1}^{k}}}\right)\left({\frac {p_{2}^{k}-1}{p_{2}^{k}}}\right)\cdots \left({\frac {p_{\omega (n)}^{k}-1}{p_{\omega (n)}^{k}}}\right).}
μ (n ) – Möbius function[ edit ] μ (n )Möbius inversion formula. See§ Dirichlet convolution μ ( n ) = { ( − 1 ) ω ( n ) = ( − 1 ) Ω ( n ) if ω ( n ) = Ω ( n ) 0 if ω ( n ) ≠ Ω ( n ) . {\displaystyle \mu (n)={\begin{cases}(-1)^{\omega (n)}=(-1)^{\Omega (n)}&{\text{if }}\;\omega (n)=\Omega (n)\\0&{\text{if }}\;\omega (n)\neq \Omega (n).\end{cases}}}
This implies thatμ (1) = 1. (Because Ω(1) =ω (1) = 0.)
τ (n ) – Ramanujan tau function[ edit ] τ (n )generating function identity:∑ n ≥ 1 τ ( n ) q n = q ∏ n ≥ 1 ( 1 − q n ) 24 . {\displaystyle \sum _{n\geq 1}\tau (n)q^{n}=q\prod _{n\geq 1}(1-q^{n})^{24}.}
Although it is hard to say exactly what "arithmetical property ofn " it "expresses",[ 7] τ (n ) is (2π )−12 times then th Fourier coefficient in theq -expansionmodular discriminant function)[ 8] σ k n ) andr k n ) functions (because these are also coefficients in the expansion ofmodular forms ).
c q n ) – Ramanujan's sum[ edit ] c q n )n th powers of the primitiveq throots of unity :c q ( n ) = ∑ gcd ( a , q ) = 1 1 ≤ a ≤ q e 2 π i a q n . {\displaystyle c_{q}(n)=\sum _{\stackrel {1\leq a\leq q}{\gcd(a,q)=1}}e^{2\pi i{\tfrac {a}{q}}n}.}
Even though it is defined as a sum of complex numbers (irrational for most values ofq ), it is an integer. For a fixed value ofn it is multiplicative inq :
Ifq andr are coprime , thenc q ( n ) c r ( n ) = c q r ( n ) . {\displaystyle c_{q}(n)c_{r}(n)=c_{qr}(n).} ψ (n ) – Dedekind psi function[ edit ] TheDedekind psi function , used in the theory ofmodular functions , is defined by the formulaψ ( n ) = n ∏ p | n ( 1 + 1 p ) . {\displaystyle \psi (n)=n\prod _{p|n}\left(1+{\frac {1}{p}}\right).}
Completely multiplicative functions [ edit ] λ (n ) – Liouville function[ edit ] λ (n )λ ( n ) = ( − 1 ) Ω ( n ) . {\displaystyle \lambda (n)=(-1)^{\Omega (n)}.}
AllDirichlet characters χ (n )
Theprincipal character (modn ) is denoted byχ 0 (a ) (orχ 1 (a )). It is defined asχ 0 ( a ) = { 1 if gcd ( a , n ) = 1 , 0 if gcd ( a , n ) ≠ 1. {\displaystyle \chi _{0}(a)={\begin{cases}1&{\text{if }}\gcd(a,n)=1,\\0&{\text{if }}\gcd(a,n)\neq 1.\end{cases}}}
Thequadratic character (modn ) is denoted by theJacobi symbol for oddn (it is not defined for evenn ):( a n ) = ( a p 1 ) a 1 ( a p 2 ) a 2 ⋯ ( a p ω ( n ) ) a ω ( n ) . {\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{a_{1}}\left({\frac {a}{p_{2}}}\right)^{a_{2}}\cdots \left({\frac {a}{p_{\omega (n)}}}\right)^{a_{\omega (n)}}.}
In this formula( a p ) {\displaystyle ({\tfrac {a}{p}})} Legendre symbol , defined for all integersa and all odd primesp by( a p ) = { 0 if a ≡ 0 ( mod p ) , + 1 if a ≢ 0 ( mod p ) and for some integer x , a ≡ x 2 ( mod p ) − 1 if there is no such x . {\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0&{\text{if }}a\equiv 0{\pmod {p}},\\+1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and for some integer }}x,\;a\equiv x^{2}{\pmod {p}}\\-1&{\text{if there is no such }}x.\end{cases}}}
Following the normal convention for the empty product,( a 1 ) = 1. {\displaystyle \left({\frac {a}{1}}\right)=1.}
ω (n ) – distinct prime divisors[ edit ] ω (n )n , is additive (seePrime omega function
Completely additive functions [ edit ] n ) – prime divisors[ edit ] Ω(n ) n counted with multiplicities, is completely additive (seePrime omega function ).
For a fixed primep ,ν p n )p dividingn , is completely additive.
Logarithmic derivative [ edit ] ld ( n ) = D ( n ) n = ∑ p prime p ∣ n v p ( n ) p {\displaystyle \operatorname {ld} (n)={\frac {D(n)}{n}}=\sum _{\stackrel {p\mid n}{p{\text{ prime}}}}{\frac {v_{p}(n)}{p}}} D ( n ) {\displaystyle D(n)} arithmetic derivative .
Neither multiplicative nor additive [ edit ] π (x ), Π(x ),ϑ (x ),ψ (x ) – prime-counting functions[ edit ] These important functions (which are not arithmetic functions) are defined for non-negative real arguments, and are used in the various statements and proofs of theprime number theorem . They are summation functions (see the main section just below) of arithmetic functions which are neither multiplicative nor additive.
π (x ), theprime-counting function , is the number of primes not exceedingx . It is the summation function of thecharacteristic function of the prime numbers.π ( x ) = ∑ p ≤ x 1 {\displaystyle \pi (x)=\sum _{p\leq x}1}
A related function counts prime powers with weight 1 for primes, 1/2 for their squares, 1/3 for cubes, etc. It is the summation function of the arithmetic function which takes the value 1/k on integers which are thek th power of some prime number, and the value 0 on other integers.Π ( x ) = ∑ p k ≤ x 1 k . {\displaystyle \Pi (x)=\sum _{p^{k}\leq x}{\frac {1}{k}}.}
ϑ (x ) andψ (x ), theChebyshev functions , are defined as sums of the natural logarithms of the primes not exceedingx .ϑ ( x ) = ∑ p ≤ x log p , {\displaystyle \vartheta (x)=\sum _{p\leq x}\log p,} ψ ( x ) = ∑ p k ≤ x log p . {\displaystyle \psi (x)=\sum _{p^{k}\leq x}\log p.}
The second Chebyshev functionψ (x ) is the summation function of the von Mangoldt function just below.
n ) – von Mangoldt function[ edit ] Λ(n ) n is a prime powerp k p :Λ ( n ) = { log p if n = 2 , 3 , 4 , 5 , 7 , 8 , 9 , 11 , 13 , 16 , … = p k is a prime power 0 if n = 1 , 6 , 10 , 12 , 14 , 15 , 18 , 20 , 21 , … is not a prime power . {\displaystyle \Lambda (n)={\begin{cases}\log p&{\text{if }}n=2,3,4,5,7,8,9,11,13,16,\ldots =p^{k}{\text{ is a prime power}}\\0&{\text{if }}n=1,6,10,12,14,15,18,20,21,\dots \;\;\;\;{\text{ is not a prime power}}.\end{cases}}}
p (n ) – partition function[ edit ] p (n )n as a sum of positive integers, where two representations with the same summands in a different order are not counted as being different:p ( n ) = | { ( a 1 , a 2 , … a k ) : 0 < a 1 ≤ a 2 ≤ ⋯ ≤ a k ∧ n = a 1 + a 2 + ⋯ + a k } | . {\displaystyle p(n)=\left|\left\{(a_{1},a_{2},\dots a_{k}):0<a_{1}\leq a_{2}\leq \cdots \leq a_{k}\;\land \;n=a_{1}+a_{2}+\cdots +a_{k}\right\}\right|.}
λ (n ) – Carmichael function[ edit ] λ (n )a λ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}} a coprime ton . Equivalently, it is theleast common multiple of the orders of the elements of themultiplicative group of integers modulon .
For powers of odd primes and for 2 and 4,λ (n ) is equal to the Euler totient function ofn ; for powers of 2 greater than 4 it is equal to one half of the Euler totient function ofn :λ ( n ) = { ϕ ( n ) if n = 2 , 3 , 4 , 5 , 7 , 9 , 11 , 13 , 17 , 19 , 23 , 25 , 27 , … 1 2 ϕ ( n ) if n = 8 , 16 , 32 , 64 , … {\displaystyle \lambda (n)={\begin{cases}\;\;\phi (n)&{\text{if }}n=2,3,4,5,7,9,11,13,17,19,23,25,27,\dots \\{\tfrac {1}{2}}\phi (n)&{\text{if }}n=8,16,32,64,\dots \end{cases}}} n it is the least common multiple ofλ of each of the prime power factors ofn :λ ( p 1 a 1 p 2 a 2 … p ω ( n ) a ω ( n ) ) = lcm [ λ ( p 1 a 1 ) , λ ( p 2 a 2 ) , … , λ ( p ω ( n ) a ω ( n ) ) ] . {\displaystyle \lambda (p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{\omega (n)}^{a_{\omega (n)}})=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})].}
h (n ) – class number[ edit ] h (n )ideal class group of an algebraic extension of the rationals withdiscriminant n . The notation is ambiguous, as there are in general many extensions with the same discriminant. Seequadratic field andcyclotomic field for classical examples.
r k n ) – sum ofk squares[ edit ] r k n )n can be represented as the sum ofk squares, where representations that differ only in the order of the summands or in the signs of the square roots are counted as different.r k ( n ) = | { ( a 1 , a 2 , … , a k ) : n = a 1 2 + a 2 2 + ⋯ + a k 2 } | {\displaystyle r_{k}(n)=\left|\left\{(a_{1},a_{2},\dots ,a_{k}):n=a_{1}^{2}+a_{2}^{2}+\cdots +a_{k}^{2}\right\}\right|}
D (n ) – Arithmetic derivative[ edit ] Using theHeaviside notation for the derivative, thearithmetic derivative D (n ) is a function such that
Summation functions [ edit ] Given an arithmetic functiona (n ), itssummation function A (x ) is defined byA ( x ) := ∑ n ≤ x a ( n ) . {\displaystyle A(x):=\sum _{n\leq x}a(n).} A can be regarded as a function of a real variable. Given a positive integerm ,A is constant alongopen intervals m <x <m + 1, and has ajump discontinuity at each integer for whicha (m ) ≠ 0.
Since such functions are often represented by series and integrals, to achieve pointwise convergence it is usual to define the value at the discontinuities as the average of the values to the left and right:A 0 ( m ) := 1 2 ( ∑ n < m a ( n ) + ∑ n ≤ m a ( n ) ) = A ( m ) − 1 2 a ( m ) . {\displaystyle A_{0}(m):={\frac {1}{2}}\left(\sum _{n<m}a(n)+\sum _{n\leq m}a(n)\right)=A(m)-{\frac {1}{2}}a(m).}
Individual values of arithmetic functions may fluctuate wildly – as in most of the above examples. Summation functions "smooth out" these fluctuations. In some cases it may be possible to findasymptotic behaviour for the summation function for largex .
A classical example of this phenomenon[ 9] divisor summatory function , the summation function ofd (n ), the number of divisors ofn :lim inf n → ∞ d ( n ) = 2 {\displaystyle \liminf _{n\to \infty }d(n)=2} lim sup n → ∞ log d ( n ) log log n log n = log 2 {\displaystyle \limsup _{n\to \infty }{\frac {\log d(n)\log \log n}{\log n}}=\log 2} lim n → ∞ d ( 1 ) + d ( 2 ) + ⋯ + d ( n ) log ( 1 ) + log ( 2 ) + ⋯ + log ( n ) = 1. {\displaystyle \lim _{n\to \infty }{\frac {d(1)+d(2)+\cdots +d(n)}{\log(1)+\log(2)+\cdots +\log(n)}}=1.}
Anaverage order of an arithmetic function g is anaverage order off if∑ n ≤ x f ( n ) ∼ ∑ n ≤ x g ( n ) {\displaystyle \sum _{n\leq x}f(n)\sim \sum _{n\leq x}g(n)}
asx tends to infinity. The example above shows thatd (n ) has the average order log(n ).[ 10]
Dirichlet convolution [ edit ] Given an arithmetic functiona (n ), letF a s ), for complexs , be the function defined by the correspondingDirichlet series (where itconverges ):[ 11] F a ( s ) := ∑ n = 1 ∞ a ( n ) n s . {\displaystyle F_{a}(s):=\sum _{n=1}^{\infty }{\frac {a(n)}{n^{s}}}.} F a s ) is called agenerating function ofa (n ). The simplest such series, corresponding to the constant functiona (n ) = 1 for alln , isζ (s ) theRiemann zeta function .
The generating function of the Möbius function is the inverse of the zeta function:ζ ( s ) ∑ n = 1 ∞ μ ( n ) n s = 1 , ℜ s > 1. {\displaystyle \zeta (s)\,\sum _{n=1}^{\infty }{\frac {\mu (n)}{n^{s}}}=1,\;\;\Re s>1.}
Consider two arithmetic functionsa andb and their respective generating functionsF a s ) andF b s ). The productF a s )F b s ) can be computed as follows:F a ( s ) F b ( s ) = ( ∑ m = 1 ∞ a ( m ) m s ) ( ∑ n = 1 ∞ b ( n ) n s ) . {\displaystyle F_{a}(s)F_{b}(s)=\left(\sum _{m=1}^{\infty }{\frac {a(m)}{m^{s}}}\right)\left(\sum _{n=1}^{\infty }{\frac {b(n)}{n^{s}}}\right).}
It is a straightforward exercise to show that ifc (n ) is defined byc ( n ) := ∑ i j = n a ( i ) b ( j ) = ∑ i ∣ n a ( i ) b ( n i ) , {\displaystyle c(n):=\sum _{ij=n}a(i)b(j)=\sum _{i\mid n}a(i)b\left({\frac {n}{i}}\right),} F c ( s ) = F a ( s ) F b ( s ) . {\displaystyle F_{c}(s)=F_{a}(s)F_{b}(s).}
This functionc is called theDirichlet convolution ofa andb , and is denoted bya ∗ b {\displaystyle a*b}
A particularly important case is convolution with the constant functiona (n ) = 1 for alln , corresponding to multiplying the generating function by the zeta function:g ( n ) = ∑ d ∣ n f ( d ) . {\displaystyle g(n)=\sum _{d\mid n}f(d).}
Multiplying by the inverse of the zeta function gives theMöbius inversion formula:f ( n ) = ∑ d ∣ n μ ( n d ) g ( d ) . {\displaystyle f(n)=\sum _{d\mid n}\mu \left({\frac {n}{d}}\right)g(d).}
Iff is multiplicative, then so isg . Iff is completely multiplicative, theng is multiplicative, but may or may not be completely multiplicative.
Relations among the functions [ edit ] There are a great many formulas connecting arithmetical functions with each other and with the functions of analysis, especially powers, roots, and the exponential and log functions. The pagedivisor sum identities contains many more generalized and related examples of identities involving arithmetic functions.
Here are a few examples:
Dirichlet convolutions [ edit ] ∑ δ ∣ n μ ( δ ) = ∑ δ ∣ n λ ( n δ ) | μ ( δ ) | = { 1 if n = 1 0 if n ≠ 1 {\displaystyle \sum _{\delta \mid n}\mu (\delta )=\sum _{\delta \mid n}\lambda \left({\frac {n}{\delta }}\right)|\mu (\delta )|={\begin{cases}1&{\text{if }}n=1\\0&{\text{if }}n\neq 1\end{cases}}} λ is the Liouville function.[ 12] ∑ δ ∣ n φ ( δ ) = n . {\displaystyle \sum _{\delta \mid n}\varphi (\delta )=n.} [ 13] φ ( n ) = ∑ δ ∣ n μ ( n δ ) δ = n ∑ δ ∣ n μ ( δ ) δ . {\displaystyle \varphi (n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\delta =n\sum _{\delta \mid n}{\frac {\mu (\delta )}{\delta }}.} ∑ d ∣ n J k ( d ) = n k . {\displaystyle \sum _{d\mid n}J_{k}(d)=n^{k}.} [ 14] J k ( n ) = ∑ δ ∣ n μ ( n δ ) δ k = n k ∑ δ ∣ n μ ( δ ) δ k . {\displaystyle J_{k}(n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\delta ^{k}=n^{k}\sum _{\delta \mid n}{\frac {\mu (\delta )}{\delta ^{k}}}.} ∑ δ ∣ n δ s J r ( δ ) J s ( n δ ) = J r + s ( n ) {\displaystyle \sum _{\delta \mid n}\delta ^{s}J_{r}(\delta )J_{s}\left({\frac {n}{\delta }}\right)=J_{r+s}(n)} [ 15] ∑ δ ∣ n φ ( δ ) d ( n δ ) = σ ( n ) . {\displaystyle \sum _{\delta \mid n}\varphi (\delta )d\left({\frac {n}{\delta }}\right)=\sigma (n).} [ 16] [ 17] ∑ δ ∣ n | μ ( δ ) | = 2 ω ( n ) . {\displaystyle \sum _{\delta \mid n}|\mu (\delta )|=2^{\omega (n)}.} [ 18] | μ ( n ) | = ∑ δ ∣ n μ ( n δ ) 2 ω ( δ ) . {\displaystyle |\mu (n)|=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)2^{\omega (\delta )}.} ∑ δ ∣ n 2 ω ( δ ) = d ( n 2 ) . {\displaystyle \sum _{\delta \mid n}2^{\omega (\delta )}=d(n^{2}).} 2 ω ( n ) = ∑ δ ∣ n μ ( n δ ) d ( δ 2 ) . {\displaystyle 2^{\omega (n)}=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)d(\delta ^{2}).} ∑ δ ∣ n d ( δ 2 ) = d 2 ( n ) . {\displaystyle \sum _{\delta \mid n}d(\delta ^{2})=d^{2}(n).} d ( n 2 ) = ∑ δ ∣ n μ ( n δ ) d 2 ( δ ) . {\displaystyle d(n^{2})=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)d^{2}(\delta ).} ∑ δ ∣ n d ( n δ ) 2 ω ( δ ) = d 2 ( n ) . {\displaystyle \sum _{\delta \mid n}d\left({\frac {n}{\delta }}\right)2^{\omega (\delta )}=d^{2}(n).} ∑ δ ∣ n λ ( δ ) = { 1 if n is a square 0 if n is not square. {\displaystyle \sum _{\delta \mid n}\lambda (\delta )={\begin{cases}&1{\text{ if }}n{\text{ is a square }}\\&0{\text{ if }}n{\text{ is not square.}}\end{cases}}} Liouville function .∑ δ ∣ n Λ ( δ ) = log n . {\displaystyle \sum _{\delta \mid n}\Lambda (\delta )=\log n.} [ 19] Λ ( n ) = ∑ δ ∣ n μ ( n δ ) log ( δ ) . {\displaystyle \Lambda (n)=\sum _{\delta \mid n}\mu \left({\frac {n}{\delta }}\right)\log(\delta ).} For allk ≥ 4 , r k ( n ) > 0. {\displaystyle k\geq 4,\;\;\;r_{k}(n)>0.} Lagrange's four-square theorem ).
r 2 ( n ) = 4 ∑ d ∣ n ( − 4 d ) , {\displaystyle r_{2}(n)=4\sum _{d\mid n}\left({\frac {-4}{d}}\right),} [ 20] where theKronecker symbol has the values
( − 4 n ) = { + 1 if n ≡ 1 ( mod 4 ) − 1 if n ≡ 3 ( mod 4 ) 0 if n is even . {\displaystyle \left({\frac {-4}{n}}\right)={\begin{cases}+1&{\text{if }}n\equiv 1{\pmod {4}}\\-1&{\text{if }}n\equiv 3{\pmod {4}}\\\;\;\;0&{\text{if }}n{\text{ is even}}.\\\end{cases}}} There is a formula forr 3 in the section onclass numbers below.r 4 ( n ) = 8 ∑ 4 ∤ d d ∣ n d = 8 ( 2 + ( − 1 ) n ) ∑ 2 ∤ d d ∣ n d = { 8 σ ( n ) if n is odd 24 σ ( n 2 ν ) if n is even , {\displaystyle r_{4}(n)=8\sum _{\stackrel {d\mid n}{4\,\nmid \,d}}d=8(2+(-1)^{n})\sum _{\stackrel {d\mid n}{2\,\nmid \,d}}d={\begin{cases}8\sigma (n)&{\text{if }}n{\text{ is odd }}\\24\sigma \left({\frac {n}{2^{\nu }}}\right)&{\text{if }}n{\text{ is even }}\end{cases}},} ν =ν 2 (n )[ 21] [ 22] [ 23] r 6 ( n ) = 16 ∑ d ∣ n χ ( n d ) d 2 − 4 ∑ d ∣ n χ ( d ) d 2 , {\displaystyle r_{6}(n)=16\sum _{d\mid n}\chi \left({\frac {n}{d}}\right)d^{2}-4\sum _{d\mid n}\chi (d)d^{2},} χ ( n ) = ( − 4 n ) . {\displaystyle \chi (n)=\left({\frac {-4}{n}}\right).} [ 24]
Define the functionσ k * (n )[ 25] σ k ∗ ( n ) = ( − 1 ) n ∑ d ∣ n ( − 1 ) d d k = { ∑ d ∣ n d k = σ k ( n ) if n is odd ∑ 2 ∣ d d ∣ n d k − ∑ 2 ∤ d d ∣ n d k if n is even . {\displaystyle \sigma _{k}^{*}(n)=(-1)^{n}\sum _{d\mid n}(-1)^{d}d^{k}={\begin{cases}\sum _{d\mid n}d^{k}=\sigma _{k}(n)&{\text{if }}n{\text{ is odd }}\\\sum _{\stackrel {d\mid n}{2\,\mid \,d}}d^{k}-\sum _{\stackrel {d\mid n}{2\,\nmid \,d}}d^{k}&{\text{if }}n{\text{ is even}}.\end{cases}}}
That is, ifn is odd,σ k * (n )k th powers of the divisors ofn , that is,σ k n ),n is even it is the sum of thek th powers of the even divisors ofn minus the sum of thek th powers of the odd divisors ofn .
r 8 ( n ) = 16 σ 3 ∗ ( n ) . {\displaystyle r_{8}(n)=16\sigma _{3}^{*}(n).} [ 24] [ 26] Adopt the convention that Ramanujan'sτ (x ) = 0x isnot an integer.
r 24 ( n ) = 16 691 σ 11 ∗ ( n ) + 128 691 { ( − 1 ) n − 1 259 τ ( n ) − 512 τ ( n 2 ) } {\displaystyle r_{24}(n)={\frac {16}{691}}\sigma _{11}^{*}(n)+{\frac {128}{691}}\left\{(-1)^{n-1}259\tau (n)-512\tau \left({\frac {n}{2}}\right)\right\}} [ 27] Divisor sum convolutions [ edit ] Here "convolution" does not mean "Dirichlet convolution" but instead refers to the formula for the coefficients of theproduct of two power series :
( ∑ n = 0 ∞ a n x n ) ( ∑ n = 0 ∞ b n x n ) = ∑ i = 0 ∞ ∑ j = 0 ∞ a i b j x i + j = ∑ n = 0 ∞ ( ∑ i = 0 n a i b n − i ) x n = ∑ n = 0 ∞ c n x n . {\displaystyle \left(\sum _{n=0}^{\infty }a_{n}x^{n}\right)\left(\sum _{n=0}^{\infty }b_{n}x^{n}\right)=\sum _{i=0}^{\infty }\sum _{j=0}^{\infty }a_{i}b_{j}x^{i+j}=\sum _{n=0}^{\infty }\left(\sum _{i=0}^{n}a_{i}b_{n-i}\right)x^{n}=\sum _{n=0}^{\infty }c_{n}x^{n}.} The sequencec n = ∑ i = 0 n a i b n − i {\displaystyle c_{n}=\sum _{i=0}^{n}a_{i}b_{n-i}} convolution or theCauchy product of the sequencesa n b n Eisenstein series ) or by elementary methods.[ 28]
σ 3 ( n ) = 1 5 { 6 n σ 1 ( n ) − σ 1 ( n ) + 12 ∑ 0 < k < n σ 1 ( k ) σ 1 ( n − k ) } . {\displaystyle \sigma _{3}(n)={\frac {1}{5}}\left\{6n\sigma _{1}(n)-\sigma _{1}(n)+12\sum _{0<k<n}\sigma _{1}(k)\sigma _{1}(n-k)\right\}.} [ 29] σ 5 ( n ) = 1 21 { 10 ( 3 n − 1 ) σ 3 ( n ) + σ 1 ( n ) + 240 ∑ 0 < k < n σ 1 ( k ) σ 3 ( n − k ) } . {\displaystyle \sigma _{5}(n)={\frac {1}{21}}\left\{10(3n-1)\sigma _{3}(n)+\sigma _{1}(n)+240\sum _{0<k<n}\sigma _{1}(k)\sigma _{3}(n-k)\right\}.} [ 30] σ 7 ( n ) = 1 20 { 21 ( 2 n − 1 ) σ 5 ( n ) − σ 1 ( n ) + 504 ∑ 0 < k < n σ 1 ( k ) σ 5 ( n − k ) } = σ 3 ( n ) + 120 ∑ 0 < k < n σ 3 ( k ) σ 3 ( n − k ) . {\displaystyle {\begin{aligned}\sigma _{7}(n)&={\frac {1}{20}}\left\{21(2n-1)\sigma _{5}(n)-\sigma _{1}(n)+504\sum _{0<k<n}\sigma _{1}(k)\sigma _{5}(n-k)\right\}\\&=\sigma _{3}(n)+120\sum _{0<k<n}\sigma _{3}(k)\sigma _{3}(n-k).\end{aligned}}} [ 30] [ 31] σ 9 ( n ) = 1 11 { 10 ( 3 n − 2 ) σ 7 ( n ) + σ 1 ( n ) + 480 ∑ 0 < k < n σ 1 ( k ) σ 7 ( n − k ) } = 1 11 { 21 σ 5 ( n ) − 10 σ 3 ( n ) + 5040 ∑ 0 < k < n σ 3 ( k ) σ 5 ( n − k ) } . {\displaystyle {\begin{aligned}\sigma _{9}(n)&={\frac {1}{11}}\left\{10(3n-2)\sigma _{7}(n)+\sigma _{1}(n)+480\sum _{0<k<n}\sigma _{1}(k)\sigma _{7}(n-k)\right\}\\&={\frac {1}{11}}\left\{21\sigma _{5}(n)-10\sigma _{3}(n)+5040\sum _{0<k<n}\sigma _{3}(k)\sigma _{5}(n-k)\right\}.\end{aligned}}} [ 29] [ 32] τ ( n ) = 65 756 σ 11 ( n ) + 691 756 σ 5 ( n ) − 691 3 ∑ 0 < k < n σ 5 ( k ) σ 5 ( n − k ) , {\displaystyle \tau (n)={\frac {65}{756}}\sigma _{11}(n)+{\frac {691}{756}}\sigma _{5}(n)-{\frac {691}{3}}\sum _{0<k<n}\sigma _{5}(k)\sigma _{5}(n-k),} τ (n ) is Ramanujan's function. [ 33] [ 34] Sinceσ k n ) (for natural numberk ) andτ (n ) are integers, the above formulas can be used to prove congruences[ 35] Ramanujan tau function for some examples.
Extend the domain of the partition function by settingp (0) = 1.
p ( n ) = 1 n ∑ 1 ≤ k ≤ n σ ( k ) p ( n − k ) . {\displaystyle p(n)={\frac {1}{n}}\sum _{1\leq k\leq n}\sigma (k)p(n-k).} [ 36] p (n ).Class number related [ edit ] Peter Gustav Lejeune Dirichlet discovered formulas that relate the class numberh ofquadratic number fields to the Jacobi symbol.[ 37]
An integerD is called afundamental discriminant if it is thediscriminant of a quadratic number field. This is equivalent toD ≠ 1 and either a)D issquarefree andD ≡ 1 (mod 4) or b)D ≡ 0 (mod 4),D /4 is squarefree, andD /4 ≡ 2 or 3 (mod 4).[ 38]
Extend the Jacobi symbol to accept even numbers in the "denominator" by defining theKronecker symbol :( a 2 ) = { 0 if a is even ( − 1 ) a 2 − 1 8 if a is odd. {\displaystyle \left({\frac {a}{2}}\right)={\begin{cases}\;\;\,0&{\text{ if }}a{\text{ is even}}\\(-1)^{\frac {a^{2}-1}{8}}&{\text{ if }}a{\text{ is odd. }}\end{cases}}}
Then ifD < −4 is a fundamental discriminant[ 39] [ 40] h ( D ) = 1 D ∑ r = 1 | D | r ( D r ) = 1 2 − ( D 2 ) ∑ r = 1 | D | / 2 ( D r ) . {\displaystyle {\begin{aligned}h(D)&={\frac {1}{D}}\sum _{r=1}^{|D|}r\left({\frac {D}{r}}\right)\\&={\frac {1}{2-\left({\tfrac {D}{2}}\right)}}\sum _{r=1}^{|D|/2}\left({\frac {D}{r}}\right).\end{aligned}}}
There is also a formula relatingr 3 andh . Again, letD be a fundamental discriminant,D < −4. Then[ 41] r 3 ( | D | ) = 12 ( 1 − ( D 2 ) ) h ( D ) . {\displaystyle r_{3}(|D|)=12\left(1-\left({\frac {D}{2}}\right)\right)h(D).}
Prime-count related [ edit ] LetH n = 1 + 1 2 + 1 3 + ⋯ + 1 n {\displaystyle H_{n}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}} n thharmonic number . Then
σ ( n ) ≤ H n + e H n log H n {\displaystyle \sigma (n)\leq H_{n}+e^{H_{n}}\log H_{n}} n if and only if theRiemann hypothesis is true. [ 42] The Riemann hypothesis is also equivalent to the statement that, for alln > 5040,σ ( n ) < e γ n log log n {\displaystyle \sigma (n)<e^{\gamma }n\log \log n} Euler–Mascheroni constant ). This isRobin's theorem .
∑ p ν p ( n ) = Ω ( n ) . {\displaystyle \sum _{p}\nu _{p}(n)=\Omega (n).} ψ ( x ) = ∑ n ≤ x Λ ( n ) . {\displaystyle \psi (x)=\sum _{n\leq x}\Lambda (n).} [ 43] Π ( x ) = ∑ n ≤ x Λ ( n ) log n . {\displaystyle \Pi (x)=\sum _{n\leq x}{\frac {\Lambda (n)}{\log n}}.} [ 44] e θ ( x ) = ∏ p ≤ x p . {\displaystyle e^{\theta (x)}=\prod _{p\leq x}p.} [ 45] e ψ ( x ) = lcm [ 1 , 2 , … , ⌊ x ⌋ ] . {\displaystyle e^{\psi (x)}=\operatorname {lcm} [1,2,\dots ,\lfloor x\rfloor ].} [ 46] In 1965P Kesava Menon proved[ 47] ∑ gcd ( k , n ) = 1 1 ≤ k ≤ n gcd ( k − 1 , n ) = φ ( n ) d ( n ) . {\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\gcd(k-1,n)=\varphi (n)d(n).}
This has been generalized by a number of mathematicians. For example,
B. Sury[ 48] ∑ gcd ( k 1 , n ) = 1 1 ≤ k 1 , k 2 , … , k s ≤ n gcd ( k 1 − 1 , k 2 , … , k s , n ) = φ ( n ) σ s − 1 ( n ) . {\displaystyle \sum _{\stackrel {1\leq k_{1},k_{2},\dots ,k_{s}\leq n}{\gcd(k_{1},n)=1}}\gcd(k_{1}-1,k_{2},\dots ,k_{s},n)=\varphi (n)\sigma _{s-1}(n).} N. Rao[ 49] ∑ gcd ( k 1 , k 2 , … , k s , n ) = 1 1 ≤ k 1 , k 2 , … , k s ≤ n gcd ( k 1 − a 1 , k 2 − a 2 , … , k s − a s , n ) s = J s ( n ) d ( n ) , {\displaystyle \sum _{\stackrel {1\leq k_{1},k_{2},\dots ,k_{s}\leq n}{\gcd(k_{1},k_{2},\dots ,k_{s},n)=1}}\gcd(k_{1}-a_{1},k_{2}-a_{2},\dots ,k_{s}-a_{s},n)^{s}=J_{s}(n)d(n),} a 1 ,a 2 , ...,a s a 1 ,a 2 , ...,a s n ) = 1. László Fejes Tóth [ 50] ∑ gcd ( k , m ) = 1 1 ≤ k ≤ m gcd ( k 2 − 1 , m 1 ) gcd ( k 2 − 1 , m 2 ) = φ ( n ) ∑ d 2 ∣ m 2 d 1 ∣ m 1 φ ( gcd ( d 1 , d 2 ) ) 2 ω ( lcm ( d 1 , d 2 ) ) , {\displaystyle \sum _{\stackrel {1\leq k\leq m}{\gcd(k,m)=1}}\gcd(k^{2}-1,m_{1})\gcd(k^{2}-1,m_{2})=\varphi (n)\sum _{\stackrel {d_{1}\mid m_{1}}{d_{2}\mid m_{2}}}\varphi (\gcd(d_{1},d_{2}))2^{\omega (\operatorname {lcm} (d_{1},d_{2}))},} m 1 andm 2 are odd,m = lcm(m 1 ,m 2 ).In fact, iff is any arithmetical function[ 51] [ 52] ∑ gcd ( k , n ) = 1 1 ≤ k ≤ n f ( gcd ( k − 1 , n ) ) = φ ( n ) ∑ d ∣ n ( μ ∗ f ) ( d ) φ ( d ) , {\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}f(\gcd(k-1,n))=\varphi (n)\sum _{d\mid n}{\frac {(\mu *f)(d)}{\varphi (d)}},} ∗ {\displaystyle *}
Letm andn be distinct, odd, and positive. Then the Jacobi symbol satisfies the law ofquadratic reciprocity :( m n ) ( n m ) = ( − 1 ) ( m − 1 ) ( n − 1 ) / 4 . {\displaystyle \left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{(m-1)(n-1)/4}.}
LetD (n ) be the arithmetic derivative. Then the logarithmic derivativeD ( n ) n = ∑ p prime p ∣ n v p ( n ) p . {\displaystyle {\frac {D(n)}{n}}=\sum _{\stackrel {p\mid n}{p{\text{ prime}}}}{\frac {v_{p}(n)}{p}}.} Arithmetic derivative
Letλ (n ) be Liouville's function. Then
| λ ( n ) | μ ( n ) = λ ( n ) | μ ( n ) | = μ ( n ) , {\displaystyle |\lambda (n)|\mu (n)=\lambda (n)|\mu (n)|=\mu (n),} λ ( n ) μ ( n ) = | μ ( n ) | = μ 2 ( n ) . {\displaystyle \lambda (n)\mu (n)=|\mu (n)|=\mu ^{2}(n).} Letλ (n ) be Carmichael's function. Then
λ ( n ) ∣ ϕ ( n ) . {\displaystyle \lambda (n)\mid \phi (n).} λ ( n ) = ϕ ( n ) if and only if n = { 1 , 2 , 4 ; 3 , 5 , 7 , 9 , 11 , … (that is, p k , where p is an odd prime) ; 6 , 10 , 14 , 18 , … (that is, 2 p k , where p is an odd prime) . {\displaystyle \lambda (n)=\phi (n){\text{ if and only if }}n={\begin{cases}1,2,4;\\3,5,7,9,11,\ldots {\text{ (that is, }}p^{k}{\text{, where }}p{\text{ is an odd prime)}};\\6,10,14,18,\ldots {\text{ (that is, }}2p^{k}{\text{, where }}p{\text{ is an odd prime)}}.\end{cases}}} SeeMultiplicative group of integers modulo n andPrimitive root modulo n .
2 ω ( n ) ≤ d ( n ) ≤ 2 Ω ( n ) . {\displaystyle 2^{\omega (n)}\leq d(n)\leq 2^{\Omega (n)}.} [ 53] [ 54] 6 π 2 < ϕ ( n ) σ ( n ) n 2 < 1. {\displaystyle {\frac {6}{\pi ^{2}}}<{\frac {\phi (n)\sigma (n)}{n^{2}}}<1.} [ 55] c q ( n ) = μ ( q gcd ( q , n ) ) ϕ ( q gcd ( q , n ) ) ϕ ( q ) = ∑ δ ∣ gcd ( q , n ) μ ( q δ ) δ . {\displaystyle {\begin{aligned}c_{q}(n)&={\frac {\mu \left({\frac {q}{\gcd(q,n)}}\right)}{\phi \left({\frac {q}{\gcd(q,n)}}\right)}}\phi (q)\\&=\sum _{\delta \mid \gcd(q,n)}\mu \left({\frac {q}{\delta }}\right)\delta .\end{aligned}}} [ 56] ϕ ( q ) = ∑ δ ∣ q μ ( q δ ) δ . {\displaystyle \phi (q)=\sum _{\delta \mid q}\mu \left({\frac {q}{\delta }}\right)\delta .} [ 57] c q ( 1 ) = μ ( q ) . {\displaystyle c_{q}(1)=\mu (q).} c q ( q ) = ϕ ( q ) . {\displaystyle c_{q}(q)=\phi (q).} ∑ δ ∣ n d 3 ( δ ) = ( ∑ δ ∣ n d ( δ ) ) 2 . {\displaystyle \sum _{\delta \mid n}d^{3}(\delta )=\left(\sum _{\delta \mid n}d(\delta )\right)^{2}.} [ 58] 13 + 23 + 33 + ... +n 3 = (1 + 2 + 3 + ... +n )2 d ( u v ) = ∑ δ ∣ gcd ( u , v ) μ ( δ ) d ( u δ ) d ( v δ ) . {\displaystyle d(uv)=\sum _{\delta \mid \gcd(u,v)}\mu (\delta )d\left({\frac {u}{\delta }}\right)d\left({\frac {v}{\delta }}\right).} [ 59] σ k ( u ) σ k ( v ) = ∑ δ ∣ gcd ( u , v ) δ k σ k ( u v δ 2 ) . {\displaystyle \sigma _{k}(u)\sigma _{k}(v)=\sum _{\delta \mid \gcd(u,v)}\delta ^{k}\sigma _{k}\left({\frac {uv}{\delta ^{2}}}\right).} [ 60] τ ( u ) τ ( v ) = ∑ δ ∣ gcd ( u , v ) δ 11 τ ( u v δ 2 ) , {\displaystyle \tau (u)\tau (v)=\sum _{\delta \mid \gcd(u,v)}\delta ^{11}\tau \left({\frac {uv}{\delta ^{2}}}\right),} τ (n ) is Ramanujan's function. [ 61] First 100 values of some arithmetic functions [ edit ] n factorization φ (n )ω (n )Ω(n ) λ (n )μ (n )Λ(n ) π (n )σ 0 (n )σ 1 (n )σ 2 (n )r 2 (n )r 3 (n )r 4 (n )1 1 1 0 0 1 1 0 0 1 1 1 4 6 8 2 2 1 1 1 −1 −1 0.69 1 2 3 5 4 12 24 3 3 2 1 1 −1 −1 1.10 2 2 4 10 0 8 32 4 22 2 1 2 1 0 0.69 2 3 7 21 4 6 24 5 5 4 1 1 −1 −1 1.61 3 2 6 26 8 24 48 6 2 · 3 2 2 2 1 1 0 3 4 12 50 0 24 96 7 7 6 1 1 −1 −1 1.95 4 2 8 50 0 0 64 8 23 4 1 3 −1 0 0.69 4 4 15 85 4 12 24 9 32 6 1 2 1 0 1.10 4 3 13 91 4 30 104 10 2 · 5 4 2 2 1 1 0 4 4 18 130 8 24 144 11 11 10 1 1 −1 −1 2.40 5 2 12 122 0 24 96 12 22 · 3 4 2 3 −1 0 0 5 6 28 210 0 8 96 13 13 12 1 1 −1 −1 2.56 6 2 14 170 8 24 112 14 2 · 7 6 2 2 1 1 0 6 4 24 250 0 48 192 15 3 · 5 8 2 2 1 1 0 6 4 24 260 0 0 192 16 24 8 1 4 1 0 0.69 6 5 31 341 4 6 24 17 17 16 1 1 −1 −1 2.83 7 2 18 290 8 48 144 18 2 · 32 6 2 3 −1 0 0 7 6 39 455 4 36 312 19 19 18 1 1 −1 −1 2.94 8 2 20 362 0 24 160 20 22 · 5 8 2 3 −1 0 0 8 6 42 546 8 24 144 21 3 · 7 12 2 2 1 1 0 8 4 32 500 0 48 256 22 2 · 11 10 2 2 1 1 0 8 4 36 610 0 24 288 23 23 22 1 1 −1 −1 3.14 9 2 24 530 0 0 192 24 23 · 3 8 2 4 1 0 0 9 8 60 850 0 24 96 25 52 20 1 2 1 0 1.61 9 3 31 651 12 30 248 26 2 · 13 12 2 2 1 1 0 9 4 42 850 8 72 336 27 33 18 1 3 −1 0 1.10 9 4 40 820 0 32 320 28 22 · 7 12 2 3 −1 0 0 9 6 56 1050 0 0 192 29 29 28 1 1 −1 −1 3.37 10 2 30 842 8 72 240 30 2 · 3 · 5 8 3 3 −1 −1 0 10 8 72 1300 0 48 576 31 31 30 1 1 −1 −1 3.43 11 2 32 962 0 0 256 32 25 16 1 5 −1 0 0.69 11 6 63 1365 4 12 24 33 3 · 11 20 2 2 1 1 0 11 4 48 1220 0 48 384 34 2 · 17 16 2 2 1 1 0 11 4 54 1450 8 48 432 35 5 · 7 24 2 2 1 1 0 11 4 48 1300 0 48 384 36 22 · 32 12 2 4 1 0 0 11 9 91 1911 4 30 312 37 37 36 1 1 −1 −1 3.61 12 2 38 1370 8 24 304 38 2 · 19 18 2 2 1 1 0 12 4 60 1810 0 72 480 39 3 · 13 24 2 2 1 1 0 12 4 56 1700 0 0 448 40 23 · 5 16 2 4 1 0 0 12 8 90 2210 8 24 144 41 41 40 1 1 −1 −1 3.71 13 2 42 1682 8 96 336 42 2 · 3 · 7 12 3 3 −1 −1 0 13 8 96 2500 0 48 768 43 43 42 1 1 −1 −1 3.76 14 2 44 1850 0 24 352 44 22 · 11 20 2 3 −1 0 0 14 6 84 2562 0 24 288 45 32 · 5 24 2 3 −1 0 0 14 6 78 2366 8 72 624 46 2 · 23 22 2 2 1 1 0 14 4 72 2650 0 48 576 47 47 46 1 1 −1 −1 3.85 15 2 48 2210 0 0 384 48 24 · 3 16 2 5 −1 0 0 15 10 124 3410 0 8 96 49 72 42 1 2 1 0 1.95 15 3 57 2451 4 54 456 50 2 · 52 20 2 3 −1 0 0 15 6 93 3255 12 84 744 51 3 · 17 32 2 2 1 1 0 15 4 72 2900 0 48 576 52 22 · 13 24 2 3 −1 0 0 15 6 98 3570 8 24 336 53 53 52 1 1 −1 −1 3.97 16 2 54 2810 8 72 432 54 2 · 33 18 2 4 1 0 0 16 8 120 4100 0 96 960 55 5 · 11 40 2 2 1 1 0 16 4 72 3172 0 0 576 56 23 · 7 24 2 4 1 0 0 16 8 120 4250 0 48 192 57 3 · 19 36 2 2 1 1 0 16 4 80 3620 0 48 640 58 2 · 29 28 2 2 1 1 0 16 4 90 4210 8 24 720 59 59 58 1 1 −1 −1 4.08 17 2 60 3482 0 72 480 60 22 · 3 · 5 16 3 4 1 0 0 17 12 168 5460 0 0 576 61 61 60 1 1 −1 −1 4.11 18 2 62 3722 8 72 496 62 2 · 31 30 2 2 1 1 0 18 4 96 4810 0 96 768 63 32 · 7 36 2 3 −1 0 0 18 6 104 4550 0 0 832 64 26 32 1 6 1 0 0.69 18 7 127 5461 4 6 24 65 5 · 13 48 2 2 1 1 0 18 4 84 4420 16 96 672 66 2 · 3 · 11 20 3 3 −1 −1 0 18 8 144 6100 0 96 1152 67 67 66 1 1 −1 −1 4.20 19 2 68 4490 0 24 544 68 22 · 17 32 2 3 −1 0 0 19 6 126 6090 8 48 432 69 3 · 23 44 2 2 1 1 0 19 4 96 5300 0 96 768 70 2 · 5 · 7 24 3 3 −1 −1 0 19 8 144 6500 0 48 1152 71 71 70 1 1 −1 −1 4.26 20 2 72 5042 0 0 576 72 23 · 32 24 2 5 −1 0 0 20 12 195 7735 4 36 312 73 73 72 1 1 −1 −1 4.29 21 2 74 5330 8 48 592 74 2 · 37 36 2 2 1 1 0 21 4 114 6850 8 120 912 75 3 · 52 40 2 3 −1 0 0 21 6 124 6510 0 56 992 76 22 · 19 36 2 3 −1 0 0 21 6 140 7602 0 24 480 77 7 · 11 60 2 2 1 1 0 21 4 96 6100 0 96 768 78 2 · 3 · 13 24 3 3 −1 −1 0 21 8 168 8500 0 48 1344 79 79 78 1 1 −1 −1 4.37 22 2 80 6242 0 0 640 80 24 · 5 32 2 5 −1 0 0 22 10 186 8866 8 24 144 81 34 54 1 4 1 0 1.10 22 5 121 7381 4 102 968 82 2 · 41 40 2 2 1 1 0 22 4 126 8410 8 48 1008 83 83 82 1 1 −1 −1 4.42 23 2 84 6890 0 72 672 84 22 · 3 · 7 24 3 4 1 0 0 23 12 224 10500 0 48 768 85 5 · 17 64 2 2 1 1 0 23 4 108 7540 16 48 864 86 2 · 43 42 2 2 1 1 0 23 4 132 9250 0 120 1056 87 3 · 29 56 2 2 1 1 0 23 4 120 8420 0 0 960 88 23 · 11 40 2 4 1 0 0 23 8 180 10370 0 24 288 89 89 88 1 1 −1 −1 4.49 24 2 90 7922 8 144 720 90 2 · 32 · 5 24 3 4 1 0 0 24 12 234 11830 8 120 1872 91 7 · 13 72 2 2 1 1 0 24 4 112 8500 0 48 896 92 22 · 23 44 2 3 −1 0 0 24 6 168 11130 0 0 576 93 3 · 31 60 2 2 1 1 0 24 4 128 9620 0 48 1024 94 2 · 47 46 2 2 1 1 0 24 4 144 11050 0 96 1152 95 5 · 19 72 2 2 1 1 0 24 4 120 9412 0 0 960 96 25 · 3 32 2 6 1 0 0 24 12 252 13650 0 24 96 97 97 96 1 1 −1 −1 4.57 25 2 98 9410 8 48 784 98 2 · 72 42 2 3 −1 0 0 25 6 171 12255 4 108 1368 99 32 · 11 60 2 3 −1 0 0 25 6 156 11102 0 72 1248 100 22 · 52 40 2 4 1 0 0 25 9 217 13671 12 30 744 n factorization φ (n )ω (n )Ω(n ) 𝜆(n ) 𝜇(n ) Λ(n ) π (n )σ 0 (n )σ 1 (n )σ 2 (n )r 2 (n )r 3 (n )r 4 (n )
^ Long (1972 , p. 151)^ Pettofrezzo & Byrkit (1970 , p. 58)^ Niven & Zuckerman, 4.2. ^ Nagell, I.9. ^ Bateman & Diamond, 2.1. ^ Hardy & Wright, intro. to Ch. XVI ^ Hardy,Ramanujan , § 10.2 ^ Apostol,Modular Functions ... , § 1.15, Ch. 4, and ch. 6 ^ Hardy & Wright, §§ 18.1–18.2 ^ Gérald Tenenbaum (1995).Introduction to Analytic and Probabilistic Number Theory . Cambridge studies in advanced mathematics. Vol. 46.Cambridge University Press . pp. 36– 55.ISBN 0-521-41261-7 ^ Hardy & Wright, § 17.6, show how the theory of generating functions can be constructed in a purely formal manner with no attention paid to convergence. ^ Hardy & Wright, Thm. 263 ^ Hardy & Wright, Thm. 63 ^ see references atJordan's totient function ^ Holden et al. in external links The formula is Gegenbauer's ^ Hardy & Wright, Thm. 288–290 ^ Dineva in external links, prop. 4 ^ Hardy & Wright, Thm. 264 ^ Hardy & Wright, Thm. 296 ^ Hardy & Wright, Thm. 278 ^ Hardy & Wright, Thm. 386 ^ Hardy,Ramanujan , eqs 9.1.2, 9.1.3 ^ Koblitz, Ex. III.5.2 ^a b Hardy & Wright, § 20.13 ^ Hardy,Ramanujan , § 9.7 ^ Hardy,Ramanujan , § 9.13 ^ Hardy,Ramanujan , § 9.17 ^ Williams, ch. 13; Huard, et al. (external links). ^a b Ramanujan,On Certain Arithmetical Functions , Table IV;Papers , p. 146 ^a b Koblitz, ex. III.2.8 ^ Koblitz, ex. III.2.3 ^ Koblitz, ex. III.2.2 ^ Koblitz, ex. III.2.4 ^ Apostol,Modular Functions ... , Ex. 6.10 ^ Apostol,Modular Functions... , Ch. 6 Ex. 10 ^ G.H. Hardy, S. Ramannujan,Asymptotic Formulæ in Combinatory Analysis , § 1.3; in Ramannujan,Papers p. 279 ^ Landau, p. 168, credits Gauss as well as Dirichlet ^ Cohen, Def. 5.1.2 ^ Cohen, Corr. 5.3.13 ^ see Edwards, § 9.5 exercises for more complicated formulas. ^ Cohen, Prop 5.3.10 ^ SeeDivisor function . ^ Hardy & Wright, eq. 22.1.2 ^ Seeprime-counting functions . ^ Hardy & Wright, eq. 22.1.1 ^ Hardy & Wright, eq. 22.1.3 ^ László Tóth,Menon's Identity and Arithmetical Sums ... , eq. 1 ^ Tóth, eq. 5 ^ Tóth, eq. 3 ^ Tóth, eq. 35 ^ Tóth, eq. 2 ^ Tóth states that Menon proved this for multiplicativef in 1965 and V. Sita Ramaiah for generalf . ^ HardyRamanujan , eq. 3.10.3 ^ Hardy & Wright, § 22.13 ^ Hardy & Wright, Thm. 329 ^ Hardy & Wright, Thms. 271, 272 ^ Hardy & Wright, eq. 16.3.1 ^ Ramanujan,Some Formulæ in the Analytic Theory of Numbers , eq. (C);Papers p. 133. A footnote says that Hardy told Ramanujan it also appears in an 1857 paper by Liouville. ^ Ramanujan,Some Formulæ in the Analytic Theory of Numbers , eq. (F);Papers p. 134 ^ Apostol,Modular Functions ... , ch. 6 eq. 4 ^ Apostol,Modular Functions ... , ch. 6 eq. 3 Tom M. Apostol (1976),Introduction to Analytic Number Theory Undergraduate Texts in Mathematics ,ISBN 0-387-90163-9 Apostol, Tom M. (1989),Modular Functions and Dirichlet Series in Number Theory (2nd Edition) ISBN 0-387-97127-0 Bateman, Paul T. ; Diamond, Harold G. (2004),Analytic number theory, an introduction ,World Scientific ,ISBN 978-981-238-938-1 Cohen, Henri (1993),A Course in Computational Algebraic Number Theory , Berlin:Springer ,ISBN 3-540-55640-0 Edwards, Harold (1977).Fermat's Last Theorem . New York:Springer .ISBN 0-387-90230-9 Hardy, G. H. (1999),Ramanujan: Twelve Lectures on Subjects Suggested by his Life and work , Providence RI: AMS / Chelsea,hdl :10115/1436 ,ISBN 978-0-8218-2023-0 Hardy, G. H. ;Wright, E. M. (1979) [1938].An Introduction to the Theory of Numbers ISBN 0-19-853171-0 MR 0568909 .Zbl 0423.10001 .Jameson, G. J. O. (2003),The Prime Number Theorem , Cambridge University Press,ISBN 0-521-89110-8 Koblitz, Neal (1984),Introduction to Elliptic Curves and Modular Forms , New York: Springer,ISBN 0-387-97966-2 Landau, Edmund (1966),Elementary Number Theory , New York: ChelseaWilliam J. LeVeque (1996),Fundamentals of Number Theory , Courier Dover Publications,ISBN 0-486-68906-9 Long, Calvin T. (1972),Elementary Introduction to Number Theory (2nd ed.), Lexington:D. C. Heath and Company ,LCCN 77-171950 Elliott Mendelson (1987),Introduction to Mathematical Logic , CRC Press,ISBN 0-412-80830-7 Nagell, Trygve (1964),Introduction to number theory (2nd Edition) , Chelsea,ISBN 978-0-8218-2833-5 {{citation }}:ISBN / Date incompatibility (help ) Niven, Ivan M. ; Zuckerman, Herbert S. (1972),An introduction to the theory of numbers (3rd Edition) ,John Wiley & Sons ,ISBN 0-471-64154-5 Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970),Elements of Number Theory , Englewood Cliffs:Prentice Hall ,LCCN 77-81766 Ramanujan, Srinivasa (2000),Collected Papers , Providence RI: AMS / Chelsea,ISBN 978-0-8218-2076-6 Williams, Kenneth S. (2011),Number theory in the spirit of Liouville , London Mathematical Society Student Texts, vol. 76, Cambridge:Cambridge University Press ,ISBN 978-0-521-17562-3 Zbl 1227.11002 Schwarz, Wolfgang; Spilker, Jürgen (1994),Arithmetical Functions. An introduction to elementary and analytic properties of arithmetic functions and to some of their almost-periodic properties , London Mathematical Society Lecture Note Series, vol. 184,Cambridge University Press ,ISBN 0-521-42725-8 Zbl 0807.11001 "Arithmetic function" ,Encyclopedia of Mathematics EMS Press , 2001 [1994]Matthew Holden, Michael Orrison, Michael VarbleYet another Generalization of Euler's Totient Function Huard, Ou, Spearman, and Williams.Elementary Evaluation of Certain Convolution Sums Involving Divisor Functions Dineva, Rosica,The Euler Totient, the Möbius, and the Divisor Functions Archived 2021-01-16 at theWayback Machine László Tóth,Menon's Identity and arithmetical sums representing functions of several variables
Possessing a specific set of other numbers
Expressible via specific sums
