Arithmetic function

In number theory, an arithmetic, arithmetical, or number-theoretic function is generally any function whose domain is the set of positive integers and whose range is a subset of the complex numbers.

Uses your system voice; voice and rate in settings.

≈ 40 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Function whose domain is the positive integers

In number theory, an arithmetic, arithmetical, or number-theoretic function[1][2] is generally any function whose domain is the set of positive integers and whose range is a subset of the complex numbers.[3][4][5] Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n".[6] There is a larger class of number-theoretic functions that do not fit this definition, for example, the prime-counting functions. This article provides links to functions of both classes.

An example of an arithmetic function is the divisor function whose value at a positive integer n is equal to the number of divisors of n.

Arithmetic functions are often extremely irregular (see table), but some of them have series expansions in terms of Ramanujan's sum.

  • 5 Completely multiplicative functions
  • 6 Additive functions
  • 7 Completely additive functions
  • 8 Neither multiplicative nor additive
  • 9 Summation functions
  • 10 Dirichlet convolution
  • 11 Relations among the functions
  • 12 First 100 values of some arithmetic functions
  • 13 Notes
  • 14 References
  • 15 Further reading
  • 16 External links
  • Multiplicative and additive functions

    edit edit source

    An arithmetic function a is

    Two whole numbers m and n are called coprime if their greatest common divisor is 1, that is, if there is no prime number that divides both of them.

    Then an arithmetic function a is

    • additive if a(mn) = a(m) + a(n) for all coprime natural numbers m and n;
    • multiplicative if a(1) = 1 and a(mn) = a(m)a(n) for all coprime natural numbers m and n.

    Notation

    edit edit source

    In this article, ∑pf(p) and ∏pf(p) mean that the sum or product is over all prime numbers: ∑pf(p)=f(2)+f(3)+f(5)+⋯ and ∏pf(p)=f(2)f(3)f(5)⋯. Similarly, ∑pkf(pk) and ∏pkf(pk) mean that the sum or product is over all prime powers with strictly positive exponent (so k = 0 is not included): ∑pkf(pk)=∑p∑k>0f(pk)=f(2)+f(3)+f(4)+f(5)+f(7)+f(8)+f(9)+⋯.

    The notations ∑d∣nf(d) and ∏d∣nf(d) mean that the sum or product is over all positive divisors of n, including 1 and n. For example, if n = 12, then ∏d∣12f(d)=f(1)f(2)f(3)f(4)f(6)f(12).

    The notations can be combined: ∑p∣nf(p) and ∏p∣nf(p) mean that the sum or product is over all prime divisors of n. For example, if n = 18, then ∑p∣18f(p)=f(2)+f(3), and similarly ∑pk∣nf(pk) and ∏pk∣nf(pk) mean that the sum or product is over all prime powers dividing n. For example, if n = 24, then ∏pk∣24f(pk)=f(2)f(3)f(4)f(8).

    Ω(n), ω(n), νp(n) – prime power decomposition

    edit edit source

    The fundamental theorem of arithmetic states that any positive integer n can be represented uniquely as a product of powers of primes: n=p1a1⋯pkak where p1 < p2 < ... < pk are primes and the 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 the p-adic valuation νp(n) to be the exponent of the highest power of the prime p that divides n. That is, if p is one of the pi then νp(n) = ai, otherwise it is zero. Then n=∏ppνp(n).

    In terms of the above the prime omega functions ω and Ω are defined by

    ω(n) = k, Ω(n) = a1 + a2 + ... + ak.

    To avoid repetition, formulas for the functions listed in this article are, whenever possible, given in terms of n and the corresponding pi, ai, ω, and Ω.

    Multiplicative functions

    edit edit source

    σk(n), τ(n), d(n) – divisor sums

    edit edit source

    σk(n) is the sum of the kth powers of the positive divisors of n, including 1 and n, where k is a complex number.

    σ1(n), the sum of the (positive) divisors of n, is usually denoted by σ(n).

    Since a positive number to the zero power is one, σ0(n) is therefore the number of (positive) divisors of n; it is usually denoted by d(n) or τ(n) (for the German Teiler = divisors).

    σk(n)=∏i=1ω(n)pi(ai+1)k−1pik−1=∏i=1ω(n)(1+pik+pi2k+⋯+piaik).

    Setting k = 0 in the second product gives τ(n)=d(n)=(1+a1)(1+a2)⋯(1+aω(n)).

    φ(n) – Euler totient function

    edit edit source

    φ(n), the Euler totient function, is the number of positive integers not greater than n that are coprime to n. φ(n)=n∏p∣n(1−1p)=n(p1−1p1)(p2−1p2)⋯(pω(n)−1pω(n)).

    Jk(n) – Jordan totient function

    edit edit source

    Jk(n), the Jordan totient function, is the number of k-tuples of positive integers all less than or equal to n that form a coprime (k + 1)-tuple together with n. It is a generalization of Euler's totient, φ(n) = J1(n). Jk(n)=nk∏p∣n(1−1pk)=nk(p1k−1p1k)(p2k−1p2k)⋯(pω(n)k−1pω(n)k).

    μ(n) – Möbius function

    edit edit source

    μ(n), the Möbius function, is important because of the Möbius inversion formula. See § Dirichlet convolution, below. μ(n)={(−1)ω(n)=(−1)Ω(n)if ω(n)=Ω(n)0if ω(n)≠Ω(n).

    This implies that μ(1) = 1. (Because Ω(1) = ω(1) = 0.)

    τ(n) – Ramanujan tau function

    edit edit source

    τ(n), the Ramanujan tau function, is defined by its generating function identity: ∑n≥1τ(n)qn=q∏n≥1(1−qn)24.

    Although it is hard to say exactly what "arithmetical property of n" it "expresses",[7] (τ(n) is (2π)−12 times the nth Fourier coefficient in the q-expansion of the modular discriminant function)[8] it is included among the arithmetical functions because it is multiplicative and it occurs in identities involving certain σk(n) and rk(n) functions (because these are also coefficients in the expansion of modular forms).

    cq(n) – Ramanujan's sum

    edit edit source

    cq(n), Ramanujan's sum, is the sum of the nth powers of the primitive qth roots of unity: cq(n)=∑gcd⁡(a,q)=11≤a≤qe2πiaqn.

    Even though it is defined as a sum of complex numbers (irrational for most values of q), it is an integer. For a fixed value of n it is multiplicative in q:

    If q and r are coprime, then cq(n)cr(n)=cqr(n).

    ψ(n) – Dedekind psi function

    edit edit source

    The Dedekind psi function, used in the theory of modular functions, is defined by the formula ψ(n)=n∏p|n(1+1p).

    Completely multiplicative functions

    edit edit source

    λ(n) – Liouville function

    edit edit source

    λ(n), the Liouville function, is defined by λ(n)=(−1)Ω(n).

    χ(n) – characters

    edit edit source

    All Dirichlet characters χ(n) are completely multiplicative. Two characters have special notations:

    The principal character (mod n) is denoted by χ0(a) (or χ1(a)). It is defined as χ0(a)={1if gcd⁡(a,n)=1,0if gcd⁡(a,n)≠1.

    The quadratic character (mod n) is denoted by the Jacobi symbol for odd n (it is not defined for even n): (an)=(ap1)a1(ap2)a2⋯(apω(n))aω(n).

    In this formula (ap) is the Legendre symbol, defined for all integers a and all odd primes p by (ap)={0if a≡0(modp),+1if a≢0(modp) and for some integer x,a≡x2(modp)−1if there is no such x.

    Following the normal convention for the empty product, (a1)=1.

    Additive functions

    edit edit source

    ω(n) – distinct prime divisors

    edit edit source

    ω(n), defined above as the number of distinct primes dividing n, is additive (see Prime omega function).

    Completely additive functions

    edit edit source

    Ω(n) – prime divisors

    edit edit source

    Ω(n), defined above as the number of prime factors of n counted with multiplicities, is completely additive (see Prime omega function).

    νp(n) – p-adic valuation of an integer n

    edit edit source

    For a fixed prime p, νp(n), defined above as the exponent of the largest power of p dividing n, is completely additive.

    Logarithmic derivative

    edit edit source

    ld⁡(n)=D(n)n=∑p primep∣nvp(n)p, where D(n) is the arithmetic derivative.

    Neither multiplicative nor additive

    edit edit source

    π(x), Π(x), ϑ(x), ψ(x) – prime-counting functions

    edit edit source

    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 the prime number theorem. They are summation functions (see the main section just below) of arithmetic functions which are neither multiplicative nor additive.

    π(x), the prime-counting function, is the number of primes not exceeding x. It is the summation function of the characteristic function of the prime numbers. π(x)=∑p≤x1

    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 the kth power of some prime number, and the value 0 on other integers. Π(x)=∑pk≤x1k.

    ϑ(x) and ψ(x), the Chebyshev functions, are defined as sums of the natural logarithms of the primes not exceeding x. ϑ(x)=∑p≤xlog⁡p, ψ(x)=∑pk≤xlog⁡p.

    The second Chebyshev function ψ(x) is the summation function of the von Mangoldt function just below.

    Λ(n) – von Mangoldt function

    edit edit source

    Λ(n), the von Mangoldt function, is 0 unless the argument n is a prime power pk, in which case it is the natural logarithm of the prime p: Λ(n)={log⁡pif n=2,3,4,5,7,8,9,11,13,16,…=pk is a prime power0if n=1,6,10,12,14,15,18,20,21,… is not a prime power.

    p(n) – partition function

    edit edit source

    p(n), the partition function, is the number of ways of representing 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)=|{(a1,a2,…ak):0<a1≤a2≤⋯≤ak∧n=a1+a2+⋯+ak}|.

    λ(n) – Carmichael function

    edit edit source

    λ(n), the Carmichael function, is the smallest positive number such that aλ(n)≡1(modn)   for all a coprime to n. Equivalently, it is the least common multiple of the orders of the elements of the multiplicative group of integers modulo n.

    For powers of odd primes and for 2 and 4, λ(n) is equal to the Euler totient function of n; for powers of 2 greater than 4 it is equal to one half of the Euler totient function of n: λ(n)={ϕ(n)if n=2,3,4,5,7,9,11,13,17,19,23,25,27,…12ϕ(n)if n=8,16,32,64,… and for general n it is the least common multiple of λ of each of the prime power factors of n: λ(p1a1p2a2…pω(n)aω(n))=lcm⁡[λ(p1a1),λ(p2a2),…,λ(pω(n)aω(n))].

    h(n) – class number

    edit edit source

    h(n), the class number function, is the order of the ideal class group of an algebraic extension of the rationals with discriminant n. The notation is ambiguous, as there are in general many extensions with the same discriminant. See quadratic field and cyclotomic field for classical examples.

    rk(n) – sum of k squares

    edit edit source

    rk(n) is the number of ways n can be represented as the sum of k squares, where representations that differ only in the order of the summands or in the signs of the square roots are counted as different. rk(n)=|{(a1,a2,…,ak):n=a12+a22+⋯+ak2}|

    D(n) – Arithmetic derivative

    edit edit source

    Using the Heaviside notation for the derivative, the arithmetic derivative D(n) is a function such that

    Summation functions

    edit edit source

    Given an arithmetic function a(n), its summation function A(x) is defined by A(x):=∑n≤xa(n). A can be regarded as a function of a real variable. Given a positive integer m, A is constant along open intervals m < x < m + 1, and has a jump discontinuity at each integer for which a(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: A0(m):=12(∑n<ma(n)+∑n≤ma(n))=A(m)−12a(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 find asymptotic behaviour for the summation function for large x.

    A classical example of this phenomenon[9] is given by the divisor summatory function, the summation function of d(n), the number of divisors of n: lim infn→∞d(n)=2 lim supn→∞log⁡d(n)log⁡log⁡nlog⁡n=log⁡2 limn→∞d(1)+d(2)+⋯+d(n)log⁡(1)+log⁡(2)+⋯+log⁡(n)=1.

    An average order of an arithmetic function is some simpler or better-understood function which has the same summation function asymptotically, and hence takes the same values "on average". We say that g is an average order of f if ∑n≤xf(n)∼∑n≤xg(n)

    as x tends to infinity. The example above shows that d(n) has the average order log(n).[10]

    Dirichlet convolution

    edit edit source

    Given an arithmetic function a(n), let Fa(s), for complex s, be the function defined by the corresponding Dirichlet series (where it converges):[11] Fa(s):=∑n=1∞a(n)ns. Fa(s) is called a generating function of a(n). The simplest such series, corresponding to the constant function a(n) = 1 for all n, is ζ(s) the Riemann zeta function.

    The generating function of the Möbius function is the inverse of the zeta function: ζ(s)∑n=1∞μ(n)ns=1,ℜs>1.

    Consider two arithmetic functions a and b and their respective generating functions Fa(s) and Fb(s). The product Fa(s)Fb(s) can be computed as follows: Fa(s)Fb(s)=(∑m=1∞a(m)ms)(∑n=1∞b(n)ns).

    It is a straightforward exercise to show that if c(n) is defined by c(n):=∑ij=na(i)b(j)=∑i∣na(i)b(ni), then Fc(s)=Fa(s)Fb(s).

    This function c is called the Dirichlet convolution of a and b, and is denoted by a∗b.

    A particularly important case is convolution with the constant function a(n) = 1 for all n, corresponding to multiplying the generating function by the zeta function: g(n)=∑d∣nf(d).

    Multiplying by the inverse of the zeta function gives the Möbius inversion formula: f(n)=∑d∣nμ(nd)g(d).

    If f is multiplicative, then so is g. If f is completely multiplicative, then g is multiplicative, but may or may not be completely multiplicative.

    Relations among the functions

    edit edit source

    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 page divisor sum identities contains many more generalized and related examples of identities involving arithmetic functions.

    Here are a few examples:

    Dirichlet convolutions

    edit edit source
    ∑δ∣nμ(δ)=∑δ∣nλ(nδ)|μ(δ)|={1if n=10if n≠1     where λ is the Liouville function.[12]
    ∑δ∣nφ(δ)=n.      [13]
    φ(n)=∑δ∣nμ(nδ)δ=n∑δ∣nμ(δ)δ.       Möbius inversion
    ∑δ∣nJk(δ)=nk.      [14]
    Jk(n)=∑δ∣nμ(nδ)δk=nk∑δ∣nμ(δ)δk.       Möbius inversion
    ∑δ∣nδsJr(δ)Js(nδ)=Jr+s(n)      [15]
    ∑δ∣nφ(δ)d(nδ)=σ(n).      [16][17]
    ∑δ∣n|μ(δ)|=2ω(n).      [18]
    |μ(n)|=∑δ∣nμ(nδ)2ω(δ).       Möbius inversion
    ∑δ∣n2ω(δ)=d(n2).      
    2ω(n)=∑δ∣nμ(nδ)d(δ2).       Möbius inversion
    ∑δ∣nd(δ2)=d2(n).      
    d(n2)=∑δ∣nμ(nδ)d2(δ).       Möbius inversion
    ∑δ∣nd(nδ)2ω(δ)=d2(n).      
    ∑δ∣nλ(δ)={1 if n is a square 0 if n is not square.     where λ is the Liouville function.
    ∑δ∣nΛ(δ)=log⁡n.      [19]
    Λ(n)=∑δ∣nμ(nδ)log⁡(δ).       Möbius inversion

    Sums of squares

    edit edit source

    For all k≥4,rk(n)>0.     (Lagrange's four-square theorem).

    r2(n)=4∑d∣n(−4d),[20]

    where the Kronecker symbol has the values

    (−4n)={+1if n≡1(mod4)−1if n≡3(mod4)0if n is even.

    There is a formula for r3 in the section on class numbers below. r4(n)=8∑4∤dd∣nd=8(2+(−1)n)∑2∤dd∣nd={8σ(n)if n is odd 24σ(n2ν)if n is even , where ν = ν2(n).    [21][22][23] r6(n)=16∑d∣nχ(nd)d2−4∑d∣nχ(d)d2, where χ(n)=(−4n).[24]

    Define the function σk*(n) as[25] σk∗(n)=(−1)n∑d∣n(−1)ddk={∑d∣ndk=σk(n)if n is odd ∑2∣dd∣ndk−∑2∤dd∣ndkif n is even.

    That is, if n is odd, σk*(n) is the sum of the kth powers of the divisors of n, that is, σk(n), and if n is even it is the sum of the kth powers of the even divisors of n minus the sum of the kth powers of the odd divisors of n.

    r8(n)=16σ3∗(n).    [24][26]

    Adopt the convention that Ramanujan's τ(x) = 0 if x is not an integer.

    r24(n)=16691σ11∗(n)+128691{(−1)n−1259τ(n)−512τ(n2)}    [27]

    Divisor sum convolutions

    edit edit source

    Here "convolution" does not mean "Dirichlet convolution" but instead refers to the formula for the coefficients of the product of two power series:

    (∑n=0∞anxn)(∑n=0∞bnxn)=∑i=0∞∑j=0∞aibjxi+j=∑n=0∞(∑i=0naibn−i)xn=∑n=0∞cnxn.

    The sequence cn=∑i=0naibn−i is called the convolution or the Cauchy product of the sequences an and bn.
    These formulas may be proved analytically (see Eisenstein series) or by elementary methods.[28]

    σ3(n)=15{6nσ1(n)−σ1(n)+12∑0<k<nσ1(k)σ1(n−k)}.    [29]
    σ5(n)=121{10(3n−1)σ3(n)+σ1(n)+240∑0<k<nσ1(k)σ3(n−k)}.    [30]
    σ7(n)=120{21(2n−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).    [30][31]
    σ9(n)=111{10(3n−2)σ7(n)+σ1(n)+480∑0<k<nσ1(k)σ7(n−k)}=111{21σ5(n)−10σ3(n)+5040∑0<k<nσ3(k)σ5(n−k)}.    [29][32]
    τ(n)=65756σ11(n)+691756σ5(n)−6913∑0<k<nσ5(k)σ5(n−k),     where τ(n) is Ramanujan's function.    [33][34]

    Since σk(n) (for natural number k) and τ(n) are integers, the above formulas can be used to prove congruences[35] for the functions. See Ramanujan tau function for some examples.

    Extend the domain of the partition function by setting p(0) = 1.

    p(n)=1n∑1≤k≤nσ(k)p(n−k).    [36]   This recurrence can be used to compute p(n).
    edit edit source

    Peter Gustav Lejeune Dirichlet discovered formulas that relate the class number h of quadratic number fields to the Jacobi symbol.[37]

    An integer D is called a fundamental discriminant if it is the discriminant of a quadratic number field. This is equivalent to D ≠ 1 and either a) D is squarefree and D ≡ 1 (mod 4) or b) D ≡ 0 (mod 4), D/4 is squarefree, and D/4 ≡ 2 or 3 (mod 4).[38]

    Extend the Jacobi symbol to accept even numbers in the "denominator" by defining the Kronecker symbol: (a2)={0 if a is even(−1)a2−18 if a is odd. 

    Then if D < −4 is a fundamental discriminant[39][40] h(D)=1D∑r=1|D|r(Dr)=12−(D2)∑r=1|D|/2(Dr).

    There is also a formula relating r3 and h. Again, let D be a fundamental discriminant, D < −4. Then[41] r3(|D|)=12(1−(D2))h(D).

    edit edit source

    Let Hn=1+12+13+⋯+1n   be the nth harmonic number. Then

    σ(n)≤Hn+eHnlog⁡Hn   is true for every natural number n if and only if the Riemann hypothesis is true.    [42]

    The Riemann hypothesis is also equivalent to the statement that, for all n > 5040, σ(n)<eγnlog⁡log⁡n (where γ is the Euler–Mascheroni constant). This is Robin's theorem.

    ∑pνp(n)=Ω(n).
    ψ(x)=∑n≤xΛ(n).    [43]
    Π(x)=∑n≤xΛ(n)log⁡n.    [44]
    eθ(x)=∏p≤xp.    [45]
    eψ(x)=lcm⁡[1,2,…,⌊x⌋].    [46]

    Menon's identity

    edit edit source

    In 1965 P Kesava Menon proved[47] ∑gcd⁡(k,n)=11≤k≤ngcd⁡(k−1,n)=φ(n)d(n).

    This has been generalized by a number of mathematicians. For example,

    • B. Sury[48] ∑gcd⁡(k1,n)=11≤k1,k2,…,ks≤ngcd⁡(k1−1,k2,…,ks,n)=φ(n)σs−1(n).
    • N. Rao[49] ∑gcd⁡(k1,k2,…,ks,n)=11≤k1,k2,…,ks≤ngcd⁡(k1−a1,k2−a2,…,ks−as,n)s=Js(n)d(n), where a1, a2, ..., as are integers, gcd(a1, a2, ..., as, n) = 1.
    • László Fejes Tóth[50] ∑gcd⁡(k,m)=11≤k≤mgcd⁡(k2−1,m1)gcd⁡(k2−1,m2)=φ(n)∑d2∣m2d1∣m1φ(gcd⁡(d1,d2))2ω(lcm⁡(d1,d2)), where m1 and m2 are odd, m = lcm(m1, m2).

    In fact, if f is any arithmetical function[51][52] ∑gcd⁡(k,n)=11≤k≤nf(gcd⁡(k−1,n))=φ(n)∑d∣n(μ∗f)(d)φ(d), where ∗ stands for Dirichlet convolution.

    Miscellaneous

    edit edit source

    Let m and n be distinct, odd, and positive. Then the Jacobi symbol satisfies the law of quadratic reciprocity: (mn)(nm)=(−1)(m−1)(n−1)/4.

    Let D(n) be the arithmetic derivative. Then the logarithmic derivative D(n)n=∑p primep∣nvp(n)p. See Arithmetic derivative for details.

    Let λ(n) be Liouville's function. Then

    |λ(n)|μ(n)=λ(n)|μ(n)|=μ(n),     and
    λ(n)μ(n)=|μ(n)|=μ2(n).    

    Let λ(n) be Carmichael's function. Then

    λ(n)∣ϕ(n).     Further,
    λ(n)=ϕ(n) if and only if n={1,2,4;3,5,7,9,11,… (that is, pk, where p is an odd prime);6,10,14,18,… (that is, 2pk, where p is an odd prime).

    See Multiplicative group of integers modulo n and Primitive root modulo n.  

    2ω(n)≤d(n)≤2Ω(n).    [53][54]
    6π2<ϕ(n)σ(n)n2<1.    [55]
    cq(n)=μ(qgcd⁡(q,n))ϕ(qgcd⁡(q,n))ϕ(q)=∑δ∣gcd⁡(q,n)μ(qδ)δ.    [56]     Note that  ϕ(q)=∑δ∣qμ(qδ)δ.    [57]
    cq(1)=μ(q).
    cq(q)=ϕ(q).
    ∑δ∣nd3(δ)=(∑δ∣nd(δ))2.    [58]   Compare this with 13 + 23 + 33 + ... + n3 = (1 + 2 + 3 + ... + n)2
    d(uv)=∑δ∣gcd⁡(u,v)μ(δ)d(uδ)d(vδ).    [59]
    σk(u)σk(v)=∑δ∣gcd⁡(u,v)δkσk(uvδ2).    [60]
    τ(u)τ(v)=∑δ∣gcd⁡(u,v)δ11τ(uvδ2),     where τ(n) is Ramanujan's function.    [61]

    First 100 values of some arithmetic functions

    edit edit source
    n factorization φ(n) ω(n) Ω(n) λ(n) μ(n) Λ(n) π(n) σ0(n) σ1(n) σ2(n) r2(n) r3(n) r4(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) r2(n) r3(n) r4(n)

    Notes

    edit edit source
    1. ^ Long (1972, p. 151) Wikipedia revision 1378437540, retrieved 2026-11-21
    2. ^ Pettofrezzo & Byrkit (1970, p. 58) Wikipedia revision 1378437540, retrieved 2026-11-21
    3. ^ Niven & Zuckerman, 4.2. Wikipedia revision 1378437540, retrieved 2026-11-21
    4. ^ Nagell, I.9. Wikipedia revision 1378437540, retrieved 2026-11-21
    5. ^ Bateman & Diamond, 2.1. Wikipedia revision 1378437540, retrieved 2026-11-21
    6. ^ Hardy & Wright, intro. to Ch. XVI Wikipedia revision 1378437540, retrieved 2026-11-21
    7. ^ Hardy, Ramanujan, § 10.2 Wikipedia revision 1378437540, retrieved 2026-11-21
    8. ^ Apostol, Modular Functions ..., § 1.15, Ch. 4, and ch. 6 Wikipedia revision 1378437540, retrieved 2026-11-21
    9. ^ Hardy & Wright, §§ 18.1–18.2 Wikipedia revision 1378437540, retrieved 2026-11-21
    10. ^ 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. Wikipedia revision 1378437540, retrieved 2026-11-21
    11. ^ 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. Wikipedia revision 1378437540, retrieved 2026-11-21
    12. ^ Hardy & Wright, Thm. 263 Wikipedia revision 1378437540, retrieved 2026-11-21
    13. ^ Hardy & Wright, Thm. 63 Wikipedia revision 1378437540, retrieved 2026-11-21
    14. ^ see references at Jordan's totient function Wikipedia revision 1378437540, retrieved 2026-11-21
    15. ^ Holden et al. in external links The formula is Gegenbauer's Wikipedia revision 1378437540, retrieved 2026-11-21
    16. ^ Hardy & Wright, Thm. 288–290 Wikipedia revision 1378437540, retrieved 2026-11-21
    17. ^ Dineva in external links, prop. 4 Wikipedia revision 1378437540, retrieved 2026-11-21
    18. ^ Hardy & Wright, Thm. 264 Wikipedia revision 1378437540, retrieved 2026-11-21
    19. ^ Hardy & Wright, Thm. 296 Wikipedia revision 1378437540, retrieved 2026-11-21
    20. ^ Hardy & Wright, Thm. 278 Wikipedia revision 1378437540, retrieved 2026-11-21
    21. ^ Hardy & Wright, Thm. 386 Wikipedia revision 1378437540, retrieved 2026-11-21
    22. ^ Hardy, Ramanujan, eqs 9.1.2, 9.1.3 Wikipedia revision 1378437540, retrieved 2026-11-21
    23. ^ Koblitz, Ex. III.5.2 Wikipedia revision 1378437540, retrieved 2026-11-21
    24. ^ a b Hardy & Wright, § 20.13 Wikipedia revision 1378437540, retrieved 2026-11-21
    25. ^ Hardy, Ramanujan, § 9.7 Wikipedia revision 1378437540, retrieved 2026-11-21
    26. ^ Hardy, Ramanujan, § 9.13 Wikipedia revision 1378437540, retrieved 2026-11-21
    27. ^ Hardy, Ramanujan, § 9.17 Wikipedia revision 1378437540, retrieved 2026-11-21
    28. ^ Williams, ch. 13; Huard, et al. (external links). Wikipedia revision 1378437540, retrieved 2026-11-21
    29. ^ a b Ramanujan, On Certain Arithmetical Functions, Table IV; Papers, p. 146 Wikipedia revision 1378437540, retrieved 2026-11-21
    30. ^ a b Koblitz, ex. III.2.8 Wikipedia revision 1378437540, retrieved 2026-11-21
    31. ^ Koblitz, ex. III.2.3 Wikipedia revision 1378437540, retrieved 2026-11-21
    32. ^ Koblitz, ex. III.2.2 Wikipedia revision 1378437540, retrieved 2026-11-21
    33. ^ Koblitz, ex. III.2.4 Wikipedia revision 1378437540, retrieved 2026-11-21
    34. ^ Apostol, Modular Functions ..., Ex. 6.10 Wikipedia revision 1378437540, retrieved 2026-11-21
    35. ^ Apostol, Modular Functions..., Ch. 6 Ex. 10 Wikipedia revision 1378437540, retrieved 2026-11-21
    36. ^ G.H. Hardy, S. Ramannujan, Asymptotic Formulæ in Combinatory Analysis, § 1.3; in Ramannujan, Papers p. 279 Wikipedia revision 1378437540, retrieved 2026-11-21
    37. ^ Landau, p. 168, credits Gauss as well as Dirichlet Wikipedia revision 1378437540, retrieved 2026-11-21
    38. ^ Cohen, Def. 5.1.2 Wikipedia revision 1378437540, retrieved 2026-11-21
    39. ^ Cohen, Corr. 5.3.13 Wikipedia revision 1378437540, retrieved 2026-11-21
    40. ^ see Edwards, § 9.5 exercises for more complicated formulas. Wikipedia revision 1378437540, retrieved 2026-11-21
    41. ^ Cohen, Prop 5.3.10 Wikipedia revision 1378437540, retrieved 2026-11-21
    42. ^ See Divisor function. Wikipedia revision 1378437540, retrieved 2026-11-21
    43. ^ Hardy & Wright, eq. 22.1.2 Wikipedia revision 1378437540, retrieved 2026-11-21
    44. ^ See prime-counting functions. Wikipedia revision 1378437540, retrieved 2026-11-21
    45. ^ Hardy & Wright, eq. 22.1.1 Wikipedia revision 1378437540, retrieved 2026-11-21
    46. ^ Hardy & Wright, eq. 22.1.3 Wikipedia revision 1378437540, retrieved 2026-11-21
    47. ^ László Tóth, Menon's Identity and Arithmetical Sums ..., eq. 1 Wikipedia revision 1378437540, retrieved 2026-11-21
    48. ^ Tóth, eq. 5 Wikipedia revision 1378437540, retrieved 2026-11-21
    49. ^ Tóth, eq. 3 Wikipedia revision 1378437540, retrieved 2026-11-21
    50. ^ Tóth, eq. 35 Wikipedia revision 1378437540, retrieved 2026-11-21
    51. ^ Tóth, eq. 2 Wikipedia revision 1378437540, retrieved 2026-11-21
    52. ^ Tóth states that Menon proved this for multiplicative f in 1965 and V. Sita Ramaiah for general f. Wikipedia revision 1378437540, retrieved 2026-11-21
    53. ^ Hardy Ramanujan, eq. 3.10.3 Wikipedia revision 1378437540, retrieved 2026-11-21
    54. ^ Hardy & Wright, § 22.13 Wikipedia revision 1378437540, retrieved 2026-11-21
    55. ^ Hardy & Wright, Thm. 329 Wikipedia revision 1378437540, retrieved 2026-11-21
    56. ^ Hardy & Wright, Thms. 271, 272 Wikipedia revision 1378437540, retrieved 2026-11-21
    57. ^ Hardy & Wright, eq. 16.3.1 Wikipedia revision 1378437540, retrieved 2026-11-21
    58. ^ 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. Wikipedia revision 1378437540, retrieved 2026-11-21
    59. ^ Ramanujan, Some Formulæ in the Analytic Theory of Numbers, eq. (F); Papers p. 134 Wikipedia revision 1378437540, retrieved 2026-11-21
    60. ^ Apostol, Modular Functions ..., ch. 6 eq. 4 Wikipedia revision 1378437540, retrieved 2026-11-21
    61. ^ Apostol, Modular Functions ..., ch. 6 eq. 3 Wikipedia revision 1378437540, retrieved 2026-11-21

    References

    edit edit source

    Further reading

    edit edit source
    • 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
    edit edit source Classes of natural numbers 3-dimensional 4-dimensional P-adic numbers-related Digit-composition related Digit-permutation related Divisor-related Other

    Text derived from https://en.wikipedia.org/w/index.php?oldid=1378437540 under CC BY-SA 4.0; modifications have been made.

    Words in each sectionFirst 100 values of som…First 100 values of some arithmetic functionsFirst 100 values of some arithmetic functions: 1,700 words1,700Relations among the fun…Relations among the functionsRelations among the functions: 1,659 words1,659NotesNotesNotes: 772 words772Neither multiplicative …Neither multiplicative nor additiveNeither multiplicative nor additive: 635 words635Multiplicative functionsMultiplicative functionsMultiplicative functions: 503 words503Summation functionsSummation functionsSummation functions: 283 words283Dirichlet convolutionDirichlet convolutionDirichlet convolution: 268 words268NotationNotationNotation: 211 words211Ω(n), ω(n), νp(n) – pri…Ω(n), ω(n), νp(n) – prime power decompositionΩ(n), ω(n), νp(n) – prime power decomposition: 174 words174Completely multiplicati…Completely multiplicative functionsCompletely multiplicative functions: 157 words157Multiplicative and addi…Multiplicative and additive functionsMultiplicative and additive functions: 115 words115Completely additive fun…Completely additive functionsCompletely additive functions: 89 words89Further readingFurther readingFurther reading: 47 words47Additive functionsAdditive functionsAdditive functions: 27 words27
    Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

    Provenance

    snapshot enwiki-001378437540 · captured 2026-10-04 · ledger · version history

    Cite this page as: encyclopegia.org, “Arithmetic function”, snapshot enwiki-001378437540. https://encyclopegia.org/a/arithmetic-function