Positive Integer Solution of x^3+y^3+z^3=n (n \in [1..5000])

[2022.01.07]x^3+y^3+z^3=n (n \in [1..5000])の正整数解

• x^3+y^3+z^3=nの小さい整数解(0<=|x|<=|y|<|z|<=1832031)または正整数解(0<=x<=y<=z)を計算するプログラム "a30.c" (C)
• x^3+y^3+z^3=nの整数解(0<=|x|<=|y|<|z|,y*z<0)を計算するプログラム "aa31.c" (C)
• x^3+y^3+z^3=nの整数解(0<=|x|<=|y|<|z|,x*y>0)を計算するプログラム "aa32.c" (C)

• 基本的に、0 <= |x| <= |y| <= |z| となるprimitiveな解を求めるが、ついでにnon-primitiveな解を求める。
  
• 負整数を扱うので、解を求めるプログラムを３つに分解して、それぞれを専用化する。
  "a30.c": 0 <= x <= y <= z となる正整数解(x,y,z)を求める。
  "a31.c": 0 <= |x| <= |y| < |z|, y*z < 0, 0 <|z|-|y| <= aとなる整数解(x,y,z)を求める。
  "a32.c": 0 <= |x| <= |y| < |z|, x*y >= 0となる整数解(x,y,z)を求める。
  
• 整数計算では、基本的に64bit符号付き整数(long long int)[型名をLINTとする]/符号無し整数(long long unsigned int)[型名をUINTとする]を使う。
  
• 3乗根の計算には、x64の80-bit浮動小数点数(long double)または64bit浮動小数点数(double)を使う[typedefの型名をDOUBLEとする]。
  
• |z|が12桁以内の範囲では、cbrt(),floor(),fabs()関数はdoubleによる計算で十分であり、long doubleによる計算よりも約2倍速いことが分かったので、doubleを採用した。ただし、|z|が13桁以上になると、cbrt()の精度が不足するので、long doubleが必要になる。
  
• 整数が３乗数になるかどうか調べるために、mod 63の３乗剰余の表p3mod63[64]を使う。
  
• |x^3+y^3+z^3|は十分小さい(< 2^63)が、途中の計算で64bitを超える場合を(mod 2^64)または(mod 2^21-q)[q=9,19,21,55,61]による計算で、正確に求める。[中国人剰余定理により、保証される。]
  

-bash-3.1$ time ./a30 -n 1730
1:1^3+1^3+12^3=1730
2:1^3+9^3+10^3=1730
2 solutions.

real    0m0.010s
user    0m0.000s
sys     0m0.010s
-bash-3.1$ time ./a30 -n 143604279
1:0^3+359^3+460^3=143604279
1 solutions.

real    0m0.017s
user    0m0.009s
sys     0m0.009s
-bash-3.1$ time ./a30 -n 143604280
1:1^3+111^3+522^3=143604280
2:1^3+359^3+460^3=143604280
3:1^3+408^3+423^3=143604280
4:323^3+328^3+421^3=143604280
4 solutions.

real    0m0.012s
user    0m0.012s
sys     0m0.000s
-bash-3.1$ time ./a30 -n 18446744073709250272
1:467^3+27094^3+2642245^3=18446744073709250272
2:1600255^3+1751201^3+2078416^3=18446744073709250272
2 solutions.

real    902m26.119s
user    902m24.138s
sys     0m0.030s

-bash-3.1$ time ./aa30 143604279 -d
1:0^3+111^3+522^3=143604279 (3)
2:0^3+359^3+460^3=143604279
3:0^3+408^3+423^3=143604279 (3)
1 primitive solutions.
3 solutions.

real    0m0.010s
user    0m0.000s
sys     0m0.010s

-bash-3.1$ time ./aa31 2022 10 1000000 100000
using (mod 2^64).
1:-13^3-37^3+38^3=2022
2:-355^3-415^3+488^3=2022
2 solutions.

real    26m38.557s
user    26m38.528s
sys     0m0.000s

-bash-3.1$ time ./aa32 2022 1 10000000
using (mod 2^64).
1:-13^3-37^3+38^3=2022
2:-331^3-472^3+521^3=2022
3:-355^3-415^3+488^3=2022
4:-5629^3-243829^3+243830^3=2022
5:-26149^3-41773^3+44942^3=2022
6:-75142^3-1421359^3+1421429^3=2022
7:-134827^3-910231^3+911216^3=2022

-bash-3.1$ time ./aa31 7 50431896357881 50431896357881 4428653338 1000
using (mod 2^64).
1:-3232871681403^3-50427467704543^3+50431896357881^3=7
1 solutions.

real    2m10.656s
user    2m10.656s
sys     0m0.000s
-bash-3.1$ time ./aa31 30 2220422932 2220422932 1534415
using (mod 2^64).
1:-283059965^3-2218888517^3+2220422932^3=30
1 solutions.

real    0m0.028s
user    0m0.019s
sys     0m0.010s
-bash-3.1$ time ./aa32 30 2220422932 2220422932
using (mod 2^64).
1:-283059965^3-2218888517^3+2220422932^3=30
1 solutions.

real    4m31.014s
user    4m31.013s
sys     0m0.000s
-bash-3.1$ time ./aa31 30 3982933876681 3982933876681 5428322135
using (mod 2^64).
1:-636600549515^3-3977505554546^3+3982933876681^3=30
1 solutions.

real    1m45.621s
user    1m45.621s
sys     0m0.000s

[参考文献]

• [1]Richard K. Guy, "Unsolved Problems in Number Theory Third Edtion", Springer-Verlag, 2004, D11, p252-262, ISBN0-387-2060-7.
  
• [2]Josh Liu Centrinia, "threecubes.txt", 2019/09/21.
  
• [3]三島 久典, "数学者の密室　４章 n=x^3+y^3+z^3 (D5 Sum of four cubes)", 2007/12/10.
  
• [4]D.J.Bernstein, "threecubes", 1.8*10^14までの一覧表(2001/07/29).
  

[Homeに戻る] [一覧に戻る]