Waring's Problem

Fermat stated, and Lagrange proved, that every number can be 
expressed as the sum of four squares, but what about 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, 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.  If you're only interested in exponents less 
than 200000 all you have to remember is  g(n) = 2^n + [(3/2)^n] - 2.

By the way, you may have noticed 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.