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.

## No comments:

## Post a Comment