Prove that the language $\{bin(p) \mid p\ \text{is prime}\}$ is not regular (prime numbers)

Question

Prove that the language $\{bin(p) \mid p\ \text{is prime}\}$ is not regular, where $bin(p)$ denotes the binary representation of $p$. I should use the pumping lemma. But I have a problem. Could you help me? Any clues?

Edit. This question is asking whether the set of primes is $2$-recognizable. A set $X$ of natural numbers is $k$-recognizable (or $k$-automatic) if the language consisting of the base-$k$ representations of the elements of $X$ is accepted by a finite automaton. More details on this theory can be found in the survey article

V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and $p$-recognizable sets of integers. Journées Montoises (Mons, 1992). Bull. Belg. Math. Soc. Simon Stevin 1 (1994), no. 2, 191--238.

The following example is an illustation of a much more general result of this theory. Let $$ T = \{n \in \mathbb{N} \mid \text{the binary representation of $n$ contains an odd number of $1$'s}\}. $$ Then the infinite binary word $t = t_0t_1t_2 \dotsm$ defined by $t_n = 1$ if and only if $n \in T$ is the Thue-Morse sequence, obtained by iterating the substitution $0 \to 01$ and $1 \to 10$.

Answer 1

Hint: If your pumping string is has length $>1$ then you can use the result that there is always a prime between $n$ and $2n$ for any natural number $n > 1$. So that only leaves the cases when your pumping string is either just '0' or '1'.

Answer 2

The answer is negative: the set of primes is not $2$-recognizable. A proof is given in [1], example 4 and in [2], Corollary 1.43. The proof relies on a property of $k$-recognizable languages due to Cobham (1972).

Let $(x_n)_{n \geqslant 0}$ be an increasing sequence of natural numbers. If the set $\{x_n \mid n \geqslant 0\}$ is $k$-recognizable, then either $$ \limsup_{n \to \infty}\ (x_{n+1} − x_n) < \infty \quad \text{or}\quad \limsup_{n \to \infty}\ \frac{x_{n + 1}}{x_n} > 1. $$ Let $p_n$ be the $n$-th prime number. Since $n! + 2, n!+3, \dotsm, n! +n$ are consecutive composite numbers, one has $\limsup_{n \to \infty}\ (p_{n+1} − p_n) = + \infty$. Moreover, it is a consequence of the prime number theorem that $\limsup_{n \to \infty}\ \frac{p_{n + 1}}{p_n} = 1$ (see Prime gap on Wikipedia).

[1] N. Rampersad, Abstract Numeration Systems in Language and Automata Theory and Applications, LNCS 6638, 65-79 (2011)

[2] M. Rigo, Formal Languages, Automata and Numeration Systems, Volume 2, John Wiley & Sons, 2014.

Conclusion. This proof answers the EDIT part of the question, but not the first part. Finding a proof relying on the pumping lemma is still an interesting challenge.