TITLE: How many numbers are products of $p^p$?
QUESTION [6 upvotes]: Consider the set $\mathcal{S}=\{1,4,16,27,\ldots\}$ of numbers which are products of numbers of the form $p^p$ for $p$ prime. ($\mathcal{S}$ is A072873 in the OEIS.) Note that multiple primes are allowed, and that a prime may appear more than once. Approximately how many members of $\mathcal{S}$ are there below $x$?
Clearly it's more than $\log_4x$ which gives just the powers of 4. It's also more than $c\log^2x$ just from considering the {4, 27}-smooth numbers, and by continuing that process it can be seen to grow faster than $\log^kx$ for any $k$.
This came up in connection with the problem of upper-bounding a certain sequence related to Pillai's arithmetical function.

REPLY [3 votes]: Write $p_n$ for the $n$th prime number, and let $K$ be the largest $K$ with $p_K^{p_K}<x$, and let $L=\log x$.
Then each element $s\in\cal S, s<x$ satisfies
$$
\log s = \sum_{i=1}^K a_i p_i \log p_i
$$
for some nonnegative integers $a_i$. Consider $\bf{z}\in \mathbb R^K$ and the simplex
$$
0 \le \sum_{i=1}^K (p_i \log p_i) z_i < L
$$
then there is a one-to-one correspondence between the $s<x$ and the lattice points  $(z_1,\ldots,z_K)=(a_1,\ldots,a_K)$ in this polytope.
For $J<K$ with $p_J \log p_J \ll L$ we can approximate the number of choices of $(a_1,\ldots,a_J)$ by the volume
$$
A  = \frac{1}{J!} \prod_{i=1}^J \frac{L}{p_i\log p_i}
$$
(In the full dimensionality this does not work because all of the points are on the surface and the volume goes to zero.) This gives an estimate for the size of the subset of allowed points with $a_{J+1}=\ldots=a_K=0$.
$$
\begin{align}
\log A & = J\log L - \log J! - \vartheta(p_J) - T(p_J) \\
& \approx J\left(\log L -2\log J - 2\log\log J +2  \right) \\
& = J\log \frac{e^2 L}{(J\log J)^2}
\end{align}
$$
where $\vartheta$ is Chebyshev's function and
$$
\log N! = N\log N - N + o(N) \\
\vartheta(p_N) = N\log N + N\log\log N - N + o(N) \\
T(x) = \sum_{p\le x} \log\log p \\
T(p_N) \sim N\log\log N
$$
(I'm not 100% certain of the asymptotic for $T(p_N)$; I'll try to find the correct form, but please let me know if this is a mistake.)
Choosing $J \approx 2\sqrt{L} (\log L)^{-1}$ we get
$$
A \approx \exp(2J) \approx \exp \left(\frac{4\sqrt{\log x}}{\log\log x}\right)
$$
For an upper approximation we can let the last $K-J$ dimensions be unconstrained to get
$$
\begin{align}
B & = A \prod_{i=J+1}^K \frac{L}{p_i\log p_i} \\
\log B & = K\log L - \log J! - \vartheta(p_K) - T(p_K)
\end{align}
$$
There may be some improvement possible for an appropriate choice of $J$, but for a first order estimate it suffices to let $J=0$. Then
$$
\begin{align}
\log B & \approx K \left(\log L - \log K - 2\log \log K + 1\right) \\
& \approx K \log \frac{e L}{K \log^2 K}
\end{align}
$$
From the prime number theorem and the definition of $K$ we can find $K \approx L (\log L-\log\log L)^{-2}$ and
$$
B \approx \exp(K) \approx \exp\left(\frac{\log x}{(\log\log x-\log\log\log x)^2}\right)
$$
These $A,B$ only give rough approximations to the sizes of a subset and superset, but I think this argument could be refined to turn them into true bounds.
{"set_name": "stack_exchange", "score": 6, "question_id": 995503}