Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's define the primarithm function, $pog : \mathbb{N} \rightarrow \mathbb{N}$, where $pog(n)$ is the largest number of distinct primes that can divide a natural number $k$, $k \leq n$.

Does this function have a real name and, more importantly, is there a good estimating function that approaches $pog(n)$ as $n$ gets large?

share|cite|improve this question
up vote 2 down vote accepted

Let $\omega(n)$ be the number of distinct prime divisors of $n$, and let $\tau(n)$ be the number of divisors of $n$. Then, one can show that $$ \tau(n) \le \exp \left( \frac{ \log 2 \log n}{\log \log n} \left( 1 + O\left( \frac{\log \log \log n}{\log \log n} \right) \right) \right)$$ (see, for instance, G. Tenenbaum's Introduction to Analytic and Probabilistic Number Theory, chapter 5).

Then, since $2^\omega(n) \le \tau(n)$, we may conclude that $$ \omega(n) \le (1+ o(1)) \frac{\log n}{\log \log n}$$ as $n \rightarrow \infty$. By directly working with numbers which are the product of the first $k$ primes, a lower bound for $\tau$ is attainable which yields a lower bound for $\omega$ of the same order. In short, one has $$\limsup_{n \rightarrow \infty} \frac{\omega(n)}{(\log n)/(\log \log n)} = 1.$$

share|cite|improve this answer
Thank you. So roughly, since $n < pog(n^n)$ $$\frac{\log{n}}{\log \log{n}} < pog(n) < 1.5 \frac{\log{n}}{\log \log{n}}$$. – Eric Nitardy Mar 15 '11 at 21:23
It appears that $$\omega(n)/((\log n)/(\log \log n)) \le 1.3840127408$$ with equality when $n=223092870$, but I'd have to do a little more checking to be absolutely sure. – Matthew Conroy Mar 15 '11 at 22:32

The primorial function gives the product of the first $n$ primes. Yours is the inverse of this. Primorial grows as about $n^n$. There are some references in OEIS.

share|cite|improve this answer
The sequence referenced is A111972. – Charles Mar 15 '11 at 19:38

Your Answer


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.