- All Contests
- ProjectEuler+
- Project Euler #65: Convergents of e

# Project Euler #65: Convergents of e

# Project Euler #65: Convergents of e

_{This problem is a programming version of Problem 65 from projecteuler.net}

The square root of 2 can be written as an infinite continued fraction.

*ad infinitum*. In a similar way, .

It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for .

Hence the sequence of the first ten convergents for are:

What is most surprising is that the important mathematical constant,

The first ten terms in the sequence of convergents for are:

The sum of digits in the numerator of the convergent is .

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

**Input Format**

Input contains an integer

**Constraints**

**Output Format**

Print the answer corresponding to the test case.

**Sample Input**

```
10
```

**Sample Output**

```
17
```