# How many distinct prime powers divide n ?

• Jun 10th 2010, 01:10 AM
Bacterius
How many distinct prime powers divide n ?
Hello,
I'm looking for an empirical result (if it can be proved it is better but not required) that could tell me how many distinct prime powers would divide a randomly chosen $\displaystyle n$ ? When I say "distinct" prime powers, it means the base has got to be different.

After some experimentation I find that if $\displaystyle n$ is the random number, then $\displaystyle n$ has on average $\displaystyle \ln{(\log{(n)})}$ distinct prime powers, but before I attempt a large scale data collection I was just wondering if you guys knew any results that could save me two days of intense computing ?

Thanks all :)
• Jun 10th 2010, 08:09 AM
chiph588@
Quote:

Originally Posted by Bacterius
Hello,
I'm looking for an empirical result (if it can be proved it is better but not required) that could tell me how many distinct prime powers would divide a randomly chosen $\displaystyle n$ ? When I say "distinct" prime powers, it means the base has got to be different.

After some experimentation I find that if $\displaystyle n$ is the random number, then $\displaystyle n$ has on average $\displaystyle \ln{(\log{(n)})}$ distinct prime powers, but before I attempt a large scale data collection I was just wondering if you guys knew any results that could save me two days of intense computing ?

Thanks all :)

The function you're thinking of has a name: $\displaystyle \Omega(n)$.

Given $\displaystyle n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}, \;\; \Omega(n)=\sum_{i=1}^k \alpha_i$.

For example, $\displaystyle 60=2^2\cdot3\cdot5\implies\Omega(60)=2+1+1=4$.

It turns out $\displaystyle \Omega(n)\sim\log\log n$ just like you observed.

If you want to get a bit more accurate though, things get messy. A better approximation for $\displaystyle \Omega(n)$ is

$\displaystyle \Omega(n)\sim\log\log n+B_2+\sum_{k=1}^\infty \left(-1+\sum_{j=0}^{k-1}\frac{\gamma_j}{j!}\right)\frac{(k-1)!}{\log^k n}$, where $\displaystyle B_2=\gamma+\sum_{n=2}^\infty\frac{\varphi(n)\log\z eta(n)}{n}\approx1.03465388$ and

$\displaystyle \gamma_j=\lim_{m \to \infty} \left(\left(\sum_{k = 1}^m \frac{(\ln k)^n}{k}\right) - \frac{(\ln m)^{n+1}}{n+1}\right)$.
• Jun 10th 2010, 10:12 PM
Bacterius
Thanks ! :)