1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Jun 17 at 12:24
  • $\begingroup$ Hmm, true. Let me think about this. $\endgroup$ – Captain Trojan Jun 17 at 12:27
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Captain Trojan Jun 17 at 13:08

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.