## Project Euler – Problem 57

Problem 57:
It is possible to show that the square root of two can be expressed as an infinite continued fraction.

`sqrt(2) = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...`

By expanding this for the first four iterations, we get:

```1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...```

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

``` import java.math.BigInteger; public class Fraction { BigInteger n,d; public Fraction(int n, int d){ this.n= new BigInteger(""+n);this.d=new BigInteger(""+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){ return new Fraction(this.n.add(d.multiply(x)), d); } public Fraction addDenominator(Fraction frac){ if(frac.d.toString().length() == 1 && frac.d.toString().equals("1")){ return addWholeNumber(frac.n); }else{ Fraction result = new Fraction(n.add(frac.d), d.add(frac.n)); result.simplify(); return result; } } public void simplify(){ /*for(int i=2; i 0){ a.subtract(b); }else if(comp < 0){ b.subtract(a); }else{ n=new BigInteger("1"); d=new BigInteger("1"); return; } } } public String toString(){ return n+"/"+d; } } ```

``` class runner { public static void main (String[] args) throws java.lang.Exception { long time = System.currentTimeMillis(); int c = 0; Fraction previous = new Fraction(1,2); for(int i=0;i<1000;i++){ Fraction current = new Fraction(1,previous.addWholeNumber(2)); previous = current; current = current.addWholeNumber(1); if(current.n.toString().length() > current.d.toString().length()) c++; //System.out.println(current); } System.out.println("c:"+c); System.out.println("time: "+(System.currentTimeMillis() - time)); } } ```

Note... just noticed addDenominator and simplify methods aren't used.. and thus un-tested methods as well :S