Consider the fraction, n/d, where n and d are positive integers. If nd and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

+-#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 p71
  closest=Ratio.new(1,10)
  (10..1000000).each do |i|
    r=Ratio.new(((3*i)/7.0-1).ceil,i)
    closest=r if r>closest
  end
  puts closest.num
end