Let us consider a set of numbers $a_{p,k}=p^k$ where $p$ is a prime and $k\in N$. Create a sorted sequence made of these numbers, starting with the smallest one:
2,3,4,5,7,8,9,11,13,16,17,19,23,25,29,31...
What is the 100th (1000th, 1000000th) number in this sequence?
I came accros this while trying to solve a pretty interesting problem that forced me to come up with an ordered list of numbers composed of three different primes raised to an arbitrary power. It turned out to be much more complicated than expected and I easily missed a few numbers.
So I tried to simplify the problem and limit the items of the list to just one prime factor and it’s still very hard not to make a mistake.
I have found this sequence described in OEIS (A000961) and it has many interesting properties but it looks that finding the n-th member of the sequence is even harder than finding the n-th prime.
Ok, this could be too difficult but would this probem be any easier if we had the list of all primes already available? Mathematica, for example, can give you the n-th prime in less than a second for fairly big values of n.
If you include knowledge of the exact prime counting function $\pi(N)$ (which Mathematica does provide as PrimePi[..]), it is fairly easy and efficient to obtain. Consider the function $f(N)$ that counts the number of $a_{p,k}=p^k \leq N$, then $$ f(N) \equiv \sum_{k \geq 0} \pi(N^\frac{1}{k}) $$ where the $k$th term counts the number of $p^k \leq N$.
An upper limit for the summation is easily found, since the highest power $k$ that could exist would be $2^k \leq N < 2^{k+1}$, and hence using the floor function $\lfloor \dots\rfloor$ $$ f(N) \equiv \sum_{k \geq 0}^{\lfloor \log N/\log 2 \rfloor} \pi(N^\frac{1}{k}) $$ From here it would be applying your favourite root finding method to find the $M$, such that $f(M-1)=N-1$ and $f(M)=N$.
Note that for $k>1$ the values of $\pi(N^\frac{1}{k})$ are relatively small with respect to $\pi(N)$, and hence that $M_0 = p_N$ the $N$th prime is a fairly good initial guess, but will of course overestimate the correct value.
The $10^3$th term in the sequence is the prime 7517, and the $10^6$th is the prime 15474787, whereas the $10^3$th and $10^6$th primes respectively are 7919 and 15485863.
Mathematica will compute the function $f(N)$ for $N \leq 10^{12}$ within a second.