まず、1000未満の17の倍数を生成します。例えば、289ですね。その上2桁を取って、28。その上の桁に数字をつけた数が13の倍数になっている必要があります。
13n = 100d + 28
このディオファントス方程式を0 ≤ d < 10の範囲で解いて、d = 7。これを数字のダブりをチェックしながら繰り返します。
def gcd(n :Int, m :Int) :Int = if(m == 0) n else gcd(m, n % m) def digits(n :Int) :Iterator[Int] = if(n == 0) Iterator() else Iterator(n % 10) ++ digits(n / 10) def number(ds :List[Int]) = ds.foldLeft(0L)((x, y) => x * 10 + y) // ax + by = c def solve_linear_equation(a :Int, b :Int, c :Int) :Option[(Int,Int)] = if(b == 0) if(c % a == 0) Some((c / a, 0)) else None else { val (a1, b1) = (b, a % b) solve_linear_equation(a1, b1, c) match { case None => None case Some((x, y)) => if(b1 == 0) Some((0, c / a1)) else Some((y, x - a / b * y)) } } def add_flag(flag :Option[Int], n :Int) :Option[Int] = flag match { case None => None case Some(f) => { if((f & (1 << n)) != 0) None else Some(f | (1 << n)) } } def residual_flag(flag :Int) :Int = if((flag & 1) == 0) 0 else 1 + residual_flag(flag >> 1) def gen_digits(p :Int, ds :List[Int]) :Iterator[Int] = ds match { case d1 :: d2 :: Nil => { val c = d1 * 10 + d2 solve_linear_equation(p, 100, c) match { case None => Iterator() case Some((x0, y0)) => { val r = (-y0) % p val d0 = if(r >= 0) r else p + r val diff = p / gcd(p, 100) Iterator.range(d0, 10, diff) } } } case _ => Iterator() } def digits2(n :Int, rep :Int) :List[Int] = if(rep == 0) Nil else digits2(n / 10, rep - 1) ++ List(n % 10) def gen_number(ps :List[Int], ds :List[Int], flag :Option[Int]) :Iterator[List[Int]] = (ps, ds, flag) match { case (_, _, None) => Iterator() case (Nil, _, Some(f)) => { val d = residual_flag(f) if(d > 0) Iterator(List(d)) else Iterator() } case (p :: pst, Nil, Some(f)) => for(n <- Iterator.range(p, 1000, p); ds2 = digits2(n, 3); ds3 <- gen_number(pst, ds2.slice(0, 2), ds2.foldLeft(flag)((x, y) => add_flag(x, y)))) yield ds3 ++ ds2 case (p :: pst, _, _) => for(d <- gen_digits(p, ds); ds2 <- gen_number(pst, List(d, ds.head), add_flag(flag, d))) yield ds2 ++ List(d) } val ps = List(17, 13, 11, 7, 5, 3, 2) println (gen_number(ps, Nil, Some(0)).map(number).sum)
