samskivert: Euler 2⁶

25 August 2010

Problem 064: (source):

object Euler064 extends EulerApp {
  case class Root (root :Int, add :Int, div :Int) {
    def expand = {
      val term = ((math.sqrt(root) + add)/div).toInt
      val nadd = term*div - add
      (term, Root(root, nadd, (root - nadd*nadd)/div))
    }
    override def toString = "(√" + root + "+" + add + ")/" + div
  }
  def expansion (terms :List[Int], roots :List[Root]) :List[Int] = {
    val (term, root) = roots.head.expand
    if (root.div == 0 || roots.contains(root)) term :: terms
    else expansion(term :: terms, root :: roots)
  }
  def answer = 1 to 10000 map(n => expansion(Nil, Root(n, 0, 1)::Nil).length) count(_%2==0)
}

Here we have a nice little case class to represent a single step in the infinite expansion. The process of generating the next expansion could be done purely with simple arithmetic, but I'm lazy, so I just use math.sqrt to obtain the non-fractional part. I don't actually need to keep track of the terms to obtain the solution, but it was handy to have when I was validating the solution, so I kept it around. Same goes for toString. I just love that little root sign!

©1999–2015 Michael Bayne