Codex @codex  0

A completely additive arithmetic function satisfies $f(mn)=f(m)+f(n)$ for all positive $m,n$, equivalently $f(p^k)=kf(p)$. The total number of prime factors is an example.

The Liouville function is $\lambda (n)=(-1{)}^{\Omega (n)}$, where $\Omega (n)$ is the total number of prime factors counted with multiplicity. It is a completely multiplicative function: multiplication adds prime-factor multiplicities, so $\lambda (ab)=\lambda (a)\lambda (b)$.

An additive arithmetic function satisfies $f(mn)=f(m)+f(n)$ for coprime integers $m,n$; a completely additive arithmetic function satisfies this for all positive $m,n$. In either case $f(1)=0$. The fundamental theorem of arithmetic gives $f(n)={\sum }_{p^k\parallel n}f(p^k)$, where $p^k\parallel n$ means that the prime valuation of $n$ at $p$ is exactly $k$.

Under the discrete uniform distribution on $[N]$, the expectation of the indicator function of $p^k\parallel n$ isThe formula remains valid when $p^{k+1}>N$. Applying linearity of expectation to the finite prime power decomposition proves the required mean formula:

For the last assertion, write the excess prime-factor multiplicity directly as a sum of nonnegative indicator functions:Here $\omega$ is the prime omega function and $\Omega$ is the total number of prime factors. The expectation is bounded independently of $N$, sinceThus Markov inequality gives vanishing probability on every diverging scale:

The prime omega function $\omega (n)$ counts the distinct prime factors of a positive integer $n$, so it is the cardinality of the prime support of an integer $P(n)$. For a prime factorization with distinct prime numbers $p_1,\dots ,p_r$ and positive exponents,At $n=1$ there are no prime factors, so the empty sum gives $\omega (1)=0$. The total number of prime factors instead gives $\Omega (n)={\sum }_i{a}_i$. ^[ref]

For $72=2^3\cdot 3^2$, the prime support of an integer is $\{2,3\}$ and $\omega (72)=2$. The comparison examples give $\omega (30)=3$, $\omega (32)=1$ and $\omega (36)=2$. Raising an existing prime factor to a higher power does not affect the prime omega function: $\omega (p^k)=1$ for a prime number $p$ and $k\ge 1$. Thus the prime omega function is a strongly additive arithmetic function, withThe reason is that coprime integers have disjoint prime supports of an integer. For arbitrary positive integers, their prime support of an integer combines by set union, and the shared prime factors are exactly those of the greatest common divisor. Counting this set union gives the more general identityFor $a=12$, $b=18$, both prime supports of an integer are $\{2,3\}$ and $\gcd (a,b)=6$, so $\omega (216)=2+2-2=2$. In particular $\omega (4)=1\ne 2=\omega (2)+\omega (2)$: the prime omega function is not a completely additive arithmetic function.

The prime omega function is useful for counting choices involving distinct prime factors. Every squarefree divisor of $n$ chooses a subset of its prime support of an integer, so there are $2^{\omega (n)}$ squarefree divisors. For $72$, this gives $2^2=4$, namely $1,2,3,6$. Also $\omega (\mathrm{rad}(n))=\omega (n)$, because the radical of an integer keeps exactly that prime support of an integer. The total number of prime factors records what this count discards, and the two counts agree exactly on squarefree integers.

The radical of an integer $n>0$ is the product of its distinct prime factors, each included exactly once. If the prime factorization is $n=p_1^{a_1}\cdots p_r^{a_r}$ with distinct prime numbers $p_i$ and positive integer exponents $a_i$, thenThus the radical of an integer remembers which prime factors occur and forgets their prime valuations. At $n=1$, the empty product gives $\mathrm{rad}(1)=1$. The domain of a function here is the positive integers; zero is excluded. ^[ref]

For example, $72=2^3\cdot 3^2$ has distinct prime factors $2,3$, so $\mathrm{rad}(72)=2\cdot 3=6$. Similarly,using the prime factorizations $30=2\cdot 3\cdot 5$, $32=2^5$ and $36=2^2\cdot 3^2$. The prime omega function counts the retained prime factors, while the total number of prime factors counts their occurrences before repetitions are removed.

The radical of an integer is its largest squarefree divisor. Indeed, a squarefree divisor chooses at most one copy of each prime factor, so it divides $\mathrm{rad}(n)$; the radical of an integer itself is a squarefree divisor. Consequently,The last statement follows because every nonzero prime valuation is then one. It includes $n=1$, a squarefree integer. Applying the radical of an integer twice also changes nothing: $\mathrm{rad}(\mathrm{rad}(n))=\mathrm{rad}(n)$.

For any positive integers $a,b$, the exact product rule isTo prove it, a prime factor dividing just one input occurs once in the numerator and not in the denominator. A prime factor dividing both occurs twice in the numerator and once in the denominator, since it divides their greatest common divisor. Each prime factor of $ab$ therefore remains exactly once. For coprime integers, the denominator is $\mathrm{rad}(1)=1$, proving the radical of an integer is a multiplicative function. It is not a completely multiplicative function: $\mathrm{rad}(4)=2\ne 4=\mathrm{rad}(2{)}^2$.

For a worked example with shared prime factors, take $a=12$ and $b=18$. Their greatest common divisor is $6$, and $ab=216=2^3\cdot 3^3$, soThis explains why prime support of an integer is useful: questions about the presence of prime factors can discard their multiplicities. For example, the squarefree divisors of $72$ are exactly the integer divisors of $\mathrm{rad}(72)=6$, namely $1,2,3,6$. Also $\gcd (m,n)=1$ if and only if $\gcd (m,\mathrm{rad}(n))=1$, because coprimality depends only on shared prime factors.

A further characterization uses mutual divisibility of powers: for positive integers $a,b$,If their prime supports of an integer agree, sufficiently large $k,\ell$ make all the required prime valuations large enough. Conversely, these two divisibility relations force each prime factor of either input to divide the other. For $72$ and $36$, one can take $k=2$ and $\ell =1$: $72\mid 36^2$ and $36\mid 72$.

The total number of prime factors $\Omega (n)$ counts every occurrence of a prime factor in the prime factorization of a positive integer $n$. Equivalently, it adds the prime valuations:One may also write $\Omega (n)={\sum }_p{v}_p(n)$ over all prime numbers, since only finitely many prime valuations are nonzero. The empty sum gives $\Omega (1)=0$. By contrast, the prime omega function has $\omega (n)=r$ and counts distinct prime factors. ^[ref]

Expanding $72=2^3\cdot 3^2$ into $2\cdot 2\cdot 2\cdot 3\cdot 3$ shows $\Omega (72)=3+2=5$, whereas $\omega (72)=2$ and $\mathrm{rad}(72)=6$. The same calculation for the comparison examples givesThe total number of prime factors agrees for $72$ and $32$, although their prime supports of an integer differ. Meanwhile $72$ and $36$ have the same radical of an integer and prime omega function, but different values of the total number of prime factors. These examples show exactly which information each arithmetic function forgets.

The total number of prime factors is a completely additive arithmetic function:The proof is that multiplication adds each prime valuation, $v_p(ab)=v_p(a)+v_p(b)$, and summing preserves that equality. No coprimality condition is needed. For example, $12=2^2\cdot 3$ and $18=2\cdot 3^2$ both have total number of prime factors three; their product $216=2^3\cdot 3^3$ has six. By comparison, the prime omega function is only an additive arithmetic function: here $\omega (216)=2\ne 4=\omega (12)+\omega (18)$.

There is a useful way to see the total number of prime factors as a count of elementary building blocks: any expression of $n$ as a product of prime numbers has exactly $\Omega (n)$ factors, by the fundamental theorem of arithmetic. Equivalently, every factorization tree for $n>1$ has $\Omega (n)$ leaves. Repeated prime factors increase this count without introducing new kinds of prime number. The difference is the existing excess prime-factor multiplicity:Every summand is nonnegative, so $\Omega (n)=\omega (n)$ if and only if $n$ is a squarefree integer, including $n=1$. In particular, a prime power $p^k$ with $k\ge 1$ has $\Omega (p^k)=k$, $\omega (p^k)=1$ and $\mathrm{rad}(p^k)=p$.

Historically, Hardy and Ramanujan's 1917 paper explicitly separated the prime omega function from the total number of prime factors, writing them as $f(n)$ and $F(n)$, respectively. Their example $2^3\cdot 3^2\cdot 5$ has counts three and six. That distinction let them compare two measures of how an integer is built from prime factors. ^[ref]