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


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}

  • $\begingroup$ 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}$. $\endgroup$ – 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(\sqrt[3]n)+...$.
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

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

  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Nov 17 '13 at 10:45
  • 1
    $\begingroup$ Thank you for the reference, very interesting. I can see how this would be true. I think I am content with this answer. $\endgroup$ – Valtteri Nov 17 '13 at 13:45
  • 1
    $\begingroup$ 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)). $\endgroup$ – Valtteri Nov 17 '13 at 13:48

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.