Waring's Problem

Fermat stated, and Lagrange proved, that every number can be 
expressed as the sum of four squares, but what about cubes, forth 
powers, etc.?  This is called Waring's Problem, because in 1770 
Waring stated (without proof) that every number is expressible as 
a sum of 4 squares, and as a sum of 9 cubes, and as a sum of 19 
fourth powers, "and so on".  In 1909 Hilbert gave the first proof 
that for each positive integer exponent n there is an integer g(n) 
such that every integer is a sum of at most g(n) non-negative nth 
powers.  A special case is Lagrange's Four Square Theorem (1770), 
which asserts that g(2) = 4.

Around 1912 Wieferich and Kempner proved that g(3) = 9 (as Waring
had asserted), but it wasn't until 1964 than Chen proved g(5)=37. 
In the mean time, several people developed the techniques leading to
the following result for all exponents greater than or equal to 6.
(Square brackets signify that we are to take just the integer part 
of the enclosed quantity.)

   Let 3^n = q 2^n + r with  0 < r < 2^n.  (In other words, 
   q is the quotient of  3^n / 2^n,  and r is the remainder.)

   If  r+q <= 2^n  then  g(n) = 2^n + [(3/2)^n] - 2.

   If  r+q > 2^n  then

               / 2^n + [(3/2)^n] + [(4/3)^n] - 2    if  Q = 2^n
      g(n) =  ( 
               \ 2^n + [(3/2)^n] + [(4/3)^n] - 3    if  Q < 2^n

   where Q = q + (q+1)(4/3)^n.


Actually, the complicated case of r+q > 2^n is somewhat academic, 
because it's been verified that r+q < 2^n for every n < 200000, and 
no value of n for which r+q exceeds 2^n is known.  However, the 
possibility has not been ruled out, so we have to carry along all 
that extra baggage.  But if we're only interested in exponents less 
than 200000 all we have to remember is  g(n) = 2^n + [(3/2)^n] - 2.

By the way, notice that the above results don't cover g(4).  It wasn't 
until 1986 that Balasubramanian, Dress, and Deshouillers finally proved 
Waring's assertion g(4)=19 to be correct.

On a closely related topic, let G(n) denote the smallest number of nth 
powers that can represent all but finitely many exceptions.  For example, 
even though g(3) is 9, there are really only two numbers (23 and 239) that 
cannot be expressed as sums of 8 cubes. It's also known that only finitely
many numbers (of which the largest is probably 454) cannot be expressed 
as sums of 7 cubes, so G(3) is certainly no greater than 7.  It may be as
low as 4, but no one knows for sure.  On the other hand, it's known that 
G(4)=16.