From http://en.wikipedia.org/wiki/Arithmetic_function#.CE.A9.28n.29.2C_.CF.89.28n.29.2C_.CE.BDp.28n.29_.E2.80.93_prime_power_decomposition

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

The fundamental theorem of arithmetic states that any positive $n = p_1^{a_1}\cdots p_k^{a_k}$ where $p_1 < p_2 < ... < p_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 $νp(n)$ as the exponent of the highest power of the prime $p$ that divides $n$. I.e. 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 functions ω and Ω are defined by

ω(n) = k,
Ω(n) = a_1 + a_2 + ... + a_k.

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

It seems that a few things are clearly known about $\omega(n)$. For instance, it has normal order $log \ log \ (n)$.

How can we bound $\Omega (n)$ in the asymptotic limit?


1 Answer 1


$\Omega[N]$ asymptotically approaches $\ln \ ln \ N$.

See this reference: http://citeseerx.ist.psu.edu/viewdoc/download?doi=

In chapter 7, they talk about related results. In particular see Exercise 7.1:

(i) Show that, for any ξ(N) → ∞, ν N {n : |Ω(n) − log log N| > ξ(N) log log N} ξ(N) −2 , and deduce that Ω(n) has normal order log log n.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .