ScalaでProject Euler（17）

Problem 9

この問題は、ピタゴラス数生成式を使えば速く答えを得ることができます。これを使うと、

a + b + c = 2lm(m + n)

となるので、500を素因数分解して約数を生成して、その一方の約数の約数を生成して条件にあてはまるか見ればよいです。

type

素因数分解された形は素数と指数のペアのリストと考えると、List[(Int,Int)]という型になりますが、長いので別名をつけましょう。別名はtypeでつけられます。

type Facts = List[(Int,Int)]

groupBy

Pythonのgroupbyは素因数分解にうってつけの関数です。

from itertools import groupby

for p, it in groupby([ 2, 2, 2, 2, 3 ]):
    print p, len(list(it))

2 4
3 1

ScalaのgroupByも似ていますが、iteratorの代わりにMapを返すところが違います。ただ、これも大きさを取ればよいだけです。

val a = List(2, 2, 2, 3, 3)
println (a.groupBy((x) => x).toList.map((x) =>(x._1, x._2.length)))

あとは、地道にコードを書いていけば答えは求まるでしょう。

def pow(n :Int, e :Int) :Int =
    if(e == 0) 1 else n * pow(n, e - 1)

def gcd(m :Int, n :Int) :Int = if(n == 0) m else gcd(n, m % n)

type Facts = List[(Int,Int)]

def factorize(n :Int) = {
    def f(n :Int, p :Int) :List[Int] = n match {
        case 1 => Nil
        case _ if p * p > n => List(n)
        case _ if n % p == 0 => p :: f(n / p, p)
        case _ => f(n, p + 1)
    }
    
    f(n, 2).groupBy((x) => x).toList.map((x) =>(x._1, x._2.length))
}

def sub_f(f1 :Facts, f2 :Facts) :Facts = (f1, f2) match {
    case (f1, Nil) => f1
    case ((p, e1) :: g1, (q, e2) :: g2) if p == q
                    => (p, e1 - e2) :: sub_f(g1, g2)
    case (h :: g1, f2) => h :: sub_f(g1, f2)
    case _ => Nil
}

def value_f(f :Facts) =
    f.foldLeft(1)((x, y) => x * pow(y._1, y._2))

def divs(f :Facts) :IndexedSeq[Facts] = f match {
    case Nil => for(m <- 0 to 0) yield Nil
    case (p, e) :: g => for(e1 <- 0 to e; d1 <- divs(g))
                                        yield (p, e1) :: d1
}

def solve(f :Facts) =
    for(f1 <- divs(f); val f2 = sub_f(f, f1); f3 <- divs(f2);
            val f4 = sub_f(f2, f3);
            val l = value_f(f1);
            val m = value_f(f3);
            val n = value_f(f4) - m;
            if (m + n) % 2 == 1 && gcd(m, n) == 1;
            if 0 < n && n < m;
            val a = l * (m * m - n * n);
            val b = 2 * l * m * n;
            val c = l * (m * m + n * n))
        yield a * b * c

val N = 1000
val f = factorize(N / 2)
println (solve(f))