0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)... $\endgroup$ – lyrically wicked Oct 18 '18 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.