Sum of kth powers

Sums of kth powers
------------------

The Waring problem: all positive integers are a sum of at most g(k) kth powers of positive integers
where g(k) is the minimum such quantity

g(k) = 1, 4, 9, 19, 37, 73, 143, 279, 548, 1079, 2132, 4223, 8384, 16673, 33203, 66190, 132055, 263619, 526502, 1051899

It is conjectured that g(k) = 2^k + floor((3/2)^k) - 2

k=1: every integer is a sum of 1x singlets:
  N = a^1
  eg, 1 = 1

k=2: every integer is a sum of 4x squares:
  N = a^2 + b^2 + c^2 + d^2
  eg, 7 = 4 + 1 + 1 + 1

k=3: every integer is a sum of 9x cubes:
  N = a^3 + b^3 + c^3 + d^3 + e^3 + f^3 + g^3 + h^3 + i^3
  eg, 23 = 8 + 8 + 1 + 1 + 1 + 1 + 1 + 1 + 1

k=4: every integer is a sum of 19x hypercubes:
  N = a^4 + b^4 + ... + s^4
  eg, 79 = 16 + 16 + 16 + 16 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

-------------------------------------------------------------------------------

Imagine (a) such that a^k < N < (a+1)^k

N is too small for (a+1)^k to be a term in the summation, so N must be
represented by several copies of a^k, and a remainder made up of smaller
terms. At an extreme, we can imagine those smaller terms would all be 1s.

  N = x copies of a^k + [remainder]

Because of the adversarial nature of this game, we have to maximise x, to
force use of a maximal number of "large" terms in the summation.

2^k is the smallest term we can add other than 1, so to prevent 2^k contributing
to this remainder, the remainder must be 1 less than 2^k. This maximises the
number of 1s, while preventing larger terms appearing.

  a^k < N < (a+1)^k
  N = x copies of a^k + (2^k - 1) copies of 1.

What is the value of a? Combining these expressions:

  x.a^k + 2^k - 1 < (a+1)^k

  x < (1 + 1/a)^k + (1 - 2^k)/a^k

To maximise x, we clearly must make (a) as small as possible. It cannot
be 1, because of the above arguments, so a = 2 it is.

Which means that:

  x < (3/2)^k  + 1/2^k - 1  =  (3^k + 1)/ 2^k - 1  < (3/2)^k - 1  =>  x = floor[(3/2)^k] - 1

Therefore,

  g(k) = x + (2^k - 1) = floor[(3/2)^k] + 2^k - 2

And,

  N = (floor[(3/2)^k] - 1) copies of 2^k, plus (2^k - 1) copies of 1.

  N = 2^k * (floor[(3/2)^k] - 1) + 2^k - 1

  N = 2^k * floor[(3/2)^k] - 1

Examples:

  N(1) = 2^1 * floor(3/2) - 1    =  2*1 - 1 =   1

            1 = 1^1

  N(2) = 2^2 * floor(9/4) - 1    =  4*2 - 1 =   7

            7 = 2^2 + 1^2 + 1^2 + 1^2

  N(3) = 2^3 * floor(27/8) - 1   =  8*3 - 1 =  23

            23 = 2^3 + 2^3 + 1^3 + ... + 1^3

  N(4) = 2^4 * floor(81/16) - 1  = 16*5 - 1 =  79
  N(5) = 2^5 * floor(243/32) - 1 = 32*7 - 1 = 223
  etc