# Sequence of $k^2$ and $2k^2$ ordered in ascending order

Let $$\eta(n)$$ be A006337, an "eta-sequence" defined as follows: $$\eta(n)=\left\lfloor(n+1)\sqrt{2}\right\rfloor-\left\lfloor n\sqrt{2}\right\rfloor$$ Sequence begins $$1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1$$ Let $$a(n)$$ be A091524, $$a(m)$$ is the multiplier of $$\sqrt{2}$$ in the constant $$\alpha(m) = a(m)\sqrt{2} - b(m)$$, where $$\alpha(m)$$ is the value of the constant determined by the binary bits in the recurrence associated with the Graham-Pollak sequence.

Sequence begins $$1, 1, 2, 2, 3, 4, 3, 5, 4, 6, 7, 5, 8, 6, 9, 7, 10, 11, 8, 12, 9, 13$$ Then we have an integer sequence given by $$b(n)=(a(n))^2\eta(n)$$ Sequence begins $$1, 2, 4, 8, 9, 16, 18, 25, 32, 36, 49, 50, 64, 72, 81, 98, 100, 121, 128, 144, 162, 169$$ I conjecture that $$b(n)$$ is a sequence of $$k^2$$ and $$2k^2$$ ordered in ascending order.

Is there a way to prove it?

Denote by $$f(n)$$ the sequence of squares and double squares in ascending order. We have to prove that $$f(n)=b(n)=(a(n))^2\eta(n)$$. Consider two cases.

1. $$f(n)=k^2$$. Then the number of squares and double squares not exceeding $$k^2$$ equals $$n$$, that is, $$n=k+\lfloor k/\sqrt{2}\rfloor$$. Therefore $$n that is equivalent (by multiplying to $$2-\sqrt{2}$$) to $$n\sqrt{2}>2n-k$$, and $$\lfloor n\sqrt{2}\rfloor\geqslant 2n-k$$. On the other hand, $$n+1>k(1+1/\sqrt{2})$$ that analogously yields $$(n+1)\sqrt{2}>2(n+1)-k$$ and $$\lfloor (n+1)\sqrt{2} \rfloor\leqslant 2n-k+1$$. Since also $$\lfloor (n+1)\sqrt{2} \rfloor\geqslant \lfloor n\sqrt{2} \rfloor+1\geqslant 2n-k+1$$, this implies that $$\eta(n)=1$$. According to OEIS we have $$a(n)=a(\lfloor k(1+1/\sqrt{2}\rfloor)=k$$, thus $$(a(n))^2\eta(n)=k^2$$ as needed.
1. $$f(n)=2k^2$$. Then the number of squares and double squares not exceeding $$2k^2$$ equals $$n$$, that is, $$n=k+\lfloor k\sqrt{2}\rfloor$$. So, $$n, and (by multiplying to $$\sqrt{2}-1$$) we get $$n\sqrt{2} and $$(n+1)\sqrt{2}>(n+1)+k$$. This yields $$\eta(n)=2$$. Again by OEIS we get $$a(n)=a(\lfloor k(1+\sqrt{2}\rfloor)=k$$ and $$(a(n))^2\eta(n)=2k^2$$.
• Hello Fedor! Thank you for answer! Of course you mean $a(n)=a(\lfloor k(1+\sqrt{2}\rfloor)=k$ instead of $a(n)=a(\lfloor k(1+\sqrt{2}\rfloor)=2$? Commented Dec 22, 2021 at 13:59
• Hello! Of course, fixed. Commented Dec 22, 2021 at 15:51

An explicit formula is given in this page which is given in the OEIS page you have referred to.

The explicit formula for the Graham-Pollak sequence is $$a_n=\lfloor{\tau(m)(2^{\frac{n}{2}}+2^{\frac{(n-1)}{2}})}\rfloor$$. Hence, $$b_n(m)=a_{2n+1}(m)-2a_{2n-1}(m)=\lfloor{\tau(m)(\sqrt{2}+1)2^n}\rfloor-\lfloor{\tau(m)(\sqrt{2}+1)2^{n-1}}\rfloor$$.

Now, the sequence $$\tau(m)$$ is the set $$\mathbb N \cup \sqrt{2} \mathbb N$$ arranged in ascending order.

Claim 1: We can write $$\tau(m)=\chi(m)\sqrt{\eta(m)}$$, where $$\chi(m)$$ is a sequence of natural numbers with each natural number appearing exactly twice.

The set $$\chi(m)$$ is such that,if for some $$m$$, $$\chi(m)=k$$ is the first appearence $$\eta(m)=1$$ and if it's second appearence $$\eta(m)=2$$.

For the sequence $$\{b_n\}(m)=a_{2n+1}(m)-2a_{2n-1}(m)$$ we would show that $$b_n(m)=b_n(m'),\forall n\in \mathbb N$$, where $$(m,m')$$ is such that $$\chi(m)=k=\chi(m'), m'>m,k \in \mathbb N$$.

We have, $$b_n(m)=\lfloor{\Lambda_n(m)}\rfloor-2\lfloor{\Lambda_n(m)/2}\rfloor$$ where $$\lfloor{\Lambda_n(m)}\rfloor=\lfloor{\tau(m)(\sqrt{2}+1)2^n}\rfloor$$. If $$\lfloor{\Lambda_n(m)}\rfloor$$ is even $$b_n(m)=0$$, if it is odd, $$b_n(m)=1$$.

Now, $$\Lambda(m')=\sqrt(2)\chi(m)\sqrt{\eta(m)}(\sqrt{2}+1)2^n$$. For, $$m,m'$$ pair $$\eta(m)=1, \chi(m) \in \mathbb N$$. Hence, $$\Lambda(m')=\Lambda(m)+\chi(m)2^n$$. Hence, $$\lfloor{\Lambda(m)}\rfloor$$ and $$\lfloor{\Lambda(m')}\rfloor$$ has same parity, implying that $$\{b_n\}(m)=\{b_n\}(m') \forall n \in \mathbb N$$....$$(1)$$

(There is no $$q$$ other than $$m'$$ such that $$\{b_n\}(m)=\{b_n\}(q)$$ for all $$n$$. Because the parity can't be same for all n when $$\tau(q) = \sqrt{2}$$and $$\tau(m)$$ and $$\eta(m)=1$$ isn't true simultaneously).

As the sequence $$a(m)$$ (which is asked) contains all the natural numbers in ascending (meaning that $$p$$ appears before $$q$$ if $$p), $$(1)$$ implies that $$\{a(m)\}=\{\chi(m)\}$$. As,the asked sequence $$\{b(n)\}=\{\tau(n)^2\}$$, it just requiers to prove Claim 1.

To do so, we have to prove $$l_{m+1}-l_{m}=\eta(m)+1$$, where $$l_i$$ is such that $$\eta(l_i)$$ is the $$i$$-th $$2$$ in the $$\eta$$ sequence.

Edit: The proof of Claim-1: Let's assume $$l_i$$ be a sequence such that $$l_{m+1}-l_{m}=\eta(m)+1\Rightarrow l_m=m-1+\sum_{i}^{m-1}\eta(i)+2$$. We will show that $$l_m$$ is the $$m$$-th $$2$$ in the $$\eta(n)$$ sequence.

First of all we have, $$\sum_{i=1}^{m-1}\eta(i)=\lfloor{m\sqrt{2}}\rfloor-1$$. Also assume,$$m\sqrt{2}=a+r, a\in \mathbb N, 0.

Hence, $$l_m=m+a$$.So, $$\eta(l_m)=\lfloor{(m+a+1)\sqrt{2}}\rfloor-\lfloor(m+a)\sqrt{2}\rfloor$$.

or, $$\eta(l_m)=\lfloor{\sqrt2+m\sqrt{2}+(m\sqrt2-r)\sqrt2}\rfloor-\lfloor m\sqrt{2}+(m\sqrt2-r)\sqrt2\rfloor$$.

Using $$m\sqrt{2}=a+r, a\in \mathbb N, 0, we get $$\eta(l_m)=\lfloor{\sqrt2-(\sqrt2-1)r}\rfloor-\lfloor-r(\sqrt2-1)\rfloor=2$$ as $$0

Now, we just need to show these are the only numbers having $$\eta=2$$.

We have, $$l_{m+1}-l_m=\eta(m)+1$$. We would show that $$\eta(l_m+c)=1$$ for all $$c\leq \eta(m)$$. If $$\eta(m)=1, c=1$$. In that case like previous steps we get $$\eta(l_m+1)=\lfloor{2\sqrt2-(\sqrt2-1)}\rfloor-\lfloor\sqrt2-r(\sqrt2-1)r\rfloor$$, as $$r<1$$ we have $$\eta(l_m+c)=1$$.

If $$\eta(m)=2, c=1 \text{or} 2$$. We have similarly $$\eta(l_m+2)=\lfloor{3\sqrt2-(\sqrt2-1)r}\rfloor-\lfloor{2\sqrt2-r(\sqrt2-1)}\rfloor=1$$ (because $$\eta(m)=2 \Rightarrow 1>r>2(\sqrt2-1)$$ and so, $$3<3\sqrt2-r(\sqrt2-1)<4$$ while $$2<2\sqrt2-r(\sqrt2-1)<3$$).

This implies that $$l_m$$ is the $$m$$-th $$2$$ in $$\eta$$ sequence, proving the Claim-1, and so the asked conjecture.