Project Euler: Problem 23

Euler0023.scala

package euler.zerosum

object Euler0023 {

  def main(args: Array[String]) {
    val limit = 28123
    val numbers = from(1).take(limit)
    val abundant = getAbundant(limit)

    println(numbers.filterNot(x => isSumOfTwoElems(x, abundant.takeWhile(_ <= x))).sum)
  }

  /**
   * seqの任意の2要素e1, e2（e1=e2 を許す）を取り出した時、
   * e1 + e2 = n を満たすかどうかを判定する。
   *
   * @param n
   * @param seq
   * @return n == seq.e1 + seq.e2 => true
   */
  private def isSumOfTwoElems(n: Int, seq: Stream[Int]): Boolean = {
    seq.find(x => seq.contains(n-x)).nonEmpty
  }

  /**
   * n以下の過剰数を返す。
   *
   * @param n
   * @return
   */
  private def getAbundant(n: Int): Stream[Int] = {
    from(0).take(n).map(getDivisors(_)).zipWithIndex.tail.filter(x => x._1.sum > x._2).unzip._2
  }

  /**
   * 自身を除いたnの約数を返す。
   * 約数は昇順にソートされる。
   *
   * @param n
   * @return
   */
  private def getDivisors(n: Int): Stream[Int] = {
    val divs = from(1).take(math.sqrt(n).toInt).filter(n%_ == 0)
    (divs ++ divs.map(n/_).filterNot(x => x == n || x == divs.last)).sortWith(_<_)
  }

  /**
   * n以上の整数の無限数列を生成する
   *
   * @param n
   * @return
   */
  private def from(n: Int):Stream[Int] = n #:: from(n + 1)
}