Additive function

---

title: "Additive function" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["arithmetic-functions", "additive-functions"] description: "Function that can be written as a sum over prime factors" topic_path: "general/arithmetic-functions" source: "https://en.wikipedia.org/wiki/Additive_function" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Function that can be written as a sum over prime factors ::

::callout[type=note]

::

In number theory, an definition-additive_function-number_theoryadditive function is an arithmetic function f(n) of the positive integer variable n such that whenever a and b are coprime, the function applied to the product ab is the sum of the values of the function applied to a and b: f(a b) = f(a) + f(b).

Completely additive

An additive function f(n) is said to be completely additive if f(a b) = f(a) + f(b) holds for all positive integers a and b, even when they are not coprime. Totally additive is also used in this sense by analogy with totally multiplicative functions. If f is a completely additive function then f(1) = 0.

Every completely additive function is additive, but not vice versa.

Examples

Examples of arithmetic functions which are completely additive are:

• The restriction of the logarithmic function to \N.
• The multiplicity of a prime factor p in n, that is the largest exponent m for which pm divides n.
• Integer logarithm a0(n) – the sum of primes dividing n counting multiplicity, sometimes called sopfr(n), the potency of n or the integer logarithm of n . For example:

::a0(4) = 2 + 2 = 4 ::a0(20) = a0(22 · 5) = 2 + 2 + 5 = 9 ::a0(27) = 3 + 3 + 3 = 9 ::a0(144) = a0(24 · 32) = a0(24) + a0(32) = 8 + 6 = 14 ::a0(2000) = a0(24 · 53) = a0(24) + a0(53) = 8 + 15 = 23 ::a0(2003) = 2003 ::a0(54,032,858,972,279) = 1240658 ::a0(54,032,858,972,302) = 1780417 ::a0(20,802,650,704,327,415) = 1240681

• The function Ω(n), defined as the total number of prime factors of n, counting multiple factors multiple times, sometimes called the "Big Omega function" . For example;

::Ω(1) = 0, since 1 has no prime factors ::Ω(4) = 2 ::Ω(16) = Ω(2·2·2·2) = 4 ::Ω(20) = Ω(2·2·5) = 3 ::Ω(27) = Ω(3·3·3) = 3 ::Ω(144) = Ω(24 · 32) = Ω(24) + Ω(32) = 4 + 2 = 6 ::Ω(2000) = Ω(24 · 53) = Ω(24) + Ω(53) = 4 + 3 = 7 ::Ω(2001) = 3 ::Ω(2002) = 4 ::Ω(2003) = 1 ::Ω(54,032,858,972,279) = Ω(11 ⋅ 19932 ⋅ 1236661) = 4 ::Ω(54,032,858,972,302) = Ω(2 ⋅ 72 ⋅ 149 ⋅ 2081 ⋅ 1778171) = 6 ::Ω(20,802,650,704,327,415) = Ω(5 ⋅ 7 ⋅ 112 ⋅ 19932 ⋅ 1236661) = 7.

Examples of arithmetic functions which are additive but not completely additive are:

• ω(n), defined as the total number of distinct prime factors of n . For example:

::ω(4) = 1 ::ω(16) = ω(24) = 1 ::ω(20) = ω(22 · 5) = 2 ::ω(27) = ω(33) = 1 ::ω(144) = ω(24 · 32) = ω(24) + ω(32) = 1 + 1 = 2 ::ω(2000) = ω(24 · 53) = ω(24) + ω(53) = 1 + 1 = 2 ::ω(2001) = 3 ::ω(2002) = 4 ::ω(2003) = 1 ::ω(54,032,858,972,279) = 3 ::ω(54,032,858,972,302) = 5 ::ω(20,802,650,704,327,415) = 5

• a1(n) – the sum of the distinct primes dividing n, sometimes called sopf(n) . For example:

::a1(1) = 0 ::a1(4) = 2 ::a1(20) = 2 + 5 = 7 ::a1(27) = 3 ::a1(144) = a1(24 · 32) = a1(24) + a1(32) = 2 + 3 = 5 ::a1(2000) = a1(24 · 53) = a1(24) + a1(53) = 2 + 5 = 7 ::a1(2001) = 55 ::a1(2002) = 33 ::a1(2003) = 2003 ::a1(54,032,858,972,279) = 1238665 ::a1(54,032,858,972,302) = 1780410 ::a1(20,802,650,704,327,415) = 1238677

Multiplicative functions

From any additive function f(n) it is possible to create a related multiplicative function g(n), which is a function with the property that whenever a and b are coprime then: g(a b) = g(a) \times g(b). One such example is g(n) = 2^{f(n)}. Likewise if f(n) is completely additive, then g(n) = 2^{f(n)} is completely multiplicative. More generally, we could consider the function g(n) = c^{f(n)} , where c is a nonzero real constant.

Summatory functions

Given an additive function f, let its summatory function be defined by \mathcal{M}f(x) := \sum{n \leq x} f(n). The average of f is given exactly as \mathcal{M}f(x) = \sum{p^{\alpha} \leq x} f(p^{\alpha}) \left(\left\lfloor \frac{x}{p^{\alpha}} \right\rfloor - \left\lfloor \frac{x}{p^{\alpha+1}} \right\rfloor\right).

The summatory functions over f can be expanded as \mathcal{M}f(x) = x E(x) + O(\sqrt{x} \cdot D(x)) where \begin{align} E(x) & = \sum{p^{\alpha} \leq x} f(p^{\alpha}) p^{-\alpha} (1-p^{-1}) \ D^2(x) & = \sum_{p^{\alpha} \leq x} |f(p^{\alpha})|^2 p^{-\alpha}. \end{align}

The average of the function f^2 is also expressed by these functions as \mathcal{M}_{f^2}(x) = x E^2(x) + O(x D^2(x)).

There is always an absolute constant C_f 0 such that for all natural numbers x \geq 1, \sum_{n \leq x} |f(n) - E(x)|^2 \leq C_f \cdot x D^2(x).

Let \nu(x; z) := \frac{1}{x} #!\left{n \leq x: \frac{f(n)-A(x)}{B(x)} \leq z\right}!.

Suppose that f is an additive function with -1 \leq f(p^{\alpha}) = f(p) \leq 1 such that as x \rightarrow \infty, B(x) = \sum_{p \leq x} f^2(p) / p \rightarrow \infty.

Then \nu(x; z) \sim G(z) where G(z) is the Gaussian distribution function G(z) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{z} e^{-t^2/2} dt.

Examples of this result related to the prime omega function and the numbers of prime divisors of shifted primes include the following for fixed z \in \R where the relations hold for x \gg 1: #{n \leq x: \omega(n) - \log\log x \leq z (\log\log x)^{1/2}} \sim x G(z), #{p \leq x: \omega(p+1) - \log\log x \leq z (\log\log x)^{1/2}} \sim \pi(x) G(z).

References

References

1. Erdös, P., and M. Kac. On the Gaussian Law of Errors in the Theory of Additive Functions. Proc Natl Acad Sci USA. 1939 April; 25(4): 206–207. [https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1077746/ online]

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::