ScalaでProject Euler（88）

Scala

Problem 57

これも多倍長整数を使うだけですね。

x + 1 = 2 + 1 / (x + 1)
x2 + 2x + 1 = 2x + 2 + 1
x2 = 2

で連分数が√2となることがわかります。
連分数の漸化式は計算で求まりますが、見ればわかりますよね。

type LongInt = List[Int]

def add(m :LongInt, n :LongInt) :LongInt = {
    val size = m.size.max(n.size) + 1
    val a = new Array[Int](size)
    for((k, e) <- Iterator.from(size - m.size).zip(m.toIterator))
        a(k) += e
    for((k, e) <- Iterator.from(size - n.size).zip(n.toIterator))
        a(k) += e
    for(k <- size - 1 to 1 by -1)
        if(a(k) >= 10) {
            a(k) -= 10
            a(k-1) += 1
        }
    if(a(0) > 0)
        a.toList
    else
        a.toList.tail
}

def next(s :(LongInt,LongInt)) = {
    val (x, y) = s
    val p = add(x, y)
    val q = add(p, y)
    (q, p)
}

def diff(f :(LongInt,LongInt)) =
    f._1.size != f._2.size

val N = 1000
val init = (List(3), List(2))
println (Iterator.iterate(init)(next).take(N).count(diff))