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

Question

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?

Answer 1

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<k(1+1/\sqrt{2})$ 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.

2. $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<k(\sqrt{2}+1)<n+1$, and (by multiplying to $\sqrt{2}-1$) we get $n\sqrt{2}<n+k$ 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$.

Answer 2

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<q$), $(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<r<1$.

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<r<1$, we get $\eta(l_m)=\lfloor{\sqrt2-(\sqrt2-1)r}\rfloor-\lfloor-r(\sqrt2-1)\rfloor=2$ as $0<r<1$

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.