Does there exist a (dis)proof of the following proposition:
For any positive integer N, there exists a prime P with larger number of significant bits than that of N, and N is a binary substring of P.
Example:
Let N = 4 [100 base 2]. Then we need to find some prime P >= 8 [1000 base 2], that would contain N as a substring [100] in binary. One such P would be 19 [10011 base 2] as it contains [100 base 2] as a substring.
If $n=(n_1...n_k)_2$ ($n$ written is basis $2$), then consider $N=2n+1=(n_1...n_k1)_2$. For $A=2^{k+2}$, we have that $(A,N)=1$ - since $N$ is odd - then, by Dirichlet's Theorem, there is a prime number of type $rA+N$ for some integer $r$, and it would contain $n$ as a substring by construction.