1. How to search the solutions of n=x3+y3+z3

Simple search method

It is generally assumed that 0 ≤ |x| ≤ |y| ≤ |z|.
There are 8 variations of sign x, y, z;

(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

(lexical order of z, y, x). In these cases,

(5) = -(4)
(6) = -(3)
(7) = -(2)
(8) = -(1)

so it is sufficient to search only from (1) to (4),

 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%)
 80        R%=fnSub(-X% , Y% , Z%)
 90        R%=fnSub(X% , -Y% , Z%)
100        R%=fnSub(-X% , -Y% , Z%)
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)

Refined search method for case (4)

Decide the range of y when z is in the fixed range.

-1000 ≤ -x3 - y3 + z3 ≤ 1000
z3 - 1000 ≤ x3 + y3 ≤ z3 + 1000

Lower bound of y is,

x3 + y3 ≤ 2y3

so

z3 - 1000 ≤ 2y3
cbrt((z3-1000)/2) ≤ y

Here cbrt( ) denotes the cube root.
cbrt(a) can be computed by exp and log,

cbrt(a) = exp(log(a)/3)

If a ≤ 0,

cbrt(a) = -exp(log(-a)/3)

changes into integer,

int(cbrt((z3-1000)/2))+1 ≤ y

Upper bound of y is,

x3 + y3 ≥ y3

so

y3 ≤ z3 + 1000
y ≤ cbrt(z3+1000)

changes into integer,

y ≤ int(cbrt(z3+1000))

Therefore

int(cbrt((z3-1000)/2))+1 ≤ y ≤ int(cbrt(z3+1000))

Next, decide the range of x when z and y are fixed.

-1000 ≤ -x3 -y3 + z3 ≤ 1000
z3-y3-1000 ≤ x3 ≤ z3-y3+1000

Here x ≥ 0, so lower bound is

max{0, int(cbrt(z3-y3-1000))+1} ≤ x

Upper bound is

x ≤ int(cbrt(z3-y3+1000))

Therefore

max{0, int(cbrt(z3-y3-1000))+1} ≤ x ≤ int(cbrt(z3-y3+1000))

 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

Solutions of n=x3+y3+z3    (1 ≤ n ≤ 10000, 0 ≤ |x| ≤ |y| ≤ |z| ≤ 106)


D. J. Berstein tried up to 10^10 and beyond for 1 ≤ n ≤ 999.

Solutions for following 14 numbers are still unknown.

33, 42, 74, 114, 165, 390, 579, 627, 633, 732, 795, 906, 921, 975


previous index next

E-mail : kc2h-msm@asahi-net.or.jp
Hisanori Mishima