# Is it possible to disprove the existence of “infinitely expandable” prime numbers?

Assuming that the binary representation of any odd prime starts with $$1$$ and ends with $$1$$, we can define a function $$F(n)$$ that outputs the number of bits between the first and last bits of the binary representation of $$n$$. For example, $$F(3) = 0$$, $$F(7) = 1$$, $$F(37) = 4$$ etc.

Then we can note that if a prime $$x$$ is greater than $$3$$ and $$y$$ is greater than $$0$$, but not greater than $$F(x)$$, then we can assume that the notation $$b_{x.y}$$ refers to the $$y$$-th bit between the first and last bits of the binary representation of $$x$$. For example, $$\begin{array}{l} b_{5.1} = 0,\\ b_{7.1} = 1,\\ b_{37.1} = 0,\\ b_{37.2} = 0,\\ b_{37.3} = 1,\\ b_{37.4} = 0,\\ \ldots \end{array}$$

Then we define an infinite family of all possible finite bitstrings ordered in the shortlex order:

$$\begin{array}{l} {B_0} = 0,\\ {B_1} = 1,\\ {B_2} = 00,\\ {B_3} = 01,\\ {B_4} = 10,\\ {B_5} = 11,\\ {B_6} = 000,\\ {B_7} = 001,\\ \ldots \end{array}$$

Assuming that the symbol $$\mathbin\Vert$$ denotes a standard concatenation operation (e.g. $$1 \mathbin\Vert B_1 \mathbin\Vert B_2$$ denotes the number $$1100$$ in base $$2$$, which corresponds to the natural number $$12$$ in base $$10$$), I call any odd prime number $$X$$ “infinitely expandable” if and only if there exists at least one constant (fixed) number $$t$$ such that $$0 \leq t \leq F(X)$$ and for all $$i \geq 0$$, the number $$\begin{array}{l} N_{X.i.t} = 1 \mathbin\Vert b_{X.1} \mathbin\Vert b_{X.2} \mathbin\Vert \ldots\\ \ldots \mathbin\Vert b_{X.(t-1)} \mathbin\Vert b_{X.t} \mathbin\Vert B_i \mathbin\Vert b_{X.(t+1)} \mathbin\Vert b_{X.(t+2)} \mathbin\Vert \ldots\\ \ldots \mathbin\Vert b_{X.(F(X)-1))} \mathbin\Vert b_{X.(F(X))} \mathbin\Vert 1\\ \end{array}$$

is prime.

In other words, the above formula implies that if we fix the position $$t$$ between the first and last bits of the binary representation of $$X$$, then, no matter what $$i$$ we choose, we can insert the bitstring $$B_i$$ in the position $$t$$ in the bitstring that encodes the binary representation of $$X$$, and the resulting bitstring will always represent some prime number in base $$2$$.

Note that $$t = 0$$ implies that $$B_i$$ should be inserted immediately after the first bit of the binary representation of $$X$$, that is, before the bit $$b_{X.1}$$. Consequently, $$t = F(X)$$ implies that $$B_i$$ should be inserted before the last bit of the binary representation of $$X$$, that is, immediately after the bit $$b_{X.(F(X))}$$.

For example, if $$t=0, i=2, X=37$$, then we should explore the number $$N_{37.2.0} = 1 \mathbin\Vert 00 \mathbin\Vert 0010 \mathbin\Vert 1 = 10000101_2 = 133_{10}.$$ Similarly, if $$t=1, i=5, X=37$$, then we should explore the number $$N_{37.5.1} = 1 \mathbin\Vert 0 \mathbin\Vert 11 \mathbin\Vert 010 \mathbin\Vert 1 = 10110101_2 = 181_{10}.$$

I should emphasize that the value of $$t$$ is fixed for all $$B_i$$ that will be inserted in the binary representation of $$X$$. That is, once we have chosen the value of $$t$$, we are not allowed to insert bitstrings $$B_i$$ in another position. (But note that if there exist more than one valid choices for the initial value of $$t$$, we can choose and fix any such value from multiple possibilities.)

The question: does there exist at least one “infinitely expandable” prime number? If yes, why? If no, is it possible to disprove the existence of such numbers?

You start with an $$m$$-bit number and insert all possible bit strings at a specific position of that number. This produces $$2^n$$ bit strings of length $$m+n$$ for each $$n$$. Thus we need at least $$2^n$$ primes $$<2^{m+n}$$, so $$\pi(2^{m+n})=o(2^n)$$, which contradicts $$\pi(2^{n+m})=O(\frac{2^{m+n}}{m+n})$$ (because $$m+n\gg 2^m$$ as $$n$$ grows).
• Interesting. I thought that the proof would describe the process when, if we insert all possible $B_i$ in a particular position, we should sooner or later obtain some number which will be divisible by $3$ (using this fact)... – lyrically wicked Oct 18 '18 at 6:48