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

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?

+-#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

def p57
  x=one=Ratio.new(1)
  c=0
  1000.times do
    x=one+one/(one+x)
    c+=1 if x.num.to_s.length>x.den.to_s.length
  end
  puts c
end