Find n-th convergent of continued fraction

Question

Let d = 7. √7 has a periodic continued fraction of the form: [2, (1, 1, 1, 4)]. So r= 4 (r is the period). Notice that r is even.

After a lot of research I found out that:

If period is even, then x₁ = h_nr-1 and y₁ = k_nr-1 , n = 1,3,5,7 ... where h_n/k_n are the convergents of the expansion of √7 and x₁, y₁ the minimal solution of Pell's equation, x² - 7y² = 1.

If period is odd, then x₁ = h_nr-1 and y₁ = k_nr-1 , n = 2,4,6,8 ...

Eg. For d = 7, period is even (=4) so x₁ = h_1*4-1 = h₃ and y₁ = k_1*4-1 = k₃. That means the solution (x1, y1) can be obtained by the 3^rd convergent of √7.

x₁ can be found very easily from a mathematical aspect.

1^st convergent: 2 + 1 / 1 = (2 * 1 + 1) / 1 = 3/1. So h₁ = 3 and k₁ = 1.

2^nd convergent: 2 + 1 / (1 + 1 / 1) = 2 + 1 / (1 + 1) = 2 + 1 / 2 = (2 * 2 + 1) / 2 = 5/2 . So h₂ = 5 and k₂ = 2.

3^rd convergent: With the same way we prove that h₃ = 8 and k₃ = 3.

So x₁ = h₃ = 8 and y1 = k₃ = 3.

The mathematical way is pretty straight-forward.

I am really stuck trying to implement an algorithm which calculates h_n and k_n.

• How can I implement the calculation of the n-th convergent when the sequence [2, (1, 1, 1, 4)] is known ?

Answer 1

I found solution to my problem from this paper: https://www.math.ru.nl/~bosma/Students/CF.pdf

You can calculate any convergent from this formula: p_n/q_n = (a_n * p_n-1 + p_n-2) / (a_n * q_n-1 + q_n-2)

Answer 2

The simple continued fraction convergents basically can be calculated like a 2x2 matrix product of the coefficients in the following form. \begin{align} \begin{bmatrix} c_0 & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_1 & 1\\ 1 & 0 \end{bmatrix} \cdot ... \cdot \begin{bmatrix} c_{n-1} & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} c_n & 1\\ 1 & 0 \end{bmatrix} = \begin{bmatrix} p_n & p_{n-1}\\ q_n & q_{n-1} \end{bmatrix} \end{align}