Problem with Queens and Pawns

[John Conway]

On Thu, 1 Jun 2000, Erich Friedman quoted and wrote:

> >n |  1 2 3 4 5 6  7  8  9 10 11 12 13 14 15 .....
> >__|______________________________________________
> ># |  0 0 0 2 4 7 10 14 19 24 30 36 44 51 60 .....
> >Formula ??
> 
> look at only the even index terms, and compute second differences...
    [they are alternately  2  and  3, if we redefine  f(1) = -1]
> the same thing happens when we do only the odd index terms...

   In such circumstances there's often a single formula of the type
"nearest-integer-to-a-polynomial" that does all cases.  Let me first
find the formulae for the separate residue classes modulo 4:

   1   5   9  13   2   6  10  14   3   7  11  15   4   8  12
  --------------- --------------- --------------- -----------
  -1   4  19  44   0   7  24  51   0  10  30  60   2  14  36
     5  15  25       7  17  27      10  20  30      12  22
      10  10          10  10          10  10          10

  Since the second differences of  x^2  are  2  this means that
the leading term of  f(4x+k)  is  5x^2,  so the leading term of
f(x) will be  5x^2/16.  So I'll compute  5x^2 - 16f(x):

   1   5   9  13   2   6  10  14   3   7  11  15   4   8  12
  --------------- --------------- --------------- -----------
  21  61 101 141  20  68 116 164  45  85 125 165  48  96 144
    40  40  40      48  48  48      40  40  40      48  48

This tells us that the x-term in this difference is  10x
or  12x  according as  x  is  odd or even, giving the new
approximations  (5x^2 - 10x)/16  or  (5x^2 - 12x)/16
so I'll work out the nearest integer to 5(x-1)^2/16 for odd x:

   1  3  5  7  9 11 13 15 
  ------------------------
   0  1  5 11 20 31 45 61   {5(x-1)^2/16}
  -1  0  4 10 19 30 44 60    f(x)

   So  f(x) is 1 more than the nearest integer to  5(x-1)^2/16,
for odd  x.  I have to go to lunch now, but "I shall return".

    John Conway