まず x, y, z に関する単純ループで 1≦n≦1000 となるようなものを探してみる。
0 ≦ |x| ≦ |y| ≦ |z| としても、一般性を失わない。
x,y,z の符号の取り得るパターンは以下の8通り。
(1) x, y, z
(2) -x, y, z
(3) x, -y, z
(4) -x, -y, z
(5) x, y, -z
(6) -x, y, -z
(7) x, -y, -z
(8) -x, -y, -z
(z、y、xの順の辞書式に並べている)
このうち、
(5) = -(4)
(6) = -(3)
(7) = -(2)
(8) = -(1)
であるから、(1)〜(4)についてのみ調べればよい。
(1)(2)(3) のとき x3+y3+z3 は常に正となるので、十分大きな x, y, z について x3+y3+z3 は 1000以上となる。
(1) については、x, y, z ≧ 7
(2) については、z ≧ 10
(3) については、x ≧ 10
よって、まず、0 ≦ x, y, z ≦ 10 の範囲で、(1)(2)(3)(4) について x3+y3+z3 ≦ 1000
となるような、x, y, z を求めてみる。
プログラムは以下のとおり。
10 ' cube1.ub 20 M%=1000 : dim T%(M%) : for I%=1 to M% : T%(I%)=0 : next I% 30 ' 40 for Z%=0 to 10 50 for Y%=0 to Z% 60 for X%=0 to Y% 70 R%=fnSub(X% , Y% , Z%) : ' (1) 80 R%=fnSub(-X% , Y% , Z%) : ' (2) 90 R%=fnSub(X% , -Y% , Z%) : ' (3) 100 R%=fnSub(-X% , -Y% , Z%) : ' (4) 110 next X% 120 next Y% 130 next Z% 140 end 150 ' 160 fnSub(X% , Y% , Z%) 170 local N , S% 180 N=X%^3+Y%^3+Z%^3 190 if abs(N)>M% then 220 200 if T%(abs(N))=1 then 220 210 S%=sgn(N) : print S%*N , S%*X% , S%*Y% , S%*Z% : T%(S%*N)=1 220 return(0)
(4) のケースについて、x, y, z ≧ 10 のとき |- x3 - y3 + z3| ≦ 1000
となるような、x, y, z を求める。
まず z の値を固定し、その z の値に対し y が取り得る値の範囲を求める。
-1000 ≦ -x3 - y3 + z3 ≦ 1000
z3 - 1000 ≦ x3 + y3 ≦ z3 + 1000
y の下限を定める。
x3 + y3 ≦ 2y3
だから、
z3 - 1000 ≦ 2y3
cbrt((z3-1000)/2) ≦ y
ここで cbrt( ) は3乗根を表す。
cbrt(a) は exp と log の組み合わせで、以下の式によって求めることができる。
cbrt(a) = exp(log(a)/3)
a ≦ 0 のときは、
cbrt(a) = -exp(log(-a)/3)
とする。整数化すると、
int(cbrt((z3-1000)/2))+1 ≦ y
次に y の上限を定める。
x3 + y3 ≧ y3
だから、
y3 ≦ z3 + 1000
y ≦ cbrt(z3+1000)
整数化すると、
y ≦ int(cbrt(z3+1000))
以上まとめると、
int(cbrt((z3-1000)/2))+1 ≦ y ≦ int(cbrt(z3+1000))
次に z , y の値が定められたときの x の値の取り得る範囲を求める。
-1000 ≦ -x3 -y3 + z3 ≦ 1000
z3-y3-1000 ≦ x3 ≦ z3-y3+1000
x ≧ 0 なので、下限は
max{0, int(cbrt(z3-y3-1000))+1} ≦ x
上限は、
x ≦ int(cbrt(z3-y3+1000))
まとめると、
max{0, int(cbrt(z3-y3-1000))+1} ≦ x ≦ int(cbrt(z3-y3+1000))
(4) のケースについて 10 ≦ z ≦ 100000 のとき |- x3 - y3 + z3| ≦ 1000 となるような x, y, z を求める。
プログラムは以下のとおり。
10 ' cube2.ub 20 M%=1000:dim T%(M%):for I%=1 to M%:T%(I%)=0:next I% 30 ' 40 for Z=10 to 100000:Z3=Z^3 50 if Z3<=M% then Ys=0 else Ys=int(exp(log((Z3-M%)/2)/3))+1 60 Ye=int(exp(log(Z3+M%)/3)) 70 for Y=Ys to Ye:W=Z3-Y^3 80 if W<=M% then Xs=0 else Xs=int(exp(log(W-M%)/3))+1 90 Xe=int(exp(log(W+M%)/3)) 100 for X=Xs to Xe:N=W-X^3:if abs(N)>M% then 130 110 if T%(abs(N))>0 then 130 120 S=sgn(N):print abs(N);":";-X*S;",";-Y*S;",";Z*S:inc T%(abs(N)) 130 next X 140 next Y 150 next Z
実行結果は次頁のとおり。
前 | この章の目次 | 次 |
---|