Hmm is there an asymptotic statement underlying this? The powers of 2 are exponentially sparse (N integers contain at most 1/logN powers of 2), whereas primes are polynomially sparse (N integers contains N/LogN primes)
Would you care to clarify? If it's a question then I'll try to answer, but if it's a conjecture, can you make it more precise?
I don't have an answer, it's not my area, but it does feel a lot like the condition "sum(1/n) diverges" is likely to be close, but that's just a gut feeling.
It's probably also worth noting that weird density distributions are possible. E.g. one could imagine a kind of oscillation where you include enough values to get the total density up to that point up to some decreasing threshold (e.g. 1-2^-k if we've flip-flopped k times) then omit values to get below a different threshold (e.g. 2^-k if we've flip-flopped k times), and repeat the process indefinitely. The count up to a point n for this construction has the interesting property that it isn't greater in a big-O sense than the count for exponentially sparse sets while also not being less than the count for any sublinear density function in a big-omega sense (using the Knuth interpretation).
If you have a sequence that grows asymptotically like n^m it means that f(n)/n^m goes to a constant asymptotically. So the question is if this implies that sum 1/f(n) converges. I feel intuitively that it should be possible to prove that.
A sketch: For every epsilon there is an N such that |1/f(n) - 1/C n^-m| < epsilon n^-m for n > N. So if we take the difference between the reciprocal partial sums, then that is bounded by eps * the partial sum. That is finite exactly if the reciprocal sums converge. Thus the convergence behaviour is the same for this case...