# Thread: How many distinct prime powers divide n ?

1. ## 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

2. 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)$.

3. Thanks !