3
$\begingroup$

What is an upper bound for number of prime powers less than $n$?

I mean the numbers in the form $a^b$ in which $b \ge 2$ and $a$ is a prime number.

I have found that $\frac {\log n} {\log 2} + \frac {\log n} {\log 3} + \frac {\log n} {\log 5} + \dots + \frac {\log n} {\log i}$ is an upper bound ($i$ is the greatest prime less than or equal to $n$).

And I guess it is less than $\pi \left( \frac {\log n} {\log 2} \right)$, so $\pi \left( \frac {\log n} {\log 2} \right)$ is an upper bound.

$\endgroup$
  • $\begingroup$ $n$ is an upper bound. (Did you want a better one?) And presumably you want $a$ to be prime. $\endgroup$ – TonyK Jan 19 '16 at 16:27
  • $\begingroup$ pi(n) is an upper bound? $\endgroup$ – Jorge Fernández Hidalgo Jan 19 '16 at 16:34
  • $\begingroup$ @dREaM: Yes, because numbers of the form $p^1$ don't count. $\endgroup$ – TonyK Jan 19 '16 at 16:36
  • $\begingroup$ Are you sure it is an upper bound though? $\endgroup$ – Jorge Fernández Hidalgo Jan 19 '16 at 16:36
  • 2
    $\begingroup$ @ttt, $n$ is also an upper bound, although not as sharp as your $\pi(n)$. In my acerbic way, I was implying that if you are not going to put any effort into your question, then I am not going to put any effort into my answer. $\endgroup$ – TonyK Jan 19 '16 at 16:38
1
$\begingroup$

The expression you give is a correct computation if you enclose every term on the right in floor brackets. You can distribute out the $\log n$ numerator, so you are really asking for $\log n\sum_{p \text{ prime}}^{p \le n}\frac 1{\log p}$ We can compute the first few terms in the sum explicitly. I arbitrarily did primes up through $19$.
$$\log n\sum_{p \text{ prime}}^{p \le n}\frac 1{\log p}\approx \log n(1.5666 +\sum_{k=10}^{p_k \le n}\frac 1{\log p_k})$$ Then using the prime number theorem, the last term becomes $$\sum_{k=10}^{p_k \le n}\frac 1{\log p_k}\approx \sum_{k=10}^{p_k \le n}\frac 1{\log (k \log k)}=\sum_{k=10}^{p_k \le n}\frac 1{\log k + \log \log k}$$ Now to get an upper bound we can ignore the $\log \log k$ term in the denominator and change the sum to an integral $$\sum_{k=10}^{p_k \le n}\frac 1{\log k + \log \log k}\gt \sum_{k=10}^{p_k \le n}\frac 1{\log k}\approx \operatorname{li}(\pi(n))-\operatorname{li}(10)$$ Putting it all together, your bound is $$\log n\left(1.5666+\operatorname{li}(\pi(n))-\operatorname{li}(10)\right)$$

$\endgroup$
1
$\begingroup$

We can count the powers of $2,3,5,7,11,13,17$ independently and then take care of the other powers using:

$\pi(x)<\lfloor1.3\frac{x}{\log(x)}\rfloor$, for $n\geq 17$.

Suppose $P$ is the number of prime powers less than or equal to $n$, in other words $\sum\limits_{i=2}^{2^i\leq n}\pi(x^{1/i})$ , Then we have the following inequality for $n>7$:

$P\leq\sum\limits_{i=1}^{i\leq7}\lfloor\log_{p_i}(n)-1\rfloor+\sum\limits_{i=2}^{19^i\leq n}\lfloor\frac{1.3n^{1/i}}{i\log(n)}-7\rfloor$

$\endgroup$
  • $\begingroup$ I need a bound in closed form $\endgroup$ – ttt Jan 19 '16 at 17:14
  • $\begingroup$ Why? We can easily calculate this bound in $\mathcal O(\log n)$ time. $\endgroup$ – Jorge Fernández Hidalgo Jan 19 '16 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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