# Number of prime powers needed to express all composites up to $n$

Assume we are given a number $n>3$.

Define a prime power as a number of the form $p^r$, where $p \in \mathbb P$ and $r \in \mathbb N, \ r >0.$

We would like to know how many distinct prime powers are needed to express all composite numbers up to $n$. In other words, if we hold not only primes but pure prime powers like $5^2$ as distinct in the composition of a number and still count all numbers but primes as composites, how large a "vocabulary" of such numbers is needed to express all composites up to $n$?

Define a function $C: \mathbb N \rightarrow \mathbb N$ where $C(n)$ is the number distinct prime powers needed to express all composite numbers up to $n$.

Does there exist a "simple" formulation of $C(n)$, where simple means not involving sums where either the summation index or summands involve floor or ceiling functions or the like? Purely combinatorial justifications or intuition would also be nice.

A few values of $C(n):$

$$\begin{array}{c|lcr} n & C(n) \\ \hline 4 & 1 \\ 6 & 3 \\ 10 & 6 \\ 100 & 25 \\ 1000 & 120 \\ \end{array}$$

Some inequalities:

\begin{equation} n-\pi(n)-1>C(n) \ \ \ \ \ (1), \end{equation} \begin{equation} C(n)>\pi \left( \frac{n}{2} \right) \ \ \ \ \ (2), \end{equation}

where $\pi(n)$ is the prime-counting function.

(1) is clear, because the lhs is the number of composite numbers up to $n$ minus 1, because 1 is not a composite in this context, and clearly we need less than this number of prime powers, because not every composite needs a new prime power in its composition.

(2) follows from the fact that $\pi \left( \frac{n}{2} \right)$ is the number of distinct primes smaller than $n/2$ and clearly we need all of them. Consider a sequence $(2k), \ k=1,2,3\dots n/2.$ Here $k$ includes all primes smaller than $n/2$.

Edit:

The "non-simple" formula for $C(n)$ would be:

\begin{equation} C(n) = \pi \left( \frac{n}{2} \right)+\sum_{k=2}_{k \in \mathbb P}^{\lfloor \sqrt{n} \rfloor} \left( \lfloor \frac{\log n}{\log k} \rfloor -1 \right) \end{equation}

Because we need all primes $\pi \left( \frac{n}{2} \right)$ and the $\lfloor \frac{\log n}{\log k} \rfloor$ tells the greatest power a prime can be raised for it to be smaller than $n$. But this counts the single power too, so we need to subtract the 1. The index goes to $\lfloor \sqrt{n} \rfloor$ because this is the magnitude of the greatest prime whose square can be smaller than $n$.

This can be simplified further, by simple removing the need for prime counting function altogether:

\begin{equation} C(n) = \sum_{k=2}_{k \in \mathbb P}^{\frac{n}{2} } \left( \lfloor \frac{\log n}{\log k} \rfloor \right) \end{equation}

• There is no simple formulation for $\pi(n)$, so there won't be any simple formulation for $C(n)$. The number of prime powers up to $n$ is, asymptotically, negligible compared to the number of primes up to $n$, so, asymptotically, $C(n)$ is $\pi(n/2)$ is $(1/2)n(\log n)^{-1}$. – Gerry Myerson Nov 17 '13 at 10:50

If i understood what you ask, you want the number of prime powers up to $n$.
Then you could define $C(n)$ as $\pi^*(n)$
(Erdos calls it like that in his famous book :Topics in the Theory of Numbers)

We can see that $\pi^*(n)=\pi(n)+\pi(\sqrt n)+\pi(\sqrtn)+...$.
The summation ends at the $k$th root, when $k\leq \frac{lnn}{ln2}$
So it is easy to see that $\pi^*(n)$ behaves like $\pi(n)$ because the above sum is not greater than $\pi(n)+(k-1)\pi(\sqrt n)$ which is asymptoticaly equal to $\pi(n)$

So,if you want an elementary bound :there are constants $a,b$ with
$\frac{an}{lnn}<\pi^*(n)<\frac{bn}{lnn}$

(But don't expect anything better at all if you want my opinion)

• That's not exactly what OP is trying to count. There's no need to count primes exceeding $n/2$, since they can't be involved in any composites, and OP is only interested in representing composites. – Gerry Myerson Nov 17 '13 at 10:45
• Thank you for the reference, very interesting. I can see how this would be true. I think I am content with this answer. – Valtteri Nov 17 '13 at 13:45
• On another note, one can, using my formulations, come up with the identity that the sum of floors of p based logarithms of n, where p goes through all primes between sqrt(n) and n/2, is equal to the pi(n/2)-pi(sqrt(n)). – Valtteri Nov 17 '13 at 13:48