# zbMATH — the first resource for mathematics

On the computation of $$g(k)$$ in Waring’s problem. (English) Zbl 0701.11043
Let $$g(k)$$ be the smallest number $$s$$ such that all natural numbers are the sum of at most $$s$$ $$k$$-th powers. It is conjectured that $$g(k)=2^ k+[(3/2)^ k]-2$$ for $$k\geq 6$$, and this is known for $$k\geq k_ 0$$, for some non-effective $$k_ 0$$. The present paper describes “fast” algorithms for writing down all the numbers $$g(2), g(3),\dots, g(k)$$ (here $$O(k^ 2)$$ operations are needed, best possible), and for writing down an individual $$g(k)$$ (needs $$O(k \log k \log\log k)$$ operations, close to best possible). The authors have also developed an algorithm which is fast, and which in certain cases gives a positive answer to the conjecture on $$g(k)$$, but not a negative one.
Reviewer: J. Brüdern

##### MSC:
 11P05 Waring’s problem and variants 11Y16 Number-theoretic algorithms; complexity 11J25 Diophantine inequalities
##### Keywords:
algorithms; Waring problem
Full Text: