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.