ScalaでProject Euler（99）

Problem 65

連分数の最後に書いた漸化式を使うと簡単です。ただし、64ビットの範囲で解けないので多倍長整数が必要です。

type LongInt = List[Int]

def digits(n: Int) :LongInt = {
    def f(m :Int) :List[Int] =
        if(m == 0) Nil else m % 10 :: f(m / 10)
    f(n).reverse
}

def add(n :LongInt, m :LongInt, c :Int = 0) :LongInt = (n, m, c) match {
    case (Nil, Nil, 0) => Nil
    case (Nil, Nil, c) => c % 10 :: add(Nil, Nil, c / 10)
    case (h1 :: t1, Nil, c) => (h1 + c) % 10 :: add(t1, Nil, (h1 + c) / 10)
    case (Nil, h2 :: t2, c) => (h2 + c) % 10 :: add(Nil, t2, (h2 + c) / 10)
    case (h1 :: t1, h2 :: t2, c) => (h1 + h2 + c) % 10 ::
                                        add(t1, t2, (h1 + h2 + c) / 10)
}

def mul(n :LongInt, m :Int, c :Int = 0) :LongInt = (n, c) match {
    case (Nil, 0) => Nil
    case (Nil, c) => c % 10 :: mul(Nil, m, c / 10)
    case (h :: t, c) => (h * m + c) % 10 :: mul(t, m, (h * m + c) / 10)
}

def coefficients() :Iterator[Int] =
    Iterator(2) ++ Iterator.from(1).flatMap(k => Iterator(1, k * 2, 1))

val N = 100
val ns = coefficients.take(N).toArray
val a = new Array[LongInt](N)
a(0) = List(2)
a(1) = List(3)
for(k <- 2 to N - 1)
    a(k) = add(mul(a(k - 1), ns(k)), a(k - 2))
println (a(N - 1).sum)