{
  "id": "enwiki-001378437540",
  "slug": "arithmetic-function",
  "title": "Arithmetic function",
  "qid": "",
  "lead": "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. Hardy & Wright include in their definition the requirement that an arithmetical function \"expresses some arithmetical property of n\". 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.",
  "body": "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. Hardy & Wright include in their definition the requirement that an arithmetical function \"expresses some arithmetical property of n\". 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. completely additive if a(mn) = a(m) + a(n) for all natural numbers m and n; completely multiplicative if a(1) = 1 and a(mn) = a(m)a(n) for all natural numbers m and n; 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. In this article, \\sum_p f(p) and \\prod_p f(p) mean that the sum or product is over all prime numbers: \\sum_p f(p) = f(2) + f(3) + f(5) + \\cdots and \\prod_p f(p)= f(2)f(3)f(5)\\cdots. Similarly, \\sum_{p^k} f(p^k) and \\prod_{p^k} f(p^k) mean that the sum or product is over all prime powers with strictly positive exponent (so is not included): \\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 \\sum_{d\\mid n} f(d) and \\prod_{d\\mid n} f(d) mean that the sum or product is over all positive divisors of n, including 1 and n. For example, if , then \\prod_{d\\mid 12} f(d) = f(1)f(2) f(3) f(4) f(6) f(12). The notations can be combined: \\sum_{p\\mid n} f(p) and \\prod_{p\\mid n} f(p) mean that the sum or product is over all prime divisors of n. For example, if n = 18, then \\sum_{p\\mid 18} f(p) = f(2) + f(3), and similarly \\sum_{p^k\\mid n} f(p^k) and \\prod_{p^k\\mid n} f(p^k) mean that the sum or product is over all prime powers dividing n. For example, if n = 24, then \\prod_{p^k\\mid 24} f(p^k) = f(2) f(3) f(4) f(8). The fundamental theorem of arithmetic states that any positive integer n can be represented uniquely as a product of powers of primes: n = p_1^{a_1}\\cdots p_k^{a_k} where p 1 2 k are primes and the a j 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 p i then ν p (n) = a i , otherwise it is zero. Then n = \\prod_p p^{\\nu_p(n)}. In terms of the above the prime omega functions ω and Ω are defined by To avoid repetition, formulas for the functions listed in this article are, whenever possible, given in terms of n and the corresponding p i , a i , ω, and Ω. 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). \\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). Setting k = 0 in the second product gives \\tau(n) = d(n) = (1 + a_{1})(1+a_{2})\\cdots(1+a_{\\omega(n)}). \\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) = n^k \\prod_{p\\mid n} \\left(1-\\frac{1}{p^k}\\right) = n^k \\left(\\frac{p^k_1 - 1}{p^k_1}\\right)\\left(\\frac{p^k_2 - 1}{p^k_2}\\right) \\cdots \\left(\\frac{p^k_{\\omega(n)} - 1}{p^k_{\\omega(n)}}\\right) . === μ(n) – Möbius function=== μ(n), the Möbius function, is important because of the Möbius inversion formula. See , below. \\mu(n)=\\begin{cases} (-1)^{\\omega(n)}=(-1)^{\\Omega(n)} &\\text{if }\\; \\omega(n) = \\Omega(n)\\\\ 0&\\text{if }\\;\\omega(n) \\ne \\Omega(n). \\end{cases} This implies that μ(1) = 1. (Because Ω(1) = ω(1) = 0.) \\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 of n\" it \"expresses\", (τ(n) is (2π) −12 times the nth Fourier coefficient in the q-expansion of the modular discriminant function) it is included among the arithmetical functions because it is multiplicative and it occurs in identities involving certain σ k (n) and r k (n) functions (because these are also coefficients in the expansion of modular forms). c_q(n) = \\sum_{\\stackrel{1\\le a\\le 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 of q), it is an integer. For a fixed value of n it is multiplicative in q: If q and r are coprime, then c_q(n)c_r(n)=c_{qr}(n). \\psi(n) = n \\prod_{p|n}\\left(1+\\frac{1}{p}\\right). \\lambda (n) = (-1)^{\\Omega(n)}. \\chi_0(a) = \\begin{cases} 1 & \\text{if } \\gcd(a,n) = 1, \\\\ 0 & \\text{if } \\gcd(a,n) \\ne 1. \\end{cases} The quadratic character (mod n) is denoted by the Jacobi symbol for odd n (it is not defined for even n): \\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 (\\tfrac{a}{p}) is the Legendre symbol, defined for all integers a and all odd primes p by \\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, \\left(\\frac{a}{1}\\right) = 1. \\operatorname{ld}(n)=\\frac{D(n)}{n} = \\sum_{\\stackrel{p\\mid n}{p\\text{ prime}}} \\frac {v_p(n)} {p} , where D(n) is the arithmetic derivative. === π(x), Π(x), ϑ(x), ψ(x) – prime-counting functions=== 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. \\pi(x) = \\sum_{p \\le 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 the kth power of some prime number, and the value 0 on other integers. \\Pi(x) = \\sum_{p^k\\le x}\\frac{1}{k}. ϑ(x) and ψ(x), the Chebyshev functions, are defined as sums of the natural logarithms of the primes not exceeding x. \\vartheta(x)=\\sum_{p\\le x} \\log p, \\psi(x) = \\sum_{p^k\\le x} \\log p. The second Chebyshev function ψ(x) is the summation function of the von Mangoldt function just below. \\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) = \\left|\\left\\{ (a_1, a_2,\\dots a_k): 0 \\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} and for general n it is the least common multiple of λ of each of the prime power factors of n: \\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)}}) ]. 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) = 1 if n prime, and D(mn) = m D(n) + D(m) n (the product rule) A(x) := \\sum_{n \\le x} a(n) . A can be regarded as a function of a real variable. Given a positive integer m, A is constant along open intervals m A_0(m) := \\frac 1 2 \\left(\\sum_{n 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 is given by the divisor summatory function, the summation function of d(n), the number of divisors of n: \\liminf_{n\\to\\infty} d(n) = 2 \\limsup_{n\\to\\infty}\\frac{\\log d(n) \\log\\log n}{\\log n} = \\log 2 \\lim_{n\\to\\infty}\\frac{d(1) + d(2)+ \\cdots +d(n)}{\\log(1) + \\log(2)+ \\cdots +\\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 \\sum_{n \\le x} f(n) \\sim \\sum_{n \\le x} g(n) as x tends to infinity. The example above shows that d(n) has the average order log(n). F_a(s) := \\sum_{n=1}^\\infty \\frac{a(n)}{n^s} . F a (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: \\zeta(s)\\,\\sum_{n=1}^\\infty\\frac{\\mu(n)}{n^s}=1, \\;\\;\\Re s >1. Consider two arithmetic functions a and b and their respective generating functions F a (s) and F b (s). The product F a (s)F b (s) can be computed as follows: 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 if c(n) is defined by c(n) := \\sum_{ij = n} a(i)b(j) = \\sum_{i\\mid n}a(i)b\\left(\\frac{n}{i}\\right) , then F_c(s) = F_a(s) F_b(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) = \\sum_{d \\mid n}f(d). Multiplying by the inverse of the zeta function gives the Möbius inversion formula: f(n) = \\sum_{d\\mid n}\\mu\\left(\\frac{n}{d}\\right)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. \\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\\ne1 \\end{cases} &nbsp; &nbsp; where λ is the Liouville function. \\sum_{\\delta\\mid n}\\varphi(\\delta) = n. &nbsp; &nbsp; &nbsp; \\varphi(n) =\\sum_{\\delta\\mid n}\\mu\\left(\\frac{n}{\\delta}\\right)\\delta =\\sum_{\\delta\\mid n}\\mu\\left(\\frac{n}{\\delta}\\right)\\delta^k \\sum_{\\delta\\mid n}\\varphi(\\delta)d\\left(\\frac{n}{\\delta}\\right) = \\sigma(n). &nbsp; &nbsp; &nbsp; \\sum_{\\delta\\mid n}|\\mu(\\delta)| = 2^{\\omega(n)}. &nbsp; &nbsp; &nbsp; |\\mu(n)|=\\sum_{\\delta\\mid n}\\mu\\left(\\frac{n}{\\delta}\\right)2^{\\omega(\\delta)}. &nbsp; &nbsp; &nbsp; Möbius inversion \\sum_{\\delta\\mid n}2^{\\omega(\\delta)}=d(n^2). &nbsp; &nbsp; &nbsp; 2^{\\omega(n)}=\\sum_{\\delta\\mid n}\\mu\\left(\\frac{n}{\\delta}\\right)d(\\delta^2). &nbsp; &nbsp; &nbsp; Möbius inversion \\sum_{\\delta\\mid n}d(\\delta^2)=d^2(n). &nbsp; &nbsp; &nbsp; d(n^2)=\\sum_{\\delta\\mid n}\\mu\\left(\\frac{n}{\\delta}\\right)d^2(\\delta). &nbsp; &nbsp; &nbsp; Möbius inversion \\sum_{\\delta\\mid n}d\\left(\\frac{n}{\\delta}\\right)2^{\\omega(\\delta)}=d^2(n). &nbsp; &nbsp; &nbsp; \\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} &nbsp; &nbsp; where λ is the Liouville function. \\sum_{\\delta\\mid n}\\Lambda(\\delta) = \\log n. &nbsp; &nbsp; &nbsp; \\Lambda(n)=\\sum_{\\delta\\mid n}\\mu\\left(\\frac{n}{\\delta}\\right)\\log(\\delta). &nbsp; &nbsp; &nbsp; Möbius inversion r_2(n) = 4\\sum_{d\\mid n}\\left(\\frac{-4}{d}\\right), where the Kronecker symbol has the values \\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 for r 3 in the section on class numbers below. 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}, where . &nbsp; &nbsp; 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, where \\chi(n) = \\left(\\frac{-4}{n}\\right). Define the function as \\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, if n is odd, is the sum of the kth powers of the divisors of n, that is, 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. r_8(n) = 16\\sigma_3^*(n). &nbsp; &nbsp; Adopt the convention that Ramanujan's if x is not an integer. 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\\} &nbsp; &nbsp; \\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 sequence c_n = \\sum_{i=0}^n a_i b_{n-i} is called the convolution or the Cauchy product of the sequences a n and b n . These formulas may be proved analytically (see Eisenstein series) or by elementary methods. \\sigma_3(n) = \\frac{1}{5}\\left\\{6n\\sigma_1(n)-\\sigma_1(n) + 12\\sum_{0 &nbsp; &nbsp; \\sigma_5(n) = \\frac{1}{21}\\left\\{10(3n-1)\\sigma_3(n)+\\sigma_1(n) + 240\\sum_{0 &nbsp; &nbsp; \\begin{align} \\sigma_7(n) &=\\frac{1}{20}\\left\\{21(2n-1)\\sigma_5(n)-\\sigma_1(n) + 504\\sum_{0 &nbsp; &nbsp; \\begin{align} \\sigma_9(n) &= \\frac{1}{11}\\left\\{10(3n-2)\\sigma_7(n)+\\sigma_1(n) + 480\\sum_{0 &nbsp; &nbsp; \\tau(n) = \\frac{65}{756}\\sigma_{11}(n) + \\frac{691}{756}\\sigma_{5}(n) - \\frac{691}{3}\\sum_{0 &nbsp; &nbsp; where τ(n) is Ramanujan's function. &nbsp; &nbsp; Since σ k (n) (for natural number k) and τ(n) are integers, the above formulas can be used to prove congruences for the functions. See Ramanujan tau function for some examples. Extend the domain of the partition function by setting p(n)=\\frac{1}{n}\\sum_{1\\le k\\le n}\\sigma(k)p(n-k). &nbsp; &nbsp; &nbsp; This recurrence can be used to compute p(n). \\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 if D \\begin{align} h(D) & = \\frac{1}{D} \\sum_{r=1}^ r\\left(\\frac{D}{r}\\right)\\\\ & = \\frac{1}{2-\\left(\\tfrac{D}{2}\\right)} \\sum_{r=1}^",
  "categories": [
    "107141658",
    "10730568",
    "11060667",
    "22969692",
    "22969693",
    "23118434",
    "23603337",
    "24623845",
    "29176345"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1378437540",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1791114109.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001378437540",
    "type": "webpage",
    "title": "Arithmetic function",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/arithmetic-function",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001378437540",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1378437540",
    "note": "Immutable snapshot enwiki-001378437540"
  }
}