追記：まともなアルゴリズムによる解法

ちょっと悩んだけれど、まともな解法も考えつくことができた。基本的には篩方式のアルゴリズム。

object Prob216 {
  def solve {
    val N = 50000000 //10000
    val nToT: Int => Long = n => 2L * n * n - 1
    val tSeq = Array.tabulate(N + 1)(nToT)

    for {
      n <- 2 to N view;
      t = tSeq(n) if t != 1
      ofs <- Seq(-n, n)
      pos <- t + ofs to N by t
      i = pos.toInt
    } while (tSeq(i) % t == 0) tSeq(i) /= t

    println(2 to N count {n => tSeq(n) == nToT(n)})
  }
}