# Is it true that PRIMES are in SPARSE?

I'm wondering if PRIMES, the language of all prime numbers represented in binary, which is $$\{10, 11, 101, 111, 1011, 1101, ...\}$$, belongs to the SPARSE class, a set of all sparse languages, that is, languages satisfying the property that the amount of words of length $$n$$ is bounded by some polynomial $$p(n)$$.

I believe the answer should be yes, because as the size of the tested number $$p$$ grows, the size of its binary representation grows logarithmically while the density of primes logarithmically shrinks, which leads me to an assumption that $$p(n)$$ could even be a constant, but I found no resources online to support or contradict this opinion.

• Please check your maths. You found two "logarithms" that are quite unrelated. The number of primes less than 10^18 is 24,739,954,287,740,860. That's most of the primes fitting into 60 bits. – gnasher729 Jun 17 at 12:24
If I remember correctly, there are $$\Theta(\frac{n}{\log(n)})$$ primes between $$n$$ and $$2n$$. Sum them up to get the number of primes up to $$2n$$, and then we know that $$2n$$ has $$\log(n)+1$$ bits. I think if you do the maths it will not end up in $$SPARSE$$, but I might be wrong here.
• I see the error of my ways. When splitting numbers into intervals from $n$ to $2n$, which are the numbers of equal binary length, $n$ grows exponentially, so $\mathcal{\Theta}(\frac{n}{log(n)})$ becomes $\frac{2^n}{log(2^n)} = \frac{2^n}{n}$. That means, for a specific binary length, there are linearly ($cn$ times) many more numbers than prime numbers as the binary length grows. – Captain Trojan Jun 17 at 13:08