Primes in binary

105 Views Asked by At

Let $$S_n(k)=\{1\leq m\leq n: m\ \mbox{has $k$ ones in its binary representation and $m$ is prime}\}\ \\ \forall \ n\geq 2^k-1,\ k\geq1.$$ Let $\pi(x)$ be the prime number function. Then what can be said about $$f(k)=\lim_{n\rightarrow \infty} \frac{|S_n(k)|}{\pi(n)}? $$

1

There are 1 best solutions below

0
On BEST ANSWER

$\pi(n)$ is roughly $\frac{n}{\log n}$. We need at most $\log n$ bits to represent $n$ (or any number smaller than $n$). There are roughly $\binom{\log n}{k} \simeq (\log n)^k$ "$m$"s that have $k$ binary digits equal to $1$. Hence, $f(k) = 0,\,\forall k$. We do not need to count the primes.