From the people behind the Alan Turing Cryptography Competition.
You are reading the website of the 2020 edition of the MathsBombe Competition, which ended on Sunday 26 April at 11:59 pm

# Puzzle 3

Continued fractions give an excellent way to approximate numbers by fractions with small denominators.

For example, suppose that we want to approximate the golden mean $$\phi$$ which satisfies $$\phi^2=\phi+1$$. We can manipulate this formula to write $\phi=1+\frac{1}{\phi}$ and then $\phi=1+\dfrac{1}{1+\frac{1}{\phi}}$ and then $\phi=1+\dfrac{1}{1+\frac{1}{1+\frac{1}{\phi}}}$ We might imagine we could repeat this process infinitely many times to write the infinite continued fraction $\phi=1+\dfrac{1}{1+\frac{1}{1+\frac{1}{1\frac{1}{1+\cdots}}}}.$ One way to give meaning to the above infinite continued fraction is to look at the finite approximations. We could write $\frac{p_1}{q_1}=1+\frac{1}{1}=2$ $\frac{p_2}{q_2}=1+\frac{1}{1+\frac{1}{1}}=\frac{3}{2}$ $\frac{p_3}{q_3}=1+\frac{1}{1+\frac{1}{1+\frac{1}{1}}}=\frac{5}{3}$ $\frac{p_4}{q_4}=1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1}}}}=\frac{8}{5}$

and see that the fractions $$\frac{p_n}{q_n}$$ really do converge to $$\phi$$. Suppose now that we want to approximate the number $$\alpha=\frac{1+\sqrt{3}}{2}$$. We write down an infinite continued fraction $\alpha=1+\dfrac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{\cdots}}}}$ where the $$a_i$$ are whole numbers $$\geq 1$$. Let $$r_n$$, $$s_n$$ be whole numbers (with no common factors) satisfying $\frac{r_n}{s_n}=1+\dfrac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{a_4+\ddots+\frac{1}{a_n}}}}}$ What is $$r_{20}$$?