Numbers whose binary complement is larger than the binary complement of its square.

OEIS sequence A323192 lists numbers whose binary complement is larger than the binary complement of its square. The binary complement is defined as flipping each bit in its binary representation. For instance, 29 is 11101 in binary, so its binary complement is 2 which is 00010 in binary. Note that the binary complement function is not one-to-one, for instance the binary complement of 61 (111101 in binary) is also 2.  This function is not exactly the same as 1's complement in computer arithmetic, since the number of bits flipped is not fixed but is equal to the number of bits in the binary representation of the number.

Giovanni Resta noted that the first 13 terms of sequence A323192 are of the form $\lfloor\sqrt{2^k-1}\rfloor$. It turns out this is true in general. In fact we can prove more. In particular, we can show that the terms of this sequence corresponds to numbers of the form $\lfloor\sqrt{2^{2k-1}}\rfloor$ which are larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$ with $k > 0$.

This result follows from the following theorem:

Theorem: if $n$ is a term of OEIS sequence A323192, then $n$ is of the form $\lfloor\sqrt{2^{2k-1}}\rfloor$ for some $k > 0$. In addition, $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if it is larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$.

Proof: suppose $n$ has $k$ bits in its binary representation, i.e. $2^{k-1} \leq n < 2^k$. Then $n^2$ has either $2k-1$ or $2k$ bits.

First we show that if $n$ is a term of the sequence, then $n^2$ has $2k-1$ bits. Suppose $n^2$ has $2k$ bits, i.e. $n^2 \geq 2^{2k-1}$. Then $2^{2k} - 1 - n^2 < 2^k - 1 - n$. This is rearranged as $n^2 - n + 2^k - 2^{2k} > 0$. Solving this quadratic inequality leads to $n > 2^k$ which contradicts the fact that $n$ has $k$ bits.

Thus $n^2 < 2^{2k-1}$ and $2^{2k-1} - 1 - n^2 < 2^k - 1 - n$. Solving this inequality and combining it with $n < \sqrt{2^{2k-1}}$ shows that $n$ must satisfy $\sqrt{2^{2k-1}} > n >  \frac{1}{2}+ \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$.

To complete the proof, we need to show that for each $k$, there is at most one integer satisfying this inequality. This is easily verified for $k = 1$. Assume that $k > 1$. Let $a = \sqrt{2^{2k-1}}$ and $b = \frac{1}{2} + \sqrt{\frac{1}{4}+ 2^{2k-1} - 2^k}$.

Using the identity $\sqrt{x} - \sqrt{y} = (x-y)/(\sqrt{x}+\sqrt{y})$ it follows that $a-b = -\frac{1}{2} + \frac{2^k - \frac{1}{4}}{\sqrt{2^{2k-1}}+\sqrt{\frac{1}{4}+ 2^{2k-1} - 2^k}} < -\frac{1}{2} + \frac{2^k}{\sqrt{2^{2k-1}} + \sqrt{2^{2k-1}-2^k}}$.

Since $k \geq 2$, $\sqrt{2^{2k-1}-2^k} = \sqrt{2^{2k-1}(1-2^{1-k})} \geq \sqrt{\frac{1}{2}}\ \sqrt{2^{2k-1}}$. This implies that $a-b < -\frac{1}{2} + \frac{2^k}{\frac{\sqrt{2}+1}{\sqrt{2}}\sqrt{2^{2k-1}}} = \frac{2\sqrt{2}}{\sqrt{2}+1} - \frac{1}{2} < 0.672$. Thus it follows that there is at most one integer in the range between $b$ and $a$.

The above discussion also completely characterizes the sequence. $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if $\sqrt{2^{2k-1}}-\lfloor\sqrt{2^{2k-1)}}\rfloor < a-b$ where $a-b$ is as defined above.

The criterion can be simplified as:
$\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if it is larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$. This concludes the proof.$\blacksquare$

Note that $a-b \rightarrow \frac{1}{2}$ as $k \rightarrow \infty$, i.e. for large $k$, the fractional part of $\sqrt{2^{2k-1}}$ should be less than about $\frac{1}{2}$ in order for the integer part to be a term.

The numbers $k$ such that $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term of OEIS sequence A323192 are listed in OEIS sequence A323062.