ScalaでProject Euler（84）

Problem 53

パスカルの三角形の下から計算します。まず、n = 100のときの最小のrを求めます。次にn = 99のときの最小のrを先ほどのrから始めて求めます。rが求まらなくなったらおしまいです。

def rmin(n :Int, r0 :Int, c0 :Int) :Option[(Int,Int)] = {
    def next(s :(Int,Int)) = {
        val (c, r) = s
        (c * (n - r) / (r + 1), r + 1)
    }
    val it = Iterator.iterate((c0, r0))(next).
                takeWhile(_._2 * 2 <= n).filter(x => x._1 > N)
    if(it.hasNext)
        Some(it.next)
    else
        None
}

def rmins(n :Int, prev_rmin :Int, prev_c :Int) :Iterator[Int] = {
    val c0 = prev_c * (n - prev_rmin + 1) / (n + 1)
    rmin(n, prev_rmin, c0) match {
        case Some((c, r)) => Iterator(r) ++ rmins(n - 1, r, c)
        case None => Iterator()
    }
}

val N = 1e6.toInt
val M = 100
println (rmins(M, 0, 1).zip(Iterator.from(M, -1)).
                        map(x => x._2 - x._1 * 2 + 1).sum)