Second digit of square numbers in binary yields $\sqrt2$

Question

Why do ratios of terms in sequences based on $2$nd binary digit of $2$nd power, converge to $\sqrt2$?

Update: Added at the bottom of the post a generalization for all other bases,powers, and digits.

---

Start with $k=1$, generate the sequences $a_d(n)$ by:

• increase $k$ by $1$, look at the binary representation of $k^2$, take the second digit
• keep repeating step one until the taken digit is $\ne$ compared to the previously taken digit

• then the number of digits you took is the new element in the sequence $a_d$, where $d$ is the value of the digit that was being taken (either $a_0$ or $a_1$)

• repeat the process for next term, but with the new digit, continuing with the $k$ you left with

The ratio of two consecutive terms in both sequences $a_0,a_1$ seems to converge to $\sqrt2$.

Why is this the case? Can we show it truly converges to $\sqrt2$ ?
How can we express this algorithm/sequences in mathematical expressions?

In other words, $a_0$ is the number of consecutive $0$'s appearing as the second digit in binary representations of squares of natural numbers, and $a_1$ is the same thing for $1$'s.

The computed terms are below: (python code on repl.it)

a_1 = 1, 1, 2, 2, 3, 4, 6, 8, 12, 17, 25, 34, 49, 68, 97, 137, 194, 274, 388, 548, 776, 1097, 1552, 2195, 3104, 4390, 6208, 8780, 12417, 17560, 24834, 35120, 49668, 70241, 99336, 140482, 198672, 280965, 397344, 561930, 794689, 1123860, 1589379, 2247720, 3178757, 4495441, 6357514, 8990882, 12715028, 17981765, 25430057, 35963531, 50860114, 71927063,...
a_0 = 3, 1, 2, 2, 4, 5, 8, 10, 15, 20, 29, 40, 58, 81, 116, 162, 231, 325, 461, 651, 921, 1302, 1842, 2603, 3683, 5207, 7365, 10415, 14729, 20830, 29458, 41660, 58916, 83319, 117832, 166638, 235663, 333276, 471325, 666553, 942649, 1333106, 1885297, 2666212, 3770594, 5332424, 7541187, 10664849, 15082374, 21329697, 30164747, 42659393, 60329493, 85318786,...

Last computed terms from above:

$$ \frac{a_1(54)}{a_1(53)}=\frac{71927063}{50860114}=1.414213562321\dots\approx\sqrt2=1.414213562373\dots$$

$$ \frac{a_0(54)}{a_0(53)}=\frac{85318786}{60329493}=1.414213542288\dots\approx\sqrt2=1.414213562373\dots$$

The first one seems to converge a bit faster. ($10$ decimal places vs $7$ decimal places for $n=54$)

How good are these fraction approximations?

Is there a closed form for these sequences?

---

Trying to find a recurrence relation:

One thing I've noticed in the successive ratios of the terms is that if we denote one as $\frac{a}{b}$, then the next one would always be $\frac{2b}{a}+c_n$, where $c_n$ is $\frac{-1}{a},\frac{1}{a}$ or $0$.

For $a_1$ I've observed values for $c_n$ in ratios in order: $c_n=$0,0,-,0,0,0,0,+,+,0,-,0,+,+,0,0,0,0,0,0,+,+,0,0,0,0,+,0,0,0,0,+,0,0,...

You can see the ratios between successive terms in $a_1$ below:

Where the left side is the ratio of $a_1(n)/a_1({n-1})$, and the right side are operations to reach the next term in the sequence, where c=1/a, if we represent the ratios as a/b;

1,       ^-1,*2
2/1,     ^-1,*2
2/2,     ^-1,*2-c
3/2,     ^-1,*2
4/3,     ^-1,*2
6/4,     ^-1,*2
8/6,     ^-1,*2
12/8,    ^-1,*2+c
17/12,   ^-1,*2+c
25/17,   ^-1,*2
34/25,   ^-1,*2-c
49/34,   ^-1,*2
68/49,   ^-1,*2+c
97/68,   ^-1,*2+c
137/97,  ^-1,*2
194/137, ^-1,*2
274/194, ^-1,*2
388/274, ^-1,*2
548/388, ^-1,*2
776/548, ^-1,*2
1097/776, ^-1,*2+c
1552/1097, ^-1,*2+c
2195/1552, ^-1,*2
3104/2195, ^-1,*2
4390/3104, ^-1,*2
6208/4390, ^-1,*2
8780/6208, ^-1,*2+c
12417/8780, ^-1,*2
17560/12417, ^-1,*2
24834/17560, ^-1,*2
35120/24834, ^-1,*2
49668/35120, ^-1,*2+c
70241/49668, ^-1,*2
99336/70241, ^-1,*2
etc.

If we can somehow find the pattern for which terms we add or subtract $c$, we could define the ratio sequences with reversal of the fractions, multiplying by $2$, and adding $c$.

With the numerators/denominators of these ratio sequences, we could define $a_1$.
A similar $c_n\in\{-c,0,c\}$ sequence exist for $a_0$.

---

Generalization

Consider the algorithm above that generates sequences $a_d$.

• Above, we were looking at the second digit, $D=2$. Lets consider any $D\ge2$ digit.

• Looking at powers $P\in\mathbb N$, lets observe the numbers $k^P$

• Also, consider bases $b\ge2$

Generate $a_d$ as explained above, observing the $D$ digit in $k^P$ in base $b$:

Then, the ratios of terms seem to converge for all sequences $d$ :

$$ \frac{a_d(n)}{a_d(n-(b-1)\cdot b^{D-2})}=\sqrt[P]{b}$$

As $n\to\infty$, for all $d$ sequences, and all variables considered above.

How can this observation be explained/proved ?

---

---

Note that $P=1$ is trivial as the sequences are of form $a_d=b^m$, where $m$ changes periodically.

For example, base $b=3$ sequences for $P=1$, when $D=2$ look like:

a_0 = 1, 1, 3, 3, 9, 9, 27, 27, 81, 81, 243, 243, 729, 729, 2187, 2187, 6561, 6561,...
a_1 = 1, 1, 3, 3, 9, 9, 27, 27, 81, 81, 243, 243, 729, 729, 2187, 2187, 6561, 6561,...
a_2 = 1, 1, 3, 3, 9, 9, 27, 27, 81, 81, 243, 243, 729, 729, 2187, 2187, 6561, 6561,...

Note that the period is $(b-1)\cdot b^{D-2}$, which is found in the term ratio above.

How can we calculate sequences $a_d$ when $P\ge2$ for some $D\ge2$ in some $b\ge2$?

Answer 1

Per request, here is a more detailed solution. Let me just tackle the general problem from the very beginning. I will use slightly different notation - it's easy to see that in the limit it's basically the same as yours.

Pick a base $b$, a digit position of interest $D$, a digit $d$ and the exponent $P$. The $D$-th base $b$ digit from the left in the number $n$ is going to be equal to $D$ if, for some $D-1$-digit number $N$ and some integer $e>0$, $$Nb^{e+1}+db^e\leq n<Nb^{e+1}+(d+1)b^e.$$ Let $A(e,N)$ be the number of perfect $P$-th powers in this interval. We are interested in certain ratios of those numbers.

Here is an easy question: how many $P$-th powers are there between $0$ and $k$ exclusive? The answer is exactly $\lceil\sqrt[P]{k}\rceil-1$. Hence the number of perfect powers between $k$ inclusive and $l$ exclusive is exactly $\lceil\sqrt[P]{l}\rceil-\lceil\sqrt[P]{k}\rceil$. Therefore, $$A(e,N)=\lceil\sqrt[P]{Nb^{e+1}+(d+1)b^e}\rceil-\lceil\sqrt[P]{Nb^{e+1}+db^e}\rceil,$$ hence $$\sqrt[P]{Nb^{e+1}+(d+1)b^e}-\sqrt[P]{Nb^{e+1}+db^e}-1\leq A(e,N)\\\leq \sqrt[P]{Nb^{e+1}+(d+1)b^e}-\sqrt[P]{Nb^{e+1}+db^e}+1.$$ We can now say that the limit of the ratios of $A(e,N)$ is the same as the limit of ratios of $B(e,N)=\sqrt[P]{Nb^{e+1}+(d+1)b^e}-\sqrt[P]{Nb^{e+1}+db^e}$ (the gist here is that we are given a sequence bounded between $\frac{a_n-1}{a_{n-1}+1}$ and $\frac{a_n+1}{a_{n-1}-1}$, which has the same limit as $\frac{a_n}{a_{n-1}}$ as $a_n\to\infty$).

Let $x=\sqrt[P]{Nb^{e+1}+(d+1)b^e},y=\sqrt[P]{Nb^{e+1}+db^e}$. We calculate, using $x^P-y^P=(x-y)(x^{P-1}+x^{P-2}y+\dots+y^{P-1})$, $$B(e,N)=x-y=\frac{x^P-y^P}{x^{P-1}+x^{P-2}y+\dots+y^{P-1}}=\frac{b^e}{x^{P-1}+x^{P-2}y+\dots+y^{P-1}}\\\sim\frac{b^e}{Py^{P-1}}=\frac{b^e}{(Nb^{e+1}+db^e)^{1-1/P}}=\frac{b^{e/P}}{(Nb+d)^{1-1/P}},$$ where $\sim$ means that the ratio of the left and right hand side goes to one, and that follows from $x\sim y$ (which is almost obvious).

Now, which ratio of the numbers are we interested in exactly? In your question, the difference of arguments is $(b-1)\cdot b^{D-2}$, so, with the intervals I have defined above, we have to ask which interval is $(b-1)\cdot b^{D-2}$-th in turn after the one for $e,N$. I leave it for you to note that this will give us precisely the interval for $e+1,N$. So the ratio of $B$'s is: $$\frac{B(e,N)}{B(e+1,N)}=\frac{b^{e/P}/(Nb+d)^{1-1/P}}{b^{(e+1)/P}/(Nb+d)^{1-1/P}}=b^{1/P}=\sqrt[P]{b}.$$

Phew!