ScalaでProject Euler（83）

Problem 52

[1, 10/6)に10のべき乗を掛けたものが答えになりえますが、桁数が増えるごとに範囲を絞り込むことができます。例えば6桁でそれぞれ上2桁が10,20,30,40,50,60だとこれで7つ数字があるのでアウトです。11,22,33,44,55,66なら12個数字があるので、12桁以上必要です。上n桁で数字がn個ならそれは一つの解です。
15桁までで7分でした。いちおう1〜7倍も計算してみましたが、15桁までで解はありませんでした。

import scala.testing.Benchmark

def number(a :List[Int]) = a.foldLeft(0)(_ * 10 + _)
def gcd(n :Int, m :Int) :Int = if(m == 0) n else gcd(m, n % m)
def lcm(n :Int, m :Int) = n / gcd(n, m) * m

def digits(n :Long) :List[Int] =
    if(n == 0) Nil else (n % 10).toInt :: digits(n / 10)

def num_digits(n :Long) :Array[Int] = {
    val a = new Array[Int](10)
    for(d <- digits(n))
        a(d) += 1
    a
}

// 70 -> (1, 2, 3, 4, 5, 7) -> 6
def sum_num_digits(n :Long) :Int = {
    val as = List.range(1L, 7).map(m => num_digits(n * m / D))
    List.range(0, 10).map(k => as.map(a => a(k)).reduceLeft(_.max(_))).sum
}

def gen_solutions(b0 :Long, e0 :Long, nd :Int) :Iterator[Long] = {
    val num_digits = sum_num_digits(b0)
    if(num_digits > N)
        Iterator()
    else {
        val b = b0 * 10
        val e = e0 * 10
        val bs = ds.flatMap(d => List.range(b / d * d + d, e, d)).
                                            toSet.toList.sortWith(_ < _)
        (if(num_digits == nd) Iterator(b0 / D) else Iterator()) ++ (
            for((b1, e1) <- (b :: bs).zip(bs ++ List(e0)).toIterator;
                         n <- gen_solutions(b1, e1, nd + 1)) yield n)
    }
}

def solve() = {
    for(n <- gen_solutions(D / 10, D / M, 0))
        println (n)
//  println (gen_solutions(D / 10, D / M, 0).toList)
}

object Test extends Benchmark {
    def run() = solve
}

val N = 15
val M = 7
val D = (1 to M).reduceLeft(lcm)
val ds = List.range(1, M + 1).filter(n => List.range(n + 1, M + 1).
                                        forall(_ % n != 0)).map(D / _)
println (Test.runBenchmark(1))