Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there a formula that can tell us how many distinct prime factors a number has? We have closed form solutions for the number of factors a number has or the sum of those factors but not the number of distinct prime factors.

So for example: \begin{array}{rr} \text{number} & \text{distinct}\atop \text{prime factors} \\ 1&0 \\ 2&1 \\ 3&1 \\ 4&1 \\ 5&1 \\ 6&2 \\ 7&1 \\ 8&1 \\ 9&1 \\ 10&2 \end{array}

share|improve this question
    
What closed form solutions are you referring to? If you mean $d(n) = \prod_{p^r \| n} (r+1)$ then what is wrong with $\omega(n) = \sum_{p \mid n} 1$? –  Erick Wong Jun 2 '13 at 23:25

3 Answers 3

up vote 5 down vote accepted

This is a historically interesting question as it led Hardy and Ramanujan to lay the foundation to probabilistic number theory in course of their solution to this problem. Given $n$ there is no non-trivial deterministic closed form formula for the number of distinct prime factors of $n$. However we have very good probabilistic formula for the same.

Hardy and Ramanujan proved that for almost all integers, the number is distinct primes dividing a number $n$ is formula

$$ \omega(n) \sim \log\log n. $$

We can do much better than the Hardy-Ramanujan estimate and find and estimate of $\omega(n)$ which can be bounded by normal distribution. Erdos and Kac imporved the estimate of $\omega(n)$ and proved that

$$ \lim_{x \to \infty} \frac{1}{x}\# \Big\{n\le x, \frac{\omega(n) - \log\log n}{\sqrt{\log\log n}} \le t \Big\} = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^{t}e^{-\frac{u^2}{2}}du $$

This formula says that if $n$ is a large number, we can estimate the distribution of the number of prime factors for numbers of this range. For example we can show that around 12.6% of 10,000 digit numbers are constructed from 10 distinct prime numbers and around 68% (±$\sigma$) are constructed from between 7 and 13 distinct primes.

share|improve this answer
    
"for almost all integers, the number is distinct primes dividing a number $n$ is given by the asymptotic formula" does not make sense. Asymptotic formulas do not apply to individual instances; you wouldn't be able to cite a single number $n$ for which the formula gives its number of distinct primes. –  Marc van Leeuwen Jun 3 '13 at 7:44
    
Yeah asymptotic is not the right word, but the result remains the same. This is a probabilistic result. –  user60930 Jun 3 '13 at 8:16
    
I see nothing random at all in the formulation. –  Marc van Leeuwen Jun 3 '13 at 8:21
    
Well then for a more precise formulation, you might want to refer to mathworld.wolfram.com/Hardy-RamanujanTheorem.html and mathworld.wolfram.com/Erdos-KacTheorem.html –  user60930 Jun 3 '13 at 8:33
    
And that statement involves an expression $\sqrt{\ln\ln x}$, which cannot be taken out without the statement losing its meaning. –  Marc van Leeuwen Jun 3 '13 at 8:37

This is commonly known as $\omega(n)$. See Wikipedia.

share|improve this answer

We do $not$ have the closed form solutions you claim. We have formulas that assume that we know the prime factorization.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.