今回の方法では、nの値に依存したアルゴリズムとはなっていない。
n の値に依存する方法としては、mod によるふるいが有効である。
例えば3乗数の mod 7, mod 9 での取り得る値は以下のとおりである。
n | n3 mod 7 |
---|---|
0 | 0 |
1 | 1 |
2 | 1 |
3 | 6 = -1 |
4 | 1 |
5 | 6 = -1 |
6 | 6 = -1 |
n | n3 mod 9 |
---|---|
0 | 0 |
1 | 1 |
2 | 8 = -1 |
3 | 0 |
4 | 1 |
5 | 8 = -1 |
6 | 0 |
7 | 1 |
8 | 8 = -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
について、誰かやってみませんか。
前 | この章の目次 |
---|