## Project Euler Problem #65

### January 29, 2012

Read the details of the problem here

Summary

Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.

Solution

This question immediately reminded me of Problem #57 which ended up being quite a simple solution though it sounded involved initially. I took a look at that, and adopted a similar approach to this one.

The trick with this problem was to spot the pattern as to how the numerator changed down the sequence. As it turned out, the values of the denominator are superflous to this and can just be ignored for this purpose.

Taking the first ten terms as given (with a zeroth term for completeness) given this is how it works:

Term Numerator Multiplier Formula
0 1
1 2 2 2 * num0
2 3 1 1 * num1 + num0
3 8 2 2 * num2 + num1
4 11 1 1 * num3 + num2
5 19 1 1 * num4 + num3
6 87 4 4 * num5 + num4
7 106 1 1 * num6 + num5
8 193 1 1 * num7 + num6
9 1264 6 6 * num8 + num7
10 1457 1 1 * num9 + num8

So this can be summarised as:

numn = muln * numn-1 + numn-2

Where n is the term being calculated and muln is the nth element of the continued fraction.  This is simply n / 3 * 2 when n mod 3 == 0, and 1 otherwise.

Given that the multipliers work in triplets, this can be used to advantage and reduce the number of calculations required. I created a function that given the n-1 and n-2 numerators, and a term number could calculate the next three numerators in the sequence. It meant that I didn’t have to do any modulus calculations as long as I kept the boundary aligned correctly i.e. only call it for terms, 2, 5, 8, etc. which were the start of the triplets.

Starting at term 2, I then called this recursively until it was being asked to calculate the 101st term. At this point the 100th term would be the n-1 numerator value and could be returned.

```def f(p1, p2, tc) {
if (tc == 101) return p1
def m = p1 + p2
def n = ((tc + 1).intdiv(3) * 2) * m + p1
f(n + m, n, tc + 3)
}