Non-Recursive Fundamental Recurrence Formulas

Question

Is there a non-recursive version of the fundamental recurrence formulas for continued fractions? I am trying to compute $A_{1000}$, and it is taking me an extremely long time.

By the way, I am expanding $\sqrt2=1+1/(2+\cdots)$.

Answer 1

I'm guessing this is about the 57th problem from Project Euler, and feel that it might be more of a question on programming and creating an optimised algorithm.

You can try to set up better recurrences. Let $d_t$ and $n_t$ denote the $t$-th denominator and numerator respectively. Then you'll find the following recurrence relations. $$ \begin{align*} d_t&=d_{t-1}+n_{t-1} \\ n_t&=2d_{t-1}+n_{t-1} \\ \Rightarrow n_t&=d_t+d_{t-1} \end{align*} $$ You can also find recurrence relations which are exclusive of one another (so the denominator recurrence relation contains no terms dependent upon the numerator and vice versa). $$ \begin{align*} d_t&=2d_{t-1}+d_{t-2} \\ n_t&=2n_{t-1}+n_{t-2} \end{align*} $$ Given that $d_0=n_0=1$, and $d_1=2$, $n_1=3$, the denominators actually form the sequence of Pell numbers, and so there is a closed form for the denominator that I'm familiar with. $$ d_{t}=\frac{(1+\sqrt{2})^{t+1}-(1-\sqrt{2})^{t+1}}{2\sqrt{2}} $$ You can also calculate a closed form for the numerator. $$ n_{t}=\frac{(1+\sqrt{2})^{t+1}+(1-\sqrt{2})^{t+1}}{2} $$