Project Euler: Problem 65

Euler0065.scala

package euler.zerosum

object Euler0065 {

  def main(args: Array[String]) {
    val a = e.take(100)
    val numer = a.init.foldRight(new Rational(a.last, 1))(new Rational(_, 1) + new Rational(1, 1) / _).numer
    println(numer.toString.toList.map(_.toInt - 48).sum)
  }

  private def e: Stream[Int] = 2 #:: eStream(1)

  private def eStream(k: Int): Stream[Int] = {
    if (k % 3 == 2) (k / 3 + 1) * 2 else 1
  } #:: eStream(k + 1)

  class Rational(n: BigInt, d: BigInt) {
    require(d != 0)

    private val g = gcd(n.abs, d.abs)
    val numer = n / g
    val denom = d / g

    def this(n: Int) = this(n, 1)

    def +(that: Rational): Rational = {
      new Rational(
        numer * that.denom + that.numer * denom,
        denom * that.denom)
    }

    def /(that: Rational): Rational = {
      new Rational(numer * that.denom, denom * that.numer)
    }

    private def gcd(a: BigInt, b: BigInt): BigInt = {
      if (b == 0) a else gcd(b, a % b)
    }
  }
}