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.