直方体の3辺の長さをp, q, r(p < q < r)としてp + qとrが直角を成す三角形の斜辺が整数になる場合を求めるのでしたが、逆にピタゴラス数(a, b, c)(a < b < c)が先に与えられた場合を考えます。
例えば、(3, 4, 5)というピタゴラス数を考えます。斜辺は関係ないので(3, 4)ですね。どちらかの辺を分割してpとqにします。
3の分割は3 = 1 + 2のみです。一般に、b ≤ Mのとき[ a / 2 ]通りの分割があります。
4の分割は4 = 2 + 2 = 1 + 3の2通りです。一般にa ≤ Mのときa - [ (b - 1) / 2 ]通りの分割があります(b / 2 ≤ aの必要があります)。
ピタゴラス数の生成はいつもの方法を使います。l = 1としたとき、
m2 - n2 ≤ 2M
2mn ≤ 2M
が必要条件になります(本当はもっと厳しい条件がありますが手抜きします。たぶん速度はあまり変わりません))。これをmの式にすると、
m2 < (1 + √2)M
さらにnの式にすると、
√(m2 - 2M) ≤ n ≤ M / m (m2 ≥ 2M)
この関係を用いてmとnを生成し、aとbを生成して直方体の個数を数えます。106で8ms、1013で46秒でした。