The square root of 2 can be written as an infinite continued fraction.

2 = 1 +	1
	2 +	1
		2 +	1
			2 +	1
				2 + ...

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	= 3/2
	2

1 +	1		= 7/5
	2 +	1
		2

1 +	1			= 17/12
	2 +	1
		2 +	1
			2

1 +	1				= 41/29
	2 +	1
		2 +	1
			2 +	1
				2

Hence the sequence of the first ten convergents for 2 are:

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:

The sum of digits in the numerator of the 10^th convergent is 1+4+5+7=17.

Find the sum of digits in the numerator of the 100^th convergent of the continued fraction for e.

+-#Ratio
class Ratio
  include Comparable
  attr_reader :num, :den
  @@facts=[1]
  @@dfacts=[1,1]
  def initialize(a,b=1)
    neg=1
    neg*=-1 if a<0
    neg*=-1 if b<0
    e=Ratio.euc(a.abs,b.abs);
    @num=neg*(a.abs)/e
    @den=(b.abs)/e
  end
  def expand(digits=20)
    a=@num.abs
    b=@den
    str=""
    str="-" if @num<0
    str+=(a/b).to_s+"."
    1.upto(digits) do
      a=10*(a%b)
      str+=(a/b).to_s
    end
    str
  end
  def to_s()
    @num.to_s+"/"+@den.to_s
  end
  def neg?
    @num<0
  end
  def *(o)
    if o.class==Fixnum or o.class==Bignum
      return Ratio.new(@num*o,@den)
    end
    return Ratio.new(@num*o.num,@den*o.den)
  end
  def **(o)
    if o.class==Fixnum
      ret=Ratio.new(1)
      mult=self
      bin=o.to_s(2)
      while(bin.length>0)
        ret*=mult if bin[-1].chr=="1"
        mult*=mult
        bin.chop!
      end
      return ret
    end
  end
  def /(o)
    if o.class==Fixnum or o.class==Bignum
      return Ratio.new(@num,@den*o)
    end
    return Ratio.new(@num*o.den,@den*o.num)
  end
  def +(o)
    if o.class==Fixnum or o.class==Bignum
      return self+Ratio.new(o,1)
    end
    return Ratio.new(@num*o.den+@den*o.num,@den*o.den)
  end
  def -(o)
    return self + (o*(-1))
  end
  def ==(o)
    return (self.den==o.den and self.num==o.num)
  end
  def <=>(b)
    a=self
    return 0 if a==b
    return -1 if(a.neg? and not b.neg?)
    return 1 if(b.neg? and not a.neg?)
    return (b*(-1))<=>(a*(-1)) if(b.neg? and a.neg?)
    c=a-b
    return -1 if c.neg?
    1
  end

  def sqrt(iter)
    guess = self / 2
    iter.times do 
      guess = (guess+(self/guess))/2
    end
    guess
  end

  def Ratio.fromDecimal(str)
  #String should be of type "4783.9233r123"
    neg=Ratio.new(1)
    if(str[0].chr=="-")
      neg*=-1
      str=str[1..-1]
    end
    return neg*Ratio.new(str.to_i,1) if(str=~/^\d+$/)
    if(str=~/^(\d*)\.(\d+)$/)
      whole=$1.to_i
      part=$2
      whole=whole*(10**(part.length))+part.to_i
      return neg*Ratio.new(whole,10**(part.length))
    elsif(str=~/^(\d*)\.(\d*)r(\d+)$/)
      whole=0
      whole=$1.to_i if $1.length>0
      part=0
      part=$2.to_i if $2.length>0
      rep=$3.to_i
      den=1
      if($2.length>0)
        whole=whole*(10**$2.length)+part
        den=10**$2.length
      end
      subtract=whole
      whole=whole*(10**$3.length)+rep
      whole-=subtract
      den*=(10**$3.length)-1
      return neg*Ratio.new(whole,den)
    end
  end

  protected
  def num=(a)
    @num=a
  end
  def den=(b)
    @den=b
  end
  private
  def Ratio.euc(a,b)
    while b!=0
      a,b=b,a%b
    end
    a
  end
end

+-#Enumerable
module Enumerable
  def sum
    self.inject{|u,v|u+v}
  end
  def product
    self.inject{|u,v|u*v}
  end
  def count(ob)
    self.select{|i|i==ob}.length
  end
  def take_while
    return [] unless yield(self.first)
    if(self.class==Range)
      evalPoint=self.first
      evalPoint=evalPoint.succ while yield(evalPoint.succ) and not evalPoint==self.last
      return self.first..evalPoint
    else
      s=self.to_a
      upTo=1
      upTo+=1 while yield(s[upTo]) and upTo<self.length
      return self[0...upTo]
    end
  end
end

+-#dig_split
def dig_split(n)
  s=n.to_s
  s.split("").map{|i|i.to_i}
end

def p65frac_num(i)
  if(i==99)
    return Ratio.new(1)
  end
  if(i>0)
    j=1
    j=(2*(i+1))/3 if(i%3==2)	  
    return Ratio.new(1)/(Ratio.new(j)+p65frac_num(i+1))
  end   
  Ratio.new(2)+p65frac_num(1)
end

def p65
  puts dig_split(p65frac_num(0).num).sum
end