ScalaでProject Euler（86）

Problem 55

再び多倍長整数の問題ですね。加算だけなので簡単です。1桁ずつリストに格納すると計算が楽になります。これを勝手にLongIntという型の名前にしています。加算のときに、繰上りを考慮して1桁余分に配列を確保しています。桁が増えなければtailで切り捨てます。

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) :LongInt = {
    val size = n.size.max(m.size) + 1
    val a = new Array[Int](size)
    
    for(k <- 0 to n.size - 1)
        a(k+size-n.size) += n(k)
    for(k <- 0 to m.size - 1)
        a(k+size-m.size) += m(k)
    
    for(k <- size - 1 to 1 by -1) {
        a(k-1) += a(k) / 10
        a(k) %= 10
    }
    
    val b = a.toList
    if(b.head == 0)
        b.tail
    else
        b
}

def next(n :LongInt) :LongInt = add(n, n.reverse)
def is_palindromic(n :LongInt) = n == n.reverse

def is_Lychrel(n :Int) :Boolean =
    Iterator.iterate(digits(n))(next).take(M).drop(1).
                            forall(m => !is_palindromic(m))

val N = 10000
val M = 50
println ((1 to N - 1).count(is_Lychrel))