Los primos en binario

Question

Deje que $$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. $$ Deje que $ \pi (x)$ ser la función de número primo. Entonces, ¿qué se puede decir sobre $$f(k)= \lim_ {n \rightarrow \infty } \frac {|S_n(k)|}{ \pi (n)}? $$

Answer 1

$\pi(n)$ es aproximadamente $\frac{n}{\log n}$ . Necesitamos como máximo $\log n$ bits para representar $n$ (o cualquier número menor que $n$ ). Hay aproximadamente $\binom{\log n}{k} \simeq (\log n)^k$ " $m$ "s que tienen $k$ dígitos binarios iguales a $1$ . Por lo tanto, $f(k) = 0,\,\forall k$ . No necesitamos contar los primos.