New twist(?) on old point-counting problem

[David Wilson]

(Best viewed in fixed width)

Let f be defined as

f(x, y) = 
    0, if y > x
    1, if y = 0
    2*SUM(k >= 1 and x-k^2 >= y; f(x-k^2, y-1)), otherwise.

A table of f(x, y), omitting the zero elements:

   \y|    0    1    2    3    4    5    6    7    8    9   10
   x\|
-----+-------------------------------------------------------
   0 |    1
   1 |    1    2
   2 |    1    2    4
   3 |    1    2    4    8
   4 |    1    4    4    8   16
   5 |    1    4   12    8   16   32
   6 |    1    4   12   32   16   32   64
   7 |    1    4   12   32   80   32   64  128
   8 |    1    4   16   32   80  192   64  128  256
   9 |    1    6   16   56   80  192  448  128  256  512
  10 |    1    6   24   56  176  192  448 1024  256  512 1024

Now use the xth row of this table as differences to generate sequence S_x. For example, taking x = 3, the third row is (1 2 4 8). Using these as differences, we generate the sequence:

                  8     8     8    ...
               4    12    20    28    ...
            2     6    18    38    66    ...
   S_3 = 1     3     9    27    65    131   ...

S_3 is indexed starting at 0.

It appears that S_x(n) gives the number of points in Z^n with norm <= sqrt(x). For example, there are S_3(4) = 65 points of Z^4 norm <= sqrt(3), namely:

(-1 -1 -1 0)
(-1 -1 0 -1)
(-1 -1 0 0)
(-1 -1 0 1)
(-1 -1 1 0)
(-1 0 -1 -1)
(-1 0 -1 0)
(-1 0 -1 1)
(-1 0 0 -1)
(-1 0 0 0)
(-1 0 0 1)
(-1 0 1 -1)
(-1 0 1 0)
(-1 0 1 1)
(-1 1 -1 0)
(-1 1 0 -1)
(-1 1 0 0)
(-1 1 0 1)
(-1 1 1 0)
(0 -1 -1 -1)
(0 -1 -1 0)
(0 -1 -1 1)
(0 -1 0 -1)
(0 -1 0 0)
(0 -1 0 1)
(0 -1 1 -1)
(0 -1 1 0)
(0 -1 1 1)
(0 0 -1 -1)
(0 0 -1 0)
(0 0 -1 1)
(0 0 0 -1)
(0 0 0 0)
(0 0 0 1)
(0 0 1 -1)
(0 0 1 0)
(0 0 1 1)
(0 1 -1 -1)
(0 1 -1 0)
(0 1 -1 1)
(0 1 0 -1)
(0 1 0 0)
(0 1 0 1)
(0 1 1 -1)
(0 1 1 0)
(0 1 1 1)
(1 -1 -1 0)
(1 -1 0 -1)
(1 -1 0 0)
(1 -1 0 1)
(1 -1 1 0)
(1 0 -1 -1)
(1 0 -1 0)
(1 0 -1 1)
(1 0 0 -1)
(1 0 0 0)
(1 0 0 1)
(1 0 1 -1)
(1 0 1 0)
(1 0 1 1)
(1 1 -1 0)
(1 1 0 -1)
(1 1 0 0)
(1 1 0 1)
(1 1 1 0)

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061027/d526f7c0/attachment-0001.htm>