Converting an integer $N$ into binary and then reading the result as a base-10 number $N_2$, the prime $N=3$ gives $N_2=11$ (which is also prime) and $N=5$ gives $N_2=101$. Are $3$ and $5$ the only prime numbers whose binary expansions, read as decimals, also give primes? If so, how is it possible to prove it?
$\endgroup$ 61 Answer
$\begingroup$A naive analysis suggests that there should be infinitely many of these: there are $2^{n-2}$ numbers of $n$ (binary) digits to test (note that every $n$-digit number must start with $1$, and it has to end with $1$ or else it'll be even). An 'average' number of size approximately $10^n$ is prime with probability $\approx\dfrac1{\ln(10^n)}=\dfrac1{n\ln10}$ by the PNT, and likewise one of size roughly $2^n$ is prime with probability $\approx\dfrac1{n\ln2}$. Assuming that these two events are independent, then the probability that a length-$n$ bitstring is prime in both representations is $\dfrac1{\ln2\ln10}\cdot\dfrac1{n^2}$ and so we should expect about $\dfrac{2^n}{4\cdot\ln2\cdot\ln10\cdot n^2}$ such 'double primes' of $n$ digits. Since $2^n\gg n^2$, this should remain positive for every $n$; in fact, it increases exponentially, so summing over $n$ and letting $n\to\infty$ we should expect an infinite number of these primes.
On the other hand, it's almost a certainty that no one has proved there are infinitely many, and it would be a shock if anyone were able to: the current machinery of number theory has proven ill-equipped to deal with 'exponential' questions about primes (for instance, the questions of whether there are infinitely many Mersenne primes or Fibonacci primes), and likewise even seemingly simple questions about representations of numbers in multiple bases (for instance, 'does the base-3 expansion of $2^n$ contain a digit 2 for all $n\gt8$?') are not only unsolved but even without any reasonable known 'plan of attack'. Since your question lies at the intersection of these two bumpy roads, it's fair to say that it would take a revolution in our knowledge of number theory to definitively answer it.
$\endgroup$
