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

  • 0
    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}}$$.2011-03-15
  • 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