## 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 100^{th} 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 * num_{0} |

2 | 3 | 1 | 1 * num_{1} + num_{0} |

3 | 8 | 2 | 2 * num_{2} + num_{1} |

4 | 11 | 1 | 1 * num_{3} + num_{2} |

5 | 19 | 1 | 1 * num_{4} + num_{3} |

6 | 87 | 4 | 4 * num_{5} + num_{4} |

7 | 106 | 1 | 1 * num_{6} + num_{5} |

8 | 193 | 1 | 1 * num_{7} + num_{6} |

9 | 1264 | 6 | 6 * num_{8} + num_{7} |

10 | 1457 | 1 | 1 * num_{9} + num_{8} |

So this can be summarised as:

num_{n} = mul_{n} * num_{n-1} + num_{n-2}

Where *n* is the term being calculated and mul_{n} is the n^{th} 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 101^{st} term. At this point the 100^{th} 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) } def answer = (f(2G, 1G, 2).toString() as List)*.toInteger().sum()

This runs in around 115 ms, with sum of the digits taking about 10 ms. A port of this code to Java runs in around 1.3 ms in total.

**Conclusion**

Groovy was a nice language to do this in. Not having to mess about with BigInteger objects explicitly is always a boon in the Java world. Performance was quite disappointing though – given that f() is only ever called with BigInteger arguments the compiler should be able to work out exactly what types the variables are and the generated bytecode should be pretty similar to that which javac outputs…but it’s not. In this case Groovy is nearly two orders of magnitude slower and I really don’t see a good reason for it at this stage in the language maturity.