プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q19:友達の友達は友達？。

Q: 2つの数の最大公約数が1でない場合、それを友達とする。ある数から他のすべての数にたどり着くには、何段階の友達をたどれば良いか数える。1~Nまでの合成から7個を選んだ時、最大で6段階たどることになる最小のNを求める。

val primes: Stream[Int] = 2 #:: Stream.from(3).filter{n => !primes.takeWhile(_ <= math.sqrt(n)).exists(n % _ == 0)}

primes.take(6).permutations.foldLeft(Int.MaxValue){(z,per) =>
  Seq(z,((per.head * per.head)+:(0 to 4).map{i => per.slice(i,i+2).product}:+(per.last*per.last)).max).min
}

横に長くなってしまった。。