原です。

In [ruby-math:00876]

>近岡です。
>
>スピード部門、シンプル部門の他に、
>「姑息な手段」部門の新設につながるようなアイデアを思いつきました。

た、確かに。探索すべき数 N に対する探索時間のオーダーに変化は
ないでしょうが、N が固定ならこんなふうに組織的にパワーアップ
する方法は有効ですね。

>例えば、 
> X**2-X*Y+Y**2 ≡ 0 (mod 5) ならば X ≡ Y ≡ 0 (mod 5) 
>ですから、A+B が5の倍数の場合には、刻み幅も5倍にできます。

それは正しいですけど、プログラムで使っているのは

  p:素数, p-1 は 3で割れない, x**3 + y**3 ≡ 0 (mod p)
      ==> x + y ≡ 0 (mod p)

という事実ですね。これの証明は f(x) = x**3 が、Z/pZ の乗法群
Z/(p-1)Z における同型を引き起こす事から分かるわけですね。


>d16=[4,2,8,2, 16,2,8,2, 2,2,8,2, 16,2,8,2]
>d27=[3,3,9, 1,1,1, 1,9,3,  9,3,9, 1,1,1, 1,9,3,  9,3,9, 1,1,1, 1,9,3]
># 例えば、
>#    a**3+b**3≡4(mod 16)のとき、c+d≡a+b(mod 16)
># 一般に、
>#    a**3+b**3≡k(mod 16)のとき、c+d≡a+b(mod d16[k])
>#    a**3+b**3≡k(mod 27)のとき、c+d≡a+b(mod d27[k])

うーむ、実験すれば正しいみたいですけど、どうやって思いつい
たのかなあ。