1
$\begingroup$

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?

2 Answers 2

2

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

  • 1
    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.2011-03-15
3

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.

  • 0
    The sequence referenced is [A111972](https://oeis.org/A111972).2011-03-15