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