Is there a positive 128-bit integer whose square has all middle bits equal to 1?


(The "middle bits" are naturally the 65th bit through the 192nd bit, defining
the 1st bit as the least significant bit of the full integer.)



Mid-Square with all bits set

> 
> Is there a positive 128-bit integer whose square has all middle bits equal to 1?
> 
> 
> 


***YES***. One is AAAAAAAAAAAAAAAB555555555555555516, which square is 71C71C71C71C71C7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8E38E38E38E38E3916.




---


It's asked if there are integers $n$ such that $0<n<2^{2k}$ and $(n^2\bmod2^{3k})\ge2^{3k}-2^k$, in the case $k=128/2$.


As noted in [comment by Max Alekseyev](https://mathoverflow.net/posts/comments/1073379?noredirect=1), that holds for $k\equiv 4\pmod6$ (thus including the question's $k=128/2$), because the integer
$$n=\frac{2^{2k+1}+2^{k+1}-1}3$$
does the trick. It's representation in base $4$ consists of $k/2-1$ digits $2$, one digit $3$, and $k/2$ digits $1$. It holds
$$n^2=\frac{8^k-1}{9}2^{k+2}+\frac{8^{k+1}+1}9$$
which representation in base $4$ consists of the digit $1$; the digits $301$ repeated $(k-4)/6$ times; the digit $3$ repeated $1+k$ times; the digit $2$; the digits $032$ repeated $(k-4)/6$ times; the digit $1$. It follows the center $2k$ bits are set, with three more on the left and one more on the right.


We can't use this to conclude exactly how many $n$ there are, or/and for other values of $k$, or/and for an arbitrary value in the middle of the square.


Here is a brute force search for $k\le21$:





| $k$ with a solution | #solution(s) | possible $n$ |
| --- | --- | --- |
| 4 | 1 | 101101012 |
| 5 | 2 | 0010110101201011010102 |
| 10 | 2 | 101010101101010101012111000100100011000112 |
| 11 | 4 | 00101010101101010101012001110001001000110001120101010101101010101010201110001001000110001102 |
| 12 | 3 | 000111000100100011000110201001000111000100010101121100011011100000011110012 |
| 13 | 3 | 000011100010010001100011002001100011011100000011110012011000110111000000111100102 |
| 14 | 1 | 10100010001100101000100110002 |
| 16 | 1 | 101010101010101101010101010101012 |
| 17 | 2 | 0010101010101010110101010101010101201010101010101011010101010101010102 |
| 19 | 1 | 111100100110010001011001001101100000112 |
| 21 | 4 | 0101000001010110111010100110001010110001112011101100111011110011000000000010111000101210100000101011011101010011000101011000111021111011100101110011000010011011101101000012 |



We see and could prove that if $n$ is a solution for $k=k\_a+1$ with $n<2^{2k\_a}$, then $n$ is a solution for $k=k\_a$. And if $n$ is a solution for $k=k\_a+1$ with $n<2^{2k\_a+1}$ and $n$ even, then $n/2$ is a solution for $k=k\_a$. That explains why more often than not, if $n=n\_a$ is a solution for $k=k\_a$, then $n=n\_a$ or/and $n=2n\_a$ is/are a solution for $k=k\_a+1$.


