## Project Euler – Problem 65

Problem 65:

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

sqrt(2) = 1+1/(2+(1/(2+1/(2+1/…))))

The infinite continued fraction can be written, 2 = [1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, 23 = [4;(1,3,1,8)].

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 2.

1+(1/2) = 3/2
1+(1/(2+1/2)) = 7/5
1+(1/(2+1/(2+1/2)) = 17/12
1+(1/(2+1/(2+1/(2+1/2))) = 41/29

Hence the sequence of the first ten convergents for 2 are:

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, …

What is most surprising is that the important mathematical constant,
e = [2; 1,2,1, 1,4,1, 1,6,1 , … , 1,2k,1, …].

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

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, …
The sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.

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

``` import java.math.BigInteger; public class Fraction { BigInteger n,d; public Fraction(int n, int d){ if(d == 0){ this.n= BigInteger.ZERO;this.d=BigInteger.ZERO; }else{ this.n= new BigInteger(""+n);this.d=new BigInteger(""+d); } } public Fraction(int n, BigInteger d){ this.n= new BigInteger(""+n);this.d=d; } public Fraction(BigInteger n, BigInteger d){ this.n=n; this.d=d; } public Fraction(int n, Fraction f){ this.n=new BigInteger(""+n); this.n = this.n.multiply(f.d); this.d = f.n; } public Fraction addWholeNumber(int i){ return addWholeNumber(new BigInteger(""+i)); } public Fraction addWholeNumber(BigInteger x){ if(d.equals(BigInteger.ZERO)) return new Fraction(x, BigInteger.ONE); return new Fraction(this.n.add(d.multiply(x)), d); } public String toString(){ return n+"/"+d; } } ```

``` class runner { private static int e_series(int i){ if(i==1) return 0; int r = (i-2)%3; if(r == 0 || r == 2) return 1; return 2*(i/3); } public static Fraction e_converge(int max){ if(max == 0) return new Fraction(2,1); return e_converge_aux(1,max).addWholeNumber(2); } public static Fraction e_converge_aux(int count, int max){ Fraction result = new Fraction(1, e_series(count+1)); if(count < max){ result = new Fraction(1, e_converge_aux(count+1, max)); } result = result.addWholeNumber(e_series(count)); return result; } public static void main (String[] args) throws java.lang.Exception { long time = System.currentTimeMillis(); Fraction frac = e_converge(100-1); int sum = 0; for(char y : frac.n.toString().toCharArray()){ sum += y; } sum -= frac.n.toString().length()*48; System.out.println(sum); System.out.println("time: "+(System.currentTimeMillis() - time)); } } ```

Note: I did not consider f(0) = 2, which is why it's simply appended into the code.