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?


2 Answers 2


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.
  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<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$.
  • $\begingroup$ 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$? $\endgroup$ Commented Dec 22, 2021 at 13:59
  • $\begingroup$ Hello! Of course, fixed. $\endgroup$ 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<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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.