samskivert: Euler 65

13 January 2011

Problem 065: (source):

object Euler065 extends EulerApp {
  case class Frac (numer :BigInt, denom :BigInt) {
    def + (n :BigInt) = Frac(n * denom + numer, denom)
    def invert = Frac(denom, numer)
  }
  def compute (count :Int, n :Int) :Frac = {
    val term = if (n == 1) 2 else if (n % 3 == 0) 2*(n/3) else 1
    if (n == count) Frac(term, 1)
    else compute(count, n+1).invert + term
  }
  def answer = compute(100, 1).numer.toString map(_-'0') sum
}

The only challenge here is algorithmizing the computation of the continued fraction, while preserving the numerator and denominator, so that we can compute the answer from the final numerator. I think the case class makes the calculations on the fraction much tidier.

©1999–2015 Michael Bayne