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

54 Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

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).