『直角三角形の面積...』に挑戦

お題：http://d.hatena.ne.jp/route150/20110428/1303994639

直角三角形の斜辺でない２辺をa、bとする。a、bは整数で「1 <= a <= b」とする。面積の小さい順に(a, b)のペアを列挙して下さい。
(追記) 但し、列挙する数は無限個とする(現実的には無理だが)。

最初に一覧にして眺めてみる。

   [1, 1]
   [1, 2]
   [1, 3]
   [1, 4]   [2, 2]
   [1, 5]
   [1, 6]   [2, 3]
   [1, 7]
   [1, 8]   [2, 4]
   [1, 9]            [3, 3]
  [1, 10]   [2, 5]
  [1, 11]
  [1, 12]   [2, 6]   [3, 4]
  [1, 13]
  [1, 14]   [2, 7]
  [1, 15]            [3, 5]
  [1, 16]   [2, 8]            [4, 4]
  [1, 17]
  [1, 18]   [2, 9]   [3, 6]
  [1, 19]
  [1, 20]  [2, 10]            [4, 5]
  [1, 21]            [3, 7]
  [1, 22]  [2, 11]
  [1, 23]
  [1, 24]  [2, 12]   [3, 8]   [4, 6]
  [1, 25]                              [5, 5]
  [1, 26]  [2, 13]
  [1, 27]            [3, 9]
  [1, 28]  [2, 14]            [4, 7]
  [1, 29]
  [1, 30]  [2, 15]  [3, 10]            [5, 6]
  [1, 31]
  [1, 32]  [2, 16]            [4, 8]
  [1, 33]           [3, 11]
  [1, 34]  [2, 17]
  [1, 35]                              [5, 7]
  [1, 36]  [2, 18]  [3, 12]   [4, 9]            [6, 6]
  [1, 37]
  [1, 38]  [2, 19]
  [1, 39]           [3, 13]
  [1, 40]  [2, 20]           [4, 10]   [5, 8]
  [1, 41]
  [1, 42]  [2, 21]  [3, 14]                     [6, 7]
  [1, 43]
  [1, 44]  [2, 22]           [4, 11]
  [1, 45]           [3, 15]            [5, 9]
  [1, 46]  [2, 23]
  [1, 47]
  [1, 48]  [2, 24]  [3, 16]  [4, 12]            [6, 8]

まずは漸化式を立てようとしたのだが間違えて n 行目までの個数を求めていた。
欲しかったのは n 番目が何行目の何列目かということなので没にした。
次に思いついたのは順列のときの階乗進法のように繰り上がりで解く方法。
i 列目の開始は i-1 列目が3回表示した次の行から表示されていることに気づいた。
(n-1)^2 + 2(n-1) + 1 = n^2
しかしそれ以降は、i 行毎に出力するだけで i-1 列目との関係が見つけられない。
とりあえず実装

def iterator() {
  def n = 1   // 行番号
  def i = -1  // 列番号
  def c = [0] // 列
  def nextIndex = {
    i += 1
    while (i >= c.size()) {
      i -= c.size()
      n++
    }
    i
  }
  def iter = [
    hasNext: { true },
    next: {
      while (true) {
        i = nextIndex()
        if (n % (i+1) == 0) break
      }
      def pair = [i+1, c[i]+=1]
      // c の末尾が 3つめなら c を1つ増やす
      if (c.size() == i+1 && c[i] == i+3) c << i+1
      pair
    }
  ] as Iterator
  return iter
}

assert iterator()[100000] == [1,19882]

列はリストなので int の範囲に限定されている。
それに代わるメリットも見出せないが 100000 番目で動作確認。

追記

def rec(row, col) {
  def (b,r) = [row.intdiv(col), row % col]
  if (r == 0)                println([col, b])
  if (row > col * (col + 2)) rec(row, col+1)
  if (col == 1)              rec(row+1, col)
}

rec(1,1)

再帰にしたら止まらないがシンプルになった。
ここから無限リストの形に持っていくにはどうしたらよいのか？

追記その2

solve :: (Integer, Integer) -> [(Integer, Integer)]
solve (row, col) = case row `quotRem` col of
  (b, r) -> if r == 0 then (col, b):rec (row, col)
                      else          rec (row, col)
  where
    rec (row, col)
      | row > col * (col + 2) = solve (row, col+1)
      | otherwise             = solve (row+1, 1)

answer :: [(Integer, Integer)]
answer = solve (1, 1)

main = print $ answer !! 100000

Haskell までもってくることができたが遅い気がする。

追記

追記 その2

追記その2