Mid-Square with all bits set

Question

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

Answer 1

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

YES. One is AAAAAAAAAAAAAAAB5555555555555555₁₆, which square is 71C71C71C71C71C7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8E38E38E38E38E39₁₆.

---

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, 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	00101101012 01011010102
10	2	101010101101010101012 111000100100011000112
11	4	00101010101101010101012 00111000100100011000112 01010101011010101010102 01110001001000110001102
12	3	0001110001001000110001102 0100100011100010001010112 1100011011100000011110012
13	3	000011100010010001100011002 001100011011100000011110012 011000110111000000111100102
14	1	10100010001100101000100110002
16	1	101010101010101101010101010101012
17	2	00101010101010101101010101010101012 01010101010101011010101010101010102
19	1	111100100110010001011001001101100000112
21	4	0101000001010110111010100110001010110001112 0111011001110111100110000000000101110001012 1010000010101101110101001100010101100011102 1111011100101110011000010011011101101000012

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

Answer 2

Not an answer, but too long for a comment.

I can't see any tricks to do this other than a brute force computational approach. The naive approach would be to loop from $2^{96}$ to $2^{128}$ squaring each integer and checking. A more efficient approach in practice is to start with the number $2^{192}-2^{64}$ and then loop up to $2^{256}-2^{64}$ in steps of $2^{192}$ -- this only involves a loop of length $2^{64}$ rather than one of length $2^{128}$. For each term $n$ in the loop (thought of as a good approximation to a square) one computes the smallest integer square which is at least $n$ and then checks to see if the difference is less than $2^{64}$. But a loop of length $2^{64}$ is too long for me.

Here's some pari-gp code which takes an even length $n=2m$ and solves the analogous problem of searching for $n$-bit numbers which have 1's from the bit controlling $2^m$ (the "$m+1$st bit, I think, in the language of the OP) to the bit controlling $2^{3m-1}$.

g(n)=m=n/2;d=2^(3*m)-2^m;r=0;forstep(i0=d,2^(4*m)-2^m,2^(3*m),if(issquare(i0),s=sqrtint(i0),s=sqrtint(i0)+1);if(s^2-i0<2^m,print("yes -- s=",s);r=1;break()));if(r==0,print("no"));r

It (rather inelegantly) prints the smallest number it finds, if it finds one, and returns 1 or 0 depending on whether it finds one or not. It runs to $n=60$ quickly.

What motivated me to post this as an answer was the observation that in fact for most values of $n$ it could find an $n$-bit number which did the job. There's nothing for 2,4,6 but 181 works for 8 and 10 (this is related to the famous fact that $181^2=2^{15}-7$). There are then failures for $n=12,14,16,18$ but after that the garden gets rosier -- the numbers 699733 (twice),1853638,707276,170076312 work for 20,22,24,26,28, we have another failure at 30, and then 2863355221 works for 32,34; another failure at 36, success at 38, failure at 40 and then another big string of successes -- everything from 42 to 62 works. For example 363103060890424251 works for 60 and 62; in binary the square of this is 110010110010001100111000111111111111111111111111111111111111111111111111111111111111111001111101101110100101010011001 . This somehow indicates the problem in general -- you have a bunch of 1's in the middle but things look pretty random outside that region. The loop I posted above brute forces the first string of digits and then looks for the nearest square (because there will be at most one string of digits at the end making the number square).

I do not know a more sensible way of approaching this problem, however given that for most small values of $n$ there did seem to be a solution one might be cautiously optimistic that such an integer could exist. I suppose that on average the moment one passes $2^{96}$ the middle digits are kind-of random, so one might ask instead if you have an event which has a $2^{-128}$ chance of happening but you have $2^{128}-2^{96}$ attempts at it, what are the chances of you being lucky, and they're about $1-1/e$. So a sporting chance!

Answer 3

I'd like to point out why the case of middle bits being all ones is somewhat special and different from other fixed values of them. Also, there is an approach for finding a suitable numbers that may not exist for other fixed values of middle bits.

I'll use the notation of Kevin and additionally require that $m$ is even, say, $m=2k$ (in OP's question we have $m=64$ and $k=32$).

We need to find integers $x,y$ such that $0\leq x,y<2^m$ and $$x\cdot 2^{3m} + (2^{3m}-2^m) + y=z^2$$ for some integer $z$. In other words, we have $$0<(x+1) - \frac{z^2}{2^{3m}} = \frac{(2^m-y)}{2^{3m}} < \frac{1}{2^{2m}}.$$ Factoring the l.h.s. as $(\sqrt{x+1}-\frac{z}{2^{3k}})(\sqrt{x+1}+\frac{z}{2^{3k}})$ and noticing that the latter factor is at least 2 (for $x>0$), we get $$0<\sqrt{x+1} - \frac{z}{2^{3k}} < \frac{1}{2^{4k+1}}.$$ This tells us that $\frac{z}{2^{3k}}$ is a very good rational approximation to $\sqrt{x+1}$.

The above analysis may suggest to search for $\frac{z}{2^{3k}}$ among convergents and semiconvergents to a square root of an integer. We can base this search on two facts:

• A continued fraction for a square root has special forms: $[a;\overline{2a}]$, $[a;\overline{b,2a}]$, $[a;\overline{b,b,2a}]$, $[a;\overline{b,c,b,2a}]$, $[a;\overline{b,c,c,b,2a}]$, etc.
• Denominators of (semi)convergents satisfy a simple recurrence relation (involving terms of the continued fraction).

So, for each of the above continued fractions, we may to try find values of $a,b,c,\dots$ such that $2^t$ with $t\leq 3k$ appears among the denominators of (semi)convergents, from which will further get $z$ (as the numerator times $2^{3k-t}$) and hopefully solve the problem.

Remarks.

1. Values $t\leq 2k$ may work only for convergents, not semiconvergents (the rational approximation in this case becomes so good that only convergents may satisfy it).
2. There is a number of underwater stones here such as (i) not every set of values $a,b,c,\dots$ guarantee that we have a a continued fraction of the square root of an integer (in general, it's the square root of a rational); (ii) semiconvergents may not guarantee that the approximation is well enough for our purposes; etc.