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<Math.sqrt(d); i++){
			while(n%i==0 && d%i==0){
				n/=i;
				d/=i;
			}
		}*/
		BigInteger a = n;
		BigInteger b = d;
		while(true){
			if(a.toString().length() == 1 && a.toString().equals("1")){
				n.divide(b);
				d.divide(b);
				break;
			}else if(b.toString().length() == 1 && b.toString().equals("1")){
				n.divide(a);
				d.divide(a);
				break;
			}
 
			int comp = a.compareTo(b);
			if(comp > 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