# Extract a Pattern of Iterated continued fractions from convergents

I have been working on an article at https://oeis.org/wiki/Table_of_convergents_constants
where I posted a table of "convergents constants" (defined at https://oeis.org/wiki/Convergents_constant) for a few numbers.

It would be nice to support the article with some quality analysis.

Before June 9, 2011, was starting to extract and clearly define a pattern to these constants cf the article. I've made some progress in finding the patterns to their continued fractions. Can you find the next pattern $a_6(n)$? If it is like $a_5(n)$ it will be dependent on the moduli of some natural number $K$.

Beginning with $n=0$, the sequence is:
Edit [I made this to hard with an error. I should have said, Beginning with $n=1$, the sequence is:]

1, 2, 1, 3, 3, 9, 4, 1, 5, 2, 7, 9, 8, 1, 9, 2, 11, 2, 12, 1, 13, 2, 15, 16, 16, 1, 17, 2, 19, 1, 20, 1, 21, 2, 23, 1, 24, 1, 25, 2, 27, 1, 28, 1, 29, 2, 31, 1, 32, 1, 33, 2, 35, 2, 36, 1, 37, 2, 39, 2, 40, 1, 41, 2, 43, 2, 44, 1, 45, 2, 47, 2, 48, 1, 49, 2, 51, 3, 52, 1, 53, 2, 55, 3, 56, 1, 57, 2, 59, 3, 60, 1, 61, 2, 63, 3, 64, 1, 65, 2, 67, 4, 68 ,1, 69, 2, 71, 4, 72, 1, 73, 2, 75, 4, 76, 1, 77, 2, 79, 4, 80, 1, 81, 2, 83, 4, 84, 1, 85, 2, 87, 5, 88, 1, 89, 2, 91, 5, 92, 1, 93, 2, 95, 5, 96, 1, 97, 2, 99, 5, 100, 1, 101, 2, 103, 6, 104, 1, 105, 2, 107, 6, 108, 1, 109, 2, 111, 6, 112, 1, 113, 2, 115, 6, 116, 1, 117, 2, 119, 7, 120, 1, 121, 2, 123, 7, 124, 1, 125, 2, 127, 7, 128, 1, 129, 2, 131, 7, 132, 1.

The function for the pattern to the sequence could be piecewise defined, as the last known piece of $a_5(n)$ started at $n=24$. Whether the functions for $a_5(n)$ and $a_6(n)$ can be defined without piecewise functions has yet to be answered as far as I know.

Addendum June 10, 2011 [Now that I have $a_1(n)$ through $a_6(n)$, I find it difficult to find what they all have in common. Perhaps there is an easier pattern to find $a_1(n)$ from $a_0(n)$, $a_2(n)$ from $a_1(n)$, ...? Can you help me find it? I will ask something like this in the talk page soon.]

-
Apart from typos and the fact that any understandable explanation should use simple examples, you cannot use "truly random" without explanation and you cannot used "it is believed" instead of saying whether this is your personal conjecture or someone else's conjecture. I will vote to close, but I will certainly vote to reopen if you edit your question, explain this conjecture and ask us if it makes sense / has relations to known conjectures and results. –  Phira May 19 '11 at 10:26
Marvin: (+1) I'd vote to reopen, but don't yet have the "threshold rep" to do so. Also @Zev: could you delete, or modify, your comments given the effort Marvin has put into modifying the question, and the sincerity of the question? –  amWhy May 19 '11 at 23:54
@Marvin: I've started a meta thread (meta.math.stackexchange.com/questions/2214/…) for gaining support for reopening the question. –  Qiaochu Yuan May 20 '11 at 6:28
This reminds me of Khinchin's constant en.wikipedia.org/wiki/Khinchin's_constant because it is also the limit value of a function on almost all continued fraction parameters. –  Dan Brumleve May 21 '11 at 5:37
@Dan Brumleve, The input of sqrt(101) into the function of iterated continued fractions from convergents gives 10.0980577066244279660274026688, when you use the Mathematica code, l = Sqrt[101]; Table[c = Convergents[l, 100]; l = FromContinuedFraction[c], {n, 1, 50}]; N[l, Floor[30]] . –  Marvin Ray Burns May 21 '11 at 11:39

Here is some theoretical calculation of the convergent constants, which also agrees with my numerical simulation. However, I get different constants than you! This is probably due to some small misunderstanding, but my method will probably work even using the "correct" formulation.

Edit: Here is the misunderstanding. My formula goes from $[x_0;x_1,x_2,\ldots]$ to $[p_0/q_0;p_1/q_1,p_2/q_2,\ldots]$. Your formula, on the other hand, has an extra step of expressing the latter as a usual integral continued fraction.

This misunderstanding shows that your pages aren't clear enough, please fix that. In more detail, you write $$x_1 = [a_0(1);a_1(1),a_2(1),\ldots] = \left[\frac{p_0(1)}{q_0(1)};\frac{p_1(1)}{q_1(1)},\frac{p_2(1)}{q_2(1)},\ldots\right],$$ but it's not really clear that the middle expression is the regular continued fraction for the value expressed by the continued fraction on the right.

The rest is per the following (erroneous) interpretation. We start with some continued fraction. We compute the partial convergents, and use them as coefficients in a new continued fraction. We then compute the convergents of the latter, and use them as coefficients in another new continued fraction. And so on.

Let the convergents at some given point be $x_0,x_1,\ldots$. In order to calculate the convergents for the next iteration, we use the following formulae: \begin{align*} P_0 &= x_0 & Q_0 &= 1 \\ P_1 &= x_0x_1 + 1 & Q_1 &= x_1 \\ P_n &= x_nP_{n-1}+P_{n-2} & Q_n &= x_nQ_{n-1}+Q_{n-2} \end{align*} We immediately get that the values of $P_0,Q_0$ always stay the same, and so the limiting value $y_0$ of the first convergent is $x_0$.

Next, for the second convergent we have $$x'_1 = P_1/Q_1 = x_0 + 1/x_1.$$ Presumably, if this iteration is repeated, it will eventually reach a fixed point $y_1$ which satisfies $$y_1 = x_0 + 1/y_1.$$ It is easy to solve the quadratic to obtain $$y_1 = \frac{x_0 + \sqrt{x_0^2+4}}{2}.$$ We also obtain limiting values for $P_1,Q_1$, namely $\hat{P}_1 = y_0y_1+1$ and $\hat{Q}_1 = x_1$.

Continuing, for the third convergent we have $x'_2 = P_2/Q_2$. The fixed point $y_2$ satisfies $Q_2 y_2 = P_2$ or $$y_2 (y_2 \hat{Q}_1 + \hat{Q}_0) = y_2 \hat{P}_1 + \hat{P}_0.$$ We again get a quadratic for $y_2$ that we can solve (choosing the positive solution), and then deduce the limiting values $\hat{P}_2,\hat{Q}_2$.

We can continue this way to calculate all the limiting convergents. We naturally have $y_n \rightarrow y_\infty$, and so to derive a numerical approximation of the convergent constant, we can simply pick $n$ big.

So far I have been unable to find a closed formula for the convergent constant, but it's possible that one can come up with such a formula. Note that the constant only depends on $x_0$, which is the floor of the original number.

You can probably get an asymptotic series for the convergent constant this way. It will start $$C(x_0) = x_0 + \frac{1}{x_0} - \frac{3}{x_0^3} + \cdots.$$ We get one more term with each new $y_i$. Probably with some effort one can come up with a recurrence formula for the coefficients.

It's probably possible to prove that if you start with an irrational number, then you always converge to the convergent constant. You just have to prove that each of the convergents converges to the correct $y_n$, and you do that by induction.

The constants I get are different from yours. For example, for $x_0 = 10$ I get the constant $10.0980671369431$.

Here is some sage code that can be used to generate my constants. In order to get the constant of 10, use convergent(10).

def iteration(x, y):
(A0,B0) = x
(A1,B1) = y
a = B1
b = B0 - A1
c = -A0
z = (-b + sqrt(b*b-4*a*c))/(2*a)
A2 = z*A1 + A0
B2 = z*B1 + B0
return (y, (A2,B2))

def convergent(x0, n = 100):
x0 = RR(x0)
A0 = x0
B0 = 1
B1 = (x0 + sqrt(x0*x0+4))/2
A1 = x0*B1 + 1
x = (A0,B0)
y = (A1,B1)
for i in range(n):
x, y = iteration(x, y)
return y

-
Marvin gives this code: l = Sqrt[101]; Table[c = Convergents[l, 100]; l = FromContinuedFraction[c], {n, 1, 50}]; N[l, Floor[30]] which wolframalpha.com won't evaluate. Is it a problem with the precision? –  Dan Brumleve May 31 '11 at 6:41
@Dan: Now I see what the problem is. This code makes it clear what Marvin intended. –  Yuval Filmus May 31 '11 at 7:56
@Yuval Filmus, I've been looking at oeis.org/wiki/Convergents_constant, and I'm somewhat at a loss to see the ambiguity of which you pointed out. Instead of the middle expression being the regular continued fraction for the value expressed by the continued fraction on the right. The writer meant that we make a generalized continued fraction from the convergents of the cf on the left. I would like the page to be clear without people resorting to my code. What changes do you think I can make to clarify things? –  Marvin Ray Burns Jun 2 '11 at 23:24
@Marvin: I would suggest giving an algorithm to generate the sequence, consisting of three steps: (1) express the current number as a (usual) continued fraction, (2) compute the sequence of partial convergents $r_1,r_2,\ldots$, (3) calculate the new number to be $[r_1;r_2,r_3,\ldots]$. I missed step (1). I also suggest removing the huge displays and using the standard notation $[\cdot;\cdot,\cdot,\cdot,\ldots]$ instead. –  Yuval Filmus Jun 3 '11 at 2:44
@Yuval Filmus, I am looking into your suggestions, and am considering putting your 3 steps at the top of the section titled "Iterated continued fractions from convergents." Would you mind rewriting them exactly as you think they should be written if they were put in that place? As for the large cf's, they seem to be rather common in the OEIS Wiki. Perhaps I could re-emphasis them in the standard notation somehow. –  Marvin Ray Burns Jun 4 '11 at 1:25

Here is some analysis for the actual definition.

Suppose that the original continued fraction is $[a;b,c,d,\ldots]$. The first few convergents are $$a \quad a + 1/b \quad a + 1/(b + 1/c) \quad \ldots$$ Therefore, the continued fraction with convergents as coefficients is equal to $$a + 1/(a + 1/b + 1/(a + 1/(b + 1/c) + \cdots)).$$ In general, we would expect that $1/b + 1/(a + \cdots) < 1$; this will happen eventually. In that case, we can recover the second coefficient of the continued fraction as $a$.

Now we're at the case $[a;a,c,d,\ldots]$. Substituting $b = a$ above, the next iteration is equal to $$a + 1/(a + 1/a + 1/(a + 1/(a + 1/c) + \cdots)).$$ Let's express that as an integral continued fraction. After peeling off the first two coefficients, we are left with $$\frac{1}{1/a + 1/(a + 1/(a + 1/c))} \approx \frac{1}{1/a + 1/a} = a/2.$$ Therefore in general, the next coefficient should be $\lfloor a/2 \rfloor$.

Now the analysis splits into two cases, whether $a$ is even or odd. You can get $a_3,a_4$ this way. Since $a_4$ involves division by $6$, we know have $6$ cases. And so on.

In order to prove that the process almost always converges to the constant, one needs to be more careful and show that the estimates above are mostly true. Probably one can get some conditions on the original continued fraction, and deduce from them that convergence happens "for most values", with some precise meaning.

This analysis will also help explain why you get different behavior for small $n$. However, the heuristic estimates I use should give you the value of all coefficients "for large $n$" - how large depends on the actual coefficient.

-
Now that I see from your explanation why $a_1(n)=a_0(n)=n, a_2(n)=floor(n/2)$, how should I argue that the special cases are exempt from the same analysis? For example let n=2.2; then the "convergents constant" of 2.2 = 2.0, where $a_0(2.2)=2$ and $a_1(2.2)$ !=2. –  Marvin Ray Burns Jun 6 '11 at 1:50
@Marvin: My guess is that the analysis works for all irrationals. This should be relatively easy to show (if true). It should also work for some rationals, but that's a bit more delicate. Experimentation may help. –  Yuval Filmus Jun 6 '11 at 2:47
Did you happen to notice that when Mathematica takes the continued fraction of 11/5? It gives both the integer part and the partial quotient for an answer of {2,5}. However, if you ask it to take the cf of 2.2, it gives only the integer part! That is what happens when you start with any one of most special cases in the algorithm for convergents constants, and why you get something else instead of the answer for most x such that 2<x<3. That shows why (or how come) many, if not all, of the special cases are "exempt" from the your analysis –  Marvin Ray Burns Jun 6 '11 at 23:17
@Marvin: I don't actually use Mathematica. If decimals confuse Mathematica, don't use them. Can you find any rational counterexamples? If not, the proof should be much easier. –  Yuval Filmus Jun 7 '11 at 0:45
I quoted you at oeis.org/wiki/Table_of_convergents_constants. If there is anything I need to change, let me know. –  Marvin Ray Burns Jun 8 '11 at 18:03

With a little help from "Phil" at Math2.org, in the thread found at http://math2.org/mmb/thread/43656, I conjectured a partial pattern for a6(n). Daniel Forgues converted it into latex at https://oeis.org/wiki/Table_of_convergents_constants. Thanks for all your help! I still need to work harder on the proof, though.

-