8
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ Please note that the second binary digits of the first few squares are 0,0,0,1,0,1,...starting with three consecutive 0, just the opposite of what your notation $a_1$ suggests. Your code is very inefficient, you don't need the whole binary representation to determine the second bit. The second bit of a positive integer $m$ would be "(m<(m^(m>>1)))?1:0" in C or Java, and the syntax in Python should be "1 if m<(m^(m>>1)) else 0". For generalization, you replace 1 by $D-1$. $\endgroup$ – Professor Vector Dec 18 '17 at 6:38
  • $\begingroup$ @ProfessorVector I reversed the order of sequences in my code and mistaken the $0$ index for $1$ and vice versa. Thanks for noticing. I've corrected the indexes in the post, and added your suggestion into the code. $\endgroup$ – Vepir Dec 18 '17 at 7:59
9
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ It would be nice if you included further details. Also, wondering, could one calculate exactly terms for some $a_d(n)$ for some $(P,D,b)$, when $P\gt1$ or can we at best estimate the $n$th term, unless we iterate over all powers for such case? $\endgroup$ – Vepir Dec 17 '17 at 23:03
  • 2
    $\begingroup$ @Vepir Took me a while, but I have written up the details. As you can see there, it is possible to express the numbers exactly using the ceiling function. $\endgroup$ – Wojowu Dec 23 '17 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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