5.まとめ


今回の方法では、nの値に依存したアルゴリズムとはなっていない。
n の値に依存する方法としては、mod によるふるいが有効である。
例えば3乗数の mod 7, mod 9 での取り得る値は以下のとおりである。

nn3 mod 7
00
11
21
36 = -1
41
56 = -1
66 = -1
nn3 mod 9
00
11
28 = -1
30
41
58 = -1
60
71
88 = -1

すなわち、mod 7, mod 9 のとき n3 の取り得る値は -1, 0, 1 のみである。
従って、例えば n = 3 mod 7 , n = 3 mod 9 のとき、
-1, 0, 1 の和で 3 となるのは、3 = 1 + 1 + 1 の場合だけなので、

mod 7 :

x, y, z : 1, 2, 4 mod 7 のみ
          0, 3, 5, 6 mod 7 の場合は解がない。
mod 9 :

x, y, z : 1, 4, 7 mod 9 のみ
          0, 2, 3, 5, 6, 8 mod 9 の場合は解がない。

となり、半分以上をふるい落とすことができる。

もちろん gcd(x, y, z)>1 の場合も探査対象から外してよい。
ただし、ループの中で gcd を計算すると時間がかかるので、 ループ構造自体に組み込むよう、何か工夫が必要。


探査について、しらみつぶしではなく個別の値についてやる方法はある。
f(x,y,z) = x3 + y3 + z3 について解を眺めてみると、 z - y が小さい値をとっていることが多いので、
y = z-d, d=1, 2, ... とし z3+(z-d)3 を求める。
x の取り得る値の範囲について -1000 ≦ x3 + z3 + (z-d)3 ≦ 1000 とすると、ループ構造が丸々1個減る。
もちろん d の値を d ≦ z までやると、単純な3重ループと同じになってしまうが、
d の値が小さくても解が見つかる可能性が高いので、 z の探査範囲は 10 倍ぐらい大きくとっても構わない。
(ただし、g(x,y,z)=x3+y3+2z3 の場合はうまくいかない)


今回の |z| ≦ 100000 までの探査は、Pentium MMX 233MHz のマシンで行い、
正負が未定の各ケースについて、約3日ほどかかった。
Pentium III の速いマシンを使うと 24hr 程度で実行できると思われる。
従って、|z| ≦ 1000000 は、パソコンで充分探査の射程内にある。
更に、|z| ≦ 10000000 までの探査も、数ヶ月かければ充分実行可能である。
(半年もかからないと思われる)

n ≦ 10000
0 ≦ |x| ≦ |y| ≦ |z| ≦ 10000000

について、誰かやってみませんか。


この章の目次  

E-mail : kc2h-msm@asahi-net.or.jp
三島 久典