On the Number of Representations of an Integer by a Linear Form

Gil Alon and Pete L. Clark 1126 Burnside Hall Department of Mathematics and Statistics McGill University 805 Sherbrooke West Montreal, QC H3A 2K6 Canada

                  alon@math.mcgill.ca
                 clark@math.mcgill.ca

Abstract

Let a_{1}, …, a_{k} be positive integers generating the unit ideal, and j be a residue class modulo L = lcm(a_{1}, …, a_{k}). It is known that the function r(N) that counts solutions to the equation x_{1}a_{1} + … + x_{k}a_{k} = N in non-negative integers x_{i} is a polynomial when restricted to non-negative integers N ≡ j (mod L). Here we give, in the case of k = 3, exact formulas for these polynomials up to the constant terms, and exact formulas including the constants for 𝔮 = gcd(a_{1}, a_{2}) · gcd(a_{1}, a_{3}) · gcd(a_{2}, a_{3}) of the L residue classes. The case 𝔮 = L plays a special role, and it is studied in more detail.

1 Introduction

We begin with some notation.

For a ∈ ℤ and n ∈ ℤ^{+}, let ⟨a⟩_{n} denote the unique non-negative integer that is congruent to a (mod n) and less than n. We view this as giving a map ⟨ ⟩ : ℤ/nℤ → {0, …, n − 1}, and the convention is that operations appearing inside the brackets are performed in the ring ℤ/nℤ. In particular, if gcd(b, n) = 1, then ⟨b^{−1}⟩_{n} is the unique integer N in the interval [0, n − 1] such that Nb ≡ 1 (mod n).

Let a_{1}, …, a_{k} be positive integers and N ∈ ℕ be a non-negative integer. We are interested in the quantity

r(N) = r(a_{1}, …, a_{k}; N) = #{(x_{1}, …, x_{k}) ∈ ℕ^{k} | x_{1}a_{1} + … + x_{k}a_{k} = N}.

We say that r(N) counts the number of representations of N by the system of weights (a_{1}, …, a_{k}).

A system of weights is (a_{1}, …, a_{k}) is primitive if gcd(a_{1}, …, a_{k}) = 1. Given a system (a_{1}, …, a_{k}) of weights with gcd(a_{1}, …, a_{k}) = d, clearly r(a_{1}, …, a_{k}; N) = 0 unless N is a multiple of d. And if N = dM, say, then we have r(a_{1}, …, a_{k}; dM) = r(\frac{a_{1}}{d} , …, \frac{a_{k}}{d}; M). So we may, and shall, consider only the primitive case.

Issai Schur showed long ago that there is a simple asymptotic formula for r(N) (Theorem 2.1(b)). We are interested in the problem of giving an “exact formula.” When k = 2 this is indeed possible: we have Popoviciu’s formula [7]

r(a, b; N) = \frac{N}{ab} − \{\frac{⟨a^{−1}⟩_{b}N}{b} \} − \{\frac{⟨b^{−1}⟩_{a}N}{a} \} + 1,  (1)

where {x} = x − ⌊x⌋ denotes the fractional part of x.

Some consequences: it follows that r(N) is the sum of a polynomial P (N) = \frac{N}{ab} and an ab-periodic function A(N). Moreover, for all N, −1 < A(N) ≤ 1, so

⌊\frac{N}{ab}⌋ ≤ r(a, b; N) ≤ ⌊\frac{N}{ab}⌋ + 1.

More precisely, the minimum value of A is 1 − \frac{b−1}{b} − \frac{a−1}{a}, attained when

⟨a^{−1}N⟩_{b} ≡ −1 (mod b), ⟨b^{−1}N⟩_{a} ≡ −1 (mod a).

The unique solution in the interval [0, ab) is N_{0} = (a − 1)(b − 1) − 1. A straightforward calculation gives r(N_{0}) = 0; alternately, just observe that A(N_{0}) < 0, \frac{N_{0}}{ab} < 1, and r(N_{0}) ∈ ℕ. Also, for N_{0} < N < ab we have A(N) > A(N_{0}) and P (N) > P (N_{0}), so r(N) > r(N_{0}) = 0; and since we clearly have r(N) ≥ 1 for N ≥ ab, it follows that N_{0} is the largest value of N for which r(N) = 0.

For any primitive set (a_{1}, …, a_{k}) of weights, one defines the Frobenius number 𝔣(a_{1}, …, a_{k}) to be the largest N such that r(N) = 0. That such a number exists is not a priori obvious, but follows from Theorem 2.1(b) (or from Theorem 7.4). Thus one of the merits of Popoviciu’s formula is that from it we can “read off” the Frobenius number for two weights:^{1}

𝔣(a_{1}, a_{2}) = (a_{1} − 1)(a_{2} − 1) − 1.  (2)

The ideal would be to give a formula for r(N) in the general case that is “as satisfactory” as (1) in the k = 2 case. This is probably impossible, and subject to a formalization of “as satisfactory” may even be provably impossible: we propose the heuristic that a “sufficiently satisfactory” formula for r(a_{,} …, a_{k}; N) should (as above) lead to an exact formula for the Frobenius number 𝔣(a_{1}, …, a_{k}). However, there is no known exact formula for the Frobenius number when k ≥ 3, although 𝔣 can be computed in polynomial time for fixed k [5]. When k is included as a parameter, it is known [8] that the problem of computing 𝔣(a_{1}, …, a_{k}) is NP-hard!

1Admittedly this formula is easily derived in many other ways; see Section 7.

Still, one observes in the k = 2 case that by restricting to values of N in a fixed residue class j modulo a_{1}a_{2}, the function r(a_{1}, a_{2}; N) is a polynomial in N. Equivalently, for all j, the function r_{j}(n) = r(a_{1}, a_{2}; j + a_{1}a_{2}n) is a polynomial. This turns out to hold true in the general case: the function r_{j}(n) = r(j + a_{1} ⋯ a_{k}n) is a polynomial function, so we can exchange the one problem of finding a formula for r(N) for the a_{1} ⋯ a_{k} problems of finding the coefficients of these polynomials.

The problem of finding a formula for r_{j}(n) (for any given j) seems not to have received much attention as such. The reasons for this may be as follows: first, “all one has to do” is to compute the coefficients in the partial fraction decomposition the rational function R(x) of equation (5). More precisely, the method of partial fractions leads to a decomposition of r(N) into a finite sum of terms – indexed by the poles of R(x) – in which the term f_{0}(n) corresponding to the pole at x = 1 has the highest order of magnitude. Moreover the computation of f_{0}(n) is relatively tractable; indeed [1] gives an exact formula for f_{0}(n) in the general case. Computation of the other terms is more involved, but in the case in which the weights are coprime in pairs, the difference r(n) − f_{0}(n) is a periodic function, so knowing f_{0}(n) is enough to compute each polynomial r_{j}(n) up to a constant. This does not hold in the general case, and here the method of partial fractions, will, in the words of [9], “entail an enormous amount of bookkeeping.” The unpleasantness of these calculations, together with the existence of a formula due to Johnson (11) which in the case of k = 3 reduces the computation of the Frobenius number 𝔣(a_{1}, a_{2}, a_{3}) to the pairwise coprime case, seems to have focused attention away from the problem of computation of the r_{j}(n) in the general case.

In this paper we derive explicit formulas for r_{j}(a_{1}, a_{2}, a_{3}; n) up to a constant for a general primitive system (a_{1}, a_{2}, a_{3}). In contrast to the methods described above, our approach is mostly independent of the partial fraction decomposition. Moreover, in a sense that will shortly be made precise, our results improve as the weights become “less and less pairwise coprime.” In particular, for a certain class of weights (called extremal), we get exact formulas for r_{j}(n) for all j.

2 Statement of the Main Results

Let (a_{1}, …, a_{k}) be a primitive set of weights, P = a_{1} ⋯ a_{k} and L = lcm(a_{1}, …, a_{k}). For 0 ≤ j < L, let r_{j}(n) = r(j + Ln).

Theorem 2.1. For any primitive set of weights (a_{1}, …, a_{k}), we have

(a) For each j, the function n ↦ r_{j}(n) is the restriction to ℕ of a degree k − 1 polynomial with rational coefficients.

(b)

r(N) ∼ \frac{N^{k−1}}{(k − 1)!(a_{1} ⋯ a_{k})}.

Remark: Part (b) is due to Issai Schur and has been rediscovered many times since. Part (a) is also well known. Probably the quickest proof is via the method of generating functions, as we shall have reason to recall. On the other hand, we shall also give combinatorial/geometric proofs of part (b), and of part (a) in the case k = 3.

The remainder of the results concern only the case k = 3. We introduce the following additional notation:

For any ordering (i, j, k) of the set {1, 2, 3}, let d_{k} = gcd(a_{i}, a_{j}), and put 𝔮 = d_{1}d_{2}d_{3}. The following are all consequences of primitivity:

(i) the d_{i}’s are pairwise coprime;

(ii) 𝔮L = P;

(iii) 𝔮 divides L.

For 0 ≤ j < L, define R_{j}(N) = r_{j}(\frac{N−j}{L}). The point of this change of variables is so that R_{j}(N) = r(N) when N ≡ j (mod L).

Theorem 2.2.

r_{0}(n) = \frac{L}{2𝔮}n^{2} + \frac{a_{1}d_{1} + a_{2}d_{2} + a_{3}d_{3}}{2𝔮} n + 1.

Remark: This result appears in several places in the case where the weights are pairwise coprime, but we were not able to find the general case in the literature. Again we give an elementary geometric proof, using a version of Pick’s Theorem.

For 0 ≤ j < L, define

y_{i}(j) = ⟨a_{i}^{−1}j⟩_{d_{i}},
y(j) = y_{1}(j)a_{1} + y_{2}(j)a_{2} + y_{3}(j)a_{3}.

(The function j ↦ y(j) has the effect of projecting a complete system of residues modulo L onto a set of 𝔮 distinct “good” residue classes modulo L, which form a complete system of residues modulo 𝔮.)

Also define polynomials Q_{j}(N), P_{j}(N) as follows:

Q_{j}(N) = r_{0} (\frac{N − y(j)}{L}) ,

P_{j}(N) = Q_{j}(N) − Q_{j}(j) + r(j).

The following is our main result:

Theorem 2.3. For all 0 ≤ j < L

(a) For all N ≡ y(j) (mod L), we have r(N) = R_{j}(N) = Q_{j}(N).

(b) For all N ≡ j (mod L), we have r(N) = R_{j}(N) = P_{j}(N).

To illustrate Theorem 2.3 we consider the case of Chicken McNuggets. Recall that they are sold in packs of 6, 9 and 20, and a now classic brainteaser asks, “What is the largest number of Chicken McNuggets you can’t buy?” or more succinctly, “What is 𝔣(6, 9, 20)?” An answer to this question follows directly from some material we shall present in Section 7. Here we are concerned with the problem of computing r(6, 9, 20; N).

Example 1: We will compute the number of ways to buy 1, 080, 005 Chicken McNuggets, or r(6, 9, 20; 1, 080, 005). We have (d_{1}, d_{2}, d_{3}) = (1, 2, 3), 𝔮 = 6 and L = 180. We shall compute R_{j}(N) for N congruent to 1080005 ≡ 5 mod L. We have y_{1}(5) = 0, y_{2}(5) = 1, y_{3}(5) = 1, so y(5) = 29. By Theorem 2.3 we get

Q_{5}(N) = R_{46}(N) = \frac{1}{2160}N^{2} + \frac{13}{1080}N + \frac{113}{432}

and

R_{5}(N) = Q_{5}(N) − Q_{5}(5) + r(5).

Since clearly r(5) = 0, we get

R_{5}(N) = \frac{1}{2160}N^{2} + \frac{13}{1080}N − \frac{31}{432}.

Thus there are r(1, 080, 005) = R_{5}(1, 080, 005) = 540, 018, 000 ways to buy 1, 080, 005 Chicken McNuggets.

Example 2: We will compute r(6, 9, 20; 1, 000, 000). We have 1000000 ≡ 100 (mod L), so we compute y_{1}(100) = 0, y_{2}(100) = 0, y_{3}(100) = 2, y(100) = 40. Applying Theorem 2.3, we get

Q_{100}(N) = \frac{1}{2160}N^{2} + \frac{1}{540}x + \frac{5}{27}

and

R_{100}(N) = Q_{100}(N) − Q_{100}(100) + r(100).

This last quantity can be evaluated using the identities

r(100) = r(80) + r(6, 9; 100) = … = ∑_{i=0}^{5} r(6, 9; 100 − 20i),

which divide up the set of all representations of 100 by (6, 9, 20) according to the number of times the weight 20 is used. Clearly r(6, 9, 100 − 20i) = 0 unless 100 ≡ 20i (mod 3), i.e., unless i = 2 or i = 5. Certainly r(6, 9; 0) = 1, and one sees easily (by Popoviciu’s formula, or otherwise) that r(6, 9; 60) = r(2, 3; 20) = 4.

Thus r(100) = 5. In fact Q_{100}(100) = 5 as well, so that we have R_{100}(N) = Q_{100}(N) = R_{40}(N). Thus the answer is r(1, 000, 000) = 462, 964, 815.

As mentioned above, the strength of Theorem 2.3 is inversely proportional to the size of \frac{L}{𝔮}: we know that r(N) is given by a (possibly) different quadratic polynomial on each residue class of N (mod L), and part (a) gives an exact formula for the 𝔮 “good” residue classes. For the other classes, we are giving the leading term (always \frac{1}{2P}) and the linear term but not the constant term. As the above examples show, the amount of computation needed to compute the constant term depends upon the size of the residue class j: if j is nearly as large as L, then it would require only about twice as much calculation to compute both r(j) and r(j + L) and interpolate, but if j is small the above method is much faster. In particular, we certainly have r(j) = 0 if 0 < j < min(a_{1}, a_{2}, a_{3}) (as in Example 1), so we have rather more exact formulas than was originally advertised.

Note that in the case 𝔮 = L we are getting exact formulas for every residue class; in this case (and only in this case) we claim Theorem 2.3 as the analogue of Popoviciu’s formula for k = 3. And indeed it is “sufficiently satisfactory” in the above sense: it can be used to derive an exact formula for 𝔣(a_{1}, a_{2}, a_{3}). This discussion is carried out in Section 7.

Unfortunately our use of generating functions in the proof of Theorem 2.3(b) seems to be essential, so in order to make our work self-contained, we begin with a review of the generatingfunctionological approach.

3 Quasi-polynomials, generating functions and partial fractions

A function r : ℕ → ℂ for which there exists L ∈ ℤ^{+} such that for each j, 0 ≤ j < L, r_{j}(n) = r(j + Ln) is a polynomial function P_{j}(n) is called a quasi-polynomial with period L. We define the degree of a quasipolynomial as the maximum of the degrees of the P_{j}’s.

Consider the collection Q = Q(L, d) of all quasipolynomials of period L and degree at most d − 1. Evidently Q is a ℂ-subspace of the vector space of all functions r : ℕ → ℂ. Moreover, since each polynomial P_{j} is uniquely determined by the values of r at j, j + L, …, j+(d−1)L, an element of Q is uniquely specified by its first dL values, so dim Q = dL.

In this case, the implied basis is given by L applications of the Lagrange interpolation theorem. Another basis is given as follows: for 0 ≤ i < d and 0 ≤ j < L, we define μ_{ij}(n) = ζ^{nj}n^{i}, where ζ is a fixed choice of a primitive Lth root of unity (say ζ = e^{\frac{2πi}{L}}). A slight modification of this basis turns out be more convenient: for i and j as above, put e_{ij}(n) = \binom{n}{i}ζ^{nj}. To see why, consider the generating function

E_{ij}(x) = ∑_{n≥0} e_{ij}(n)x^{n}.

By taking the ith derivative of the identity ∑_{n} x^{n} = \frac{1}{1−x}, we get:

E_{i0}(x) = ∑_{n≥0} \binom{n + i}{i}x^{n} = \frac{1}{(1 − x)^{i+1}} .

It follows that

E_{ij}(x) = E_{i0}(ζ^{j}x) = ∑_{m} \binom{n + i}{i}ζ^{nj}x^{n} = \frac{1}{(1 − ζ^{j}x)^{i+1}} .  (3)

From this we readily deduce the following basic result:

Proposition 3.1. For a function f : ℕ → ℂ, the following are equivalent:

(a) f ∈ Q(L, d) is a quasi-polynomial of period L and degree at most d − 1.

(b) The generating function F (x) = ∑_{n} f(n)x^{n} of f is a rational function of the form \frac{P (x)}{(1−x^{L})^{d}}, where deg P < Ld.

Proof. Certainly the space of proper rational functions of the above form has the right dimension, so it suffices to see that the Taylor series coefficients are quasipolynomial functions of n. The key point is that, as for any proper rational function R(X) = \frac{P (x)}{Q(x)} with Q(0) ≠ 0, we have a partial fractions decomposition

\frac{P (x)}{Q(x)} = ∑_{j=0}^{M−1} ∑_{i=1}^{m_{j}} \frac{C_{ij}}{(1 − s_{j}x)^{i}} .  (4)

Here s_{1}, …, s_{M} are the reciprocals (s_{j} = r_{j}^{−1}) of the distinct zeros r_{j} of the denominator Q(x), and m_{j} denotes the multiplicity of r_{j}. In the given case, the (reciprocal) zeros of the denominator are Lth roots of unity, so the partial fractions decomposition precisely expresses \frac{P (x)}{(1−x^{L})^{d}} as a ℂ-linear combination of the E_{ij}(x)’s. This proves the result.

Now fix a primitive system of weights (a_{1}, …, a_{k}) and consider the generating function R(x) = ∑ r(n)x^{n} for r(n) = r(a_{1}, …, a_{k}; n). We have the identity

R(x) = (1 + x^{a_{1}} + x^{2a_{1}} + …) ⋯ (1 + x^{a_{k}} + x^{2a_{k}} + …) = \frac{1}{(1 − x^{a_{1}}) ⋯ (1 − x^{a_{k}})}. (5)

Let D(x) = (1 − x^{a_{1}}) ⋯ (1 − x^{a_{k}}). Recalling that we have put L = lcm(a_{1}, …, a_{k}), the (reciprocal) zeros of D(x) are all Lth roots of unity, but some zeros may occur with multiplicity greater than one: e.g., x = 1 occurs with multiplicity k. Since 1 − x^{a_{i}} has distinct zeros, it is clear that m_{i} ≤ k for all i, so there exists a polynomial N(x) such that N(x)D(x) = (1−x^{L})^{k}, whence R(x) = \frac{N(x)}{(1−x^{L})^{k}}, and we conclude that r(n) is a quasipolynomial of period L and degree at most k − 1. Thus we have proved Theorem 2.1(a).

Before proceeding further, there is something to be addressed: is it not the case that Proposition 4 already gives the explicit formula for r(N) that we seek? Namely, with C_{ij} equal to the coefficient of (1 − ζ^{−j}x)^{−i}, then using (4) and (5), do we not get

r(n) = ∑_{j=0}^{M−1} ∑_{i=1}^{m_{j}} C_{ij}\binom{n + i − 1}{i − 1}ζ^{nj} ?

Certainly we do. However, this formula has its shortcomings. First, it is not really a formula at all until we say what the coefficients C_{ij} are. The total number of such coefficients is equal to S = a_{1} +…+a_{k}. We all know how the C_{ij}’s are supposed to be computed: starting with the identity

\frac{1}{(1 − x^{a_{1}}) ⋯ (1 − x^{a_{k}})} = ∑_{j=0}^{M−1} ∑_{i=1}^{m_{j}} \frac{C_{ij}}{(1 − s_{j}x)^{i}} ,  (6)

cross multiplication yields an S × S linear system to be solved for the C_{ij}’s. But, as any calculus student knows, the amount of computation needed to solve such linear systems quickly gets out of hand. Second, even if we happen to know all the C_{ij}’s, then our explicit formula for r(n) will still be an unwieldy mess. Our difficulties are really linear algebraic in nature: the method of partial fractions computes the coefficients of the basis e_{ij} of Q(L, d), which is the wrong basis for efficient computation of the coefficients of r_{j}(n).

However, the partial fractions decomposition is a powerful tool for extracting other information about the function r(n). Let us look at it a bit more carefully: first, for any fixed j corresponding to an Lth root of unity ζ^{−j} of order w_{j}, we get a contribution to r(n) that is a function of the form f_{j}(n)ζ^{−jn}, where f_{j}(n) is a polynomial of degree m_{j} − 1. If j = 0, f_{0}(n) is an honest polynomial of degree k − 1. For a general j, the multiplicity m_{j} is equal to the number of i’s for which w_{j} | a_{i}, so if w_{j} > 1, the primitivity of the system assures that m_{j} ≤ k − 1. (So if the coefficients a_{i} were coprime in pairs, we would have that f_{j}(n) is a constant for all j ≠ 0.) This implies r(n) is asymptotic to the leading term of f_{0}(n):

r(n) ∼ C_{0k}\binom{n + k − 1}{k − 1} = \frac{C_{0k}}{(k − 1)!}n^{k−1}.

We can compute C_{0k}: just multiply (6) by (1 − x)^{k} and evaluate at x = 1, getting

C_{0k} = \frac{1}{(1 + x + … + x^{a_{1}−1}) ⋯ (1 + x + … + x^{a_{k}−1})}|_{x=1} = \frac{1}{a_{1} ⋯ a_{k}} .

Thus we get

r(n) ∼ \frac{n^{k−1}}{(k − 1)!(a_{1} ⋯ a_{k})},

establishing Theorem 2.1(b).

For later use (indeed, the only essential use we shall make of the methods of this section), we record the following result:

Lemma 3.2. Let k = 3, and write r(n) = c_{2}(n)n^{2} + c_{1}(n)n + c_{0}(n), where the c_{i}(n)’s are periodic modulo L. The linear term c_{1} is in fact periodic modulo 𝔮 = d_{1}d_{2}d_{3}.

Proof. In general we have r(n) = ∑_{j=0}^{M−1} f_{j}(n)ζ^{−jn}, where f_{j}(n) is a polynomial of degree equal to one less than the number of i’s for which a_{i} divides the order w_{j} of ζ^{−j}. Thus f_{j}(n) has a linear term only when w_{j} divides two of a_{1}, a_{2}, a_{3}, i.e., when w_{j} | d_{1}d_{2}d_{3}.

4 Lattice Geometry

The problem of computing the number of solutions to x_{1}a_{1}+…+x_{k}a_{k} = N has an evident geometric interpretation: let T_{N} denote the locus of solutions to this same equation among nonnegative real numbers: this forms a simplex in ℝ^{k} whose vertices are V_{i} = (0, 0, …, \frac{N}{a_{i}} , …, 0) for 1 ≤ i ≤ k. Thus we can look at r(N) as counting the lattice points – i.e., points with integral coordinates, on the simplex T_{N}.

In other words, even counting lattice points in triangles with rational vertices is a difficult problem! However, it has long been known that if the vertices of the triangle have integral coordinates (i.e., are themselves lattice points), then there is a wonderful explicit formula. Theorem 2.2 will follow easily from the following elementary result (for the proof, see e.g. [3]), a version of Pick’s Theorem “renormalized” for two-dimensional lattices in higher-dimensional Euclidean spaces.

Theorem 4.1. (Pick’s Theorem) Let Λ be a two-dimensional lattice in ℝ^{k} with 2-volume δ. Let P be a lattice polygon containing h interior lattice points and b boundary lattice points. Then the area A(P) of P is equal to δ · (h + \frac{b}{2} − 1).

Let r(P) = h + b be the total number of lattice points of P. Then Pick’s Theorem is equivalent to the formula

r(P) = \frac{A(P)}{δ} + \frac{b}{2} + 1.  (7)

We can now prove Theorem 2.2.

Proof. Although we have “the right” to compute r_{0}(n) = r(nL) directly, we will find it easier to first derive a formula for r(nP) and then change variables to obtain the formula for r_{0}(n).

To compute r(nP) we must count lattice points on the simplex

T_{n} : x_{1}a_{1} + x_{2}a_{2} + x_{3}a_{3} = nP,

whose vertices are V_{1} = (a_{2}a_{3}n, 0), V_{2} = (0, a_{1}a_{3}n, 0) V_{3} = (0, 0, a_{1}a_{2}n). Clearly we have \frac{A(P)}{δ} = αn^{2} for some nonzero α, whereas from Section 3 we know that r(T_{n}) is a quadratic polynomial in n whose leading coefficient is (P)^{2}/2(P) = \frac{P}{2} . Thus from our algebraic formalism we get that α = \frac{a_{1}a_{2}a_{3}}{2} .

As for the linear term, the number of lattice points on any line segment joining two integer points V_{i} = (x_{i}, y_{i}, z_{i}) and V_{j} = (x_{j}, y_{j}, z_{j}) is equal to gcd(x_{i} − x_{j}, y_{i} − y_{j}, z_{i} − z_{j}). If for distinct i, j ∈ {1, 2, 3} we denote by ℓ_{ij} the line segment from V_{i} to V_{j}, we have

#(ℤ^{3} ∩ ℓ_{ij}) = a_{k}N gcd(a_{i}, a_{j}) = a_{k}d_{k}N,

where k is the remaining index. This gives

r(nP) = \frac{a_{1}a_{2}a_{3}}{2} + \frac{a_{1}d_{1} + a_{2}d_{2} + a_{3}d_{3}}{2} n + 1.

Finally, observe that r(nL) is also given by a quadratic polynomial in n. On the one hand, this follows immediately from the considerations of the previous section – we know that r(N) is a quasi-polynomial with period L. On the other hand, even without computing the coefficients explicitly, the above argument using Pick’s Theorem establishes this fact. Thus r_{0}(𝔮n) = r(𝔮Ln) = r(Pn) is an identity of quadratic polynomials, so it can be inverted to give r_{0}(n) = r(P(\frac{n}{𝔮})). Performing this change of variables gives the formula of Theorem 2.2.

Remark: A less sneaky proof would compute A(T_{n}) and δ and not merely their ratio. This will be done in Section 6.

5 Recursions and congruences

Let (a_{1}, …, a_{k}) be any primitive set of weights. We will get a lot of mileage out of the following innocuous identity:

r(n + a_{1}) = r(n) + r(a_{2}, …, a_{k}; n + a_{1}).  (8)

The proof could hardly be simpler: the representations of n+a_{1} by weights a_{1}, …, a_{k} that use a_{1} at least once are in one-to-one correspondence with all representations of n by a_{1}, …, a_{k}, and the ones that do not use a_{1} at all are actually representations by a_{2}, …, a_{k}.

There are of course analogous formulas for the other weights, which we use without comment.

We now return to the case of k = 3.

Proposition 5.1. Let 0 ≤ y_{i} < d_{i}. Then

r(y_{1}a_{1} + y_{2}a_{2} + y_{3}a_{3} + nL) = r(nL).

Proof. Assume that d_{1} > 1. We have r(a_{1}+nL) = r(nL)+r(a_{2}, a_{3}; a_{1}+nL). Since 𝔮 divides L and (a_{1}, d_{1}) = 1, we have that d_{1} does not divide a_{1}+nL, so necessarily r(a_{2}, a_{3}; a_{1}+nL) = 0. Repeated application of this argument gives the result.

Recall that we have defined numbers y_{i}(j) = ⟨a_{i}^{−1}j⟩_{d_{i}} and y_{j} = y_{1}a_{1} + y_{2}a_{2} + y_{3}a_{3}. By construction y(j) is congruent to j modulo L and satisfies the hypothesis of Proposition 5.1. Thus we have

r_{y(j)}(n) = r(y_{1}a_{1} + y_{2}a_{2} + y_{3}a_{3} + nL) = r(nL) = r_{0}(n).

The change of variables n = \frac{N−y(j)}{L} gives us the expression for r(N) valid on the congruence class y(j), which gives Theorem 2.3(a). Since y(j) ≡ j (mod L), applying Lemma 3.2, the expression Q_{j}(N) = r_{0}(\frac{N−y(j)}{L}) differs from the correct expression for r(N) on the class j by at most a constant. The expression for P_{j}(N) corrects for this (in a rather tautological way) by ensuring that P_{j}(j) = r(j). This completes the proof of Theorem 2.3.

6 Geometric and Combinatorial Proofs

In this section we give proofs of the results of this paper (except Theorem 2.3(b)) that do not require the theory of generating functions.

6.1 More lattice geometry

First, recall that r(N) = r(a_{1}, …, a_{k}; N) counts lattice points on the simplex T_{N} given by the intersection of the hyperplane x_{1}a_{1} + … + x_{k}a_{k} = N with the positive orthant. As N varies, the lattices of integral solutions are isometric – they are all principal homogeneous spaces for the rank k − 1 free abelian group of integral solutions to x_{1}a_{1} + … x_{k}a_{k} = 0. Thus these lattices have a common 2-volume δ. Because the simplices T_{N} are similar, as N approaches infinity we must have r(N) ∼ \frac{A(T_{N})}{δ} (more precisely, the geometric picture gives |r(N) − \frac{A(T_{N})}{δ}| = O(N^{k−2}).) We saw earlier that the ratio of these two quantities is \frac{N^{k−1}}{(k−1)!(a_{1}···a_{k})}, but we shall now compute both quantities individually.

Let Λ ⊂ ℝ^{k} be a d-dimensional sublattice of ℤ^{k}, i.e., the ℤ-span of d ℝ-linearly independent vectors {v_{1}, …, v_{k}} with integral coordinates. The volume of Λ is the d-dimensional volume of any fundamental region for Λ, e.g. of the paralleletope formed by {x_{1}v_{1}+… x_{d}v_{d} | 0 ≤ x_{i} ≤ 1}.

Given an orthonormal basis e_{1}, …, e_{d} of the vector space V spanned by Λ, we can write v_{i} = ∑_{ij} α_{ij}e_{j}, and we have Vol(Λ) = det(α_{ij}). Alternately, for any ℤ-basis {v_{1}, …, v_{k}} for Λ, Vol(Λ) is the square root of the determinant of the Gram matrix M_{ij} = v_{i} · v_{j}.

The problem is that our lattice

Λ_{0} = {(z_{1}, …, z_{k}) ∈ ℤ^{k} | z_{1}a_{1} + … + z_{k}a_{k} = 0},

a k − 1-dimensional lattice in ℝ^{k}, does not come equipped with any natural basis. Nevertheless we present the following method to compute the volume of any lattice Λ_{a} defined by the hyperplane equation (z_{1}, …, z_{k}) · a = 0, for a = (a_{1}, …, a_{k}) a primitive set of weights (rebaptized here as a primitive vector).

Let Λ = ℤv_{1} ⊕ … ⊕ ℤv_{k−1} ⊂ ℤ^{k}. With e_{1}, …, e_{k} an orthonormal basis of ℝ^{k}, define the generalized cross-product

cross(v_{1}, …, v_{k−1}) = [ e_{1} … e_{k} ; ⟵ v_{1} ⟶ ; ⋮ ; ⟵ v_{k−1} ⟶ ]

By expanding out the determinant, one checks that cross(v_{1}, …, v_{k−1}) is orthogonal to Λ and that Vol(Λ) = || cross(v_{1}, …, v_{k−1})||.

Example: Take k = 2 and a = (a_{1}, a_{2}) a primitive vector. Then Λ_{a} = ℤ(−a_{2}, −a_{1}), i.e. the orthogonal complement of v is obtained by rotating ℤa through a 90 degree angle. Notice that in this case the 1-volume of a is equal to the (k − 1)-volume of Λ_{a}.

That this remains true in higher dimensions is the content of the following result:

Lemma 6.1. Let a = (a_{1}, …, a_{k}) be a primitive vector. Then

Vol(Λ_{a}) = Vol(a) = \sqrt{a_{1}^{2} + … + a_{k}^{2}}.

Proof. For any v_{1}, …, v_{k−1} is a ℤ-basis of Λ_{a}, Vol(Λ_{a}) = || cross(v_{1}, …, v_{k−1})||. On the other hand, the cross product of integer vectors remains an integer vector, so cross(v_{1}, …, v_{k−1}) and a are two integer vectors spanning the same 1-dimensional ℝ-subspace. Since a is assumed to be primitive, we must have cross(v_{1}, …, v_{k−1}) = na, for some integer n, so that Vol(Λ_{a}) ≥ Vol(a). We claim that n = 1, which will finish the proof.

To establish the claim, consider the set C = {cross(w_{1}, …, w_{k−1}) | w_{i} ∈ Λ_{a}} of vectors that are cross-products from Λ_{a}. Writing w_{i} = Σα_{ij}v_{j} with α_{ij} in ℤ, we get

cross(w_{1}, …, w_{k−1}) = det(α_{ij}) cross(v_{1}, …, v_{k−1}),

which shows that C is just the 1-dimensional lattice generated by cross(v_{1}, …, v_{k_{1}}). In particular, we can exploit the fact that C is a ℤ-module as follows: note that Λ_{a} is precisely the set of integer solutions of

a_{1}z_{1} + … + a_{k}z_{k} = 0.

Thus

v_{1} = (−a_{2}, a_{1}, 0, …, 0), v_{2} = (−a_{3}, 0, a_{1}, 0, …, 0), …, v_{k−1} = (−a_{k}, 0, …, a_{1})

are all elements of Λ_{a}, so that

cross(v_{1}, …, v_{k−1}) = a_{1}^{k−2}(a_{1}, …, a_{k−1})

is a vector in C. By symmetry, we see that a_{2}^{k−2}(a_{1}, …, a_{k−1}), …, a_{k}^{k−2}(a_{1}, …, a_{k}) are also vectors of C. Since C is a ℤ-module, we know that for any integers z_{1}, …, z_{k}, we have

(z_{1}a_{1}^{k−2} + z_{2}a_{2}^{k−2} + … z_{k}a_{k}^{k−2})(a_{1}, …, a_{k}) ∈ C.

Since (a_{1}, …, a_{k}) is primitive, so is (a_{1}^{k−2}, …, a_{k}^{k−2}), so that we can choose z_{1}, …, z_{k} such that z_{1}a_{1}^{k−2} + … + z_{k}a_{k}^{k−2} = 1. But this implies that a = (a_{1}, …, a_{k}) is in C, and n = 1. This establishes the claim and completes the proof of Lemma 6.1.

Coming back to our lattice Λ_{0}, we have Vol(Λ_{0}) = \sqrt{a_{1}^{2} + … + a_{k}^{2}}. It remains to compute the volume of T_{N}. First consider the (k − 1)-paralleletope P_{N} whose sides are the vectors v_{1} − v_{2}, v_{1} − v_{3}, …, v_{1} − v_{k}, where v_{i} = \frac{N}{a_{i}} e_{i} gives the intersection points of the simplex H_{N} ∩ ℝ^{k+} with the coordinate axes. Using the cross-product, we calculate

Vol(P_{N}) = \frac{\sqrt{a_{1}^{2} + … + a_{k}^{2}}N^{k−1}}{a_{1} ⋯ a_{k}} .

Noting that the cone on an r-dimensional base has volume equal to 1/(r + 1) times the corresponding cylinder, induction then gives that

Vol(T_{N}) = \frac{1}{(k − 1)!} Vol(P_{N}) = \frac{\sqrt{a_{1}^{2} + … + a_{k}^{2}}}{a_{1} ⋯ a_{k}} \frac{N^{k−1}}{(k − 1)!}.

Thus we conclude once again that

r(a_{1}, …, a_{k}, N) ∼ \frac{N^{k−1}}{a_{1} ⋯ a_{k}(k − 1)!}.

6.2 More recursions and congruences

Using the results of the last section, it is easy to rederive the quasipolynomiality of r(N) = r(a_{1}, a_{2}, a_{3}; N). We need only use our basic recursion formula

r(a_{1} + N) = r(N) + r(a_{2}, a_{3}; a_{1} + N)

“in reverse.” Namely, fix a class j (mod L). Since, for all positive integers N we have r(N) = r(N + a_{1}) − r(a_{2}, a_{3}; N + a_{1}), taking N = j + nL, we get

r(j + nL) = r(a_{1} + j + nL) − r(a_{2}, a_{3}; a_{1} + j + nL).  (9)

A similar formula holds for a_{2} and a_{3}. By Theorem 1(b), every sufficiently large integer N is representable by the system (x_{1}, x_{2}, x_{3}); in particular, there exist x_{1}, x_{2}, x_{3} such that L | x_{1}a_{1} + x_{2}a_{2} + x_{3}a_{3} + j. Repeated application of (8) gives that r(j + nL) − r(x_{1}a_{1} + x_{2}a_{2} + x_{3}a_{3} + j + nL) is equal to a sum of x_{1} + x_{2} + x_{3} terms of the form r(a_{i}, a_{j}; a_{k} + c_{ijk} + nL) for various positive integers c_{ijk}. Now it is easy to see that each of these terms is either zero or a linear polynomial in n: e.g. this can be seen by contemplating the family of planar line segments

L_{N} = {(x_{1}, x_{2}) ∈ ℝ^{2} | x_{1}a_{1} + x_{2}a_{2} = N, x_{1}, x_{2} ≥ 0},

the two-dimensional analogue of the family of simplices T_{N} considered above. The geometric picture makes clear that for any positive integers a, b, j, r(a, b; j + lcm(a, b)) − r(a, b; j) is equal to 1 if gcd(a, b) | j and 0 otherwise. Details are left to the reader.

Thus r(j + nL) differs from r(x_{1}a_{1} + x_{2}a_{2} + x_{3}a_{3} + j + nL) by a linear polynomial. But since x_{1}a_{1} + x_{2}a_{2} + x_{3}a_{3} + j = ML, we have r(x_{1}a_{1} + x_{2}a_{2} + x_{3}a_{3} + j + nL) = r((M + n)L) = r_{0}(M +n), which by Theorem 2 is a quadratic polynomial. Thus r(j+nL) is itself a quadratic polynomial, which was to be shown.

7 Extremal systems

Suppose (a_{1}, a_{2}, a_{3}) is a primitive system of weights with 𝔮 = L; we say the system is extremal. This implies that a_{i} = \frac{𝔮}{d_{i}}. Conversely, given any triple (d_{1}, d_{2}, d_{3}) of pairwise coprime positive integers, by putting a_{i} = \frac{d_{1}d_{2}d_{3}}{d_{i}}, we get an extremal system.

The extremal systems are, in many ways, the three-dimensional systems whose behavior most closely parallels that of two-dimensional systems. In particular, their Frobenius number can be computed:^{2}

Proposition 7.1. Let d_{1}, d_{2}, d_{3} pairwise coprime positive integers. Then

𝔣(d_{1}d_{2}, d_{1}d_{3}, d_{2}d_{3}) = 2d_{1}d_{2}d_{3} − d_{1}d_{2} − d_{1}d_{3} − d_{2}d_{3}.

This result appeared as Problem A3 on the 1983 International Mathematical Olympiad. We shall discuss four proofs. First, we begin with the following general observation.

Lemma 7.2. Let (a_{1}, a_{2}, a_{3}) be any primitive system of weights. For 1 ≤ i ≤ 3, the Frobenius number 𝔣 = 𝔣(a_{1}, a_{2}, a_{3}) satisfies 𝔣 ≡ −a_{i} (mod d_{i}).

Proof. By symmetry, it suffices to consider the case i = 1. Since 𝔣 + a_{1} > 𝔣, we can write 𝔣 + a_{1} as x_{1}a_{1} + x_{2}a_{2} + x_{3}a_{3}, with nonnegative x_{i}’s. But x_{1} cannot be positive, since that would lead to a representation of 𝔣 by a_{1}, a_{2} and a_{3}. So 𝔣 + a_{1} is an integral combination of a_{2} and a_{3}, and is therefore divisible by d_{1}.

2Another property enjoyed by all extremal systems is the so-called Gorenstein condition: namely, that exactly half of the positive integers N ≤ 𝔣(a_{1}, …, a_{k}) + 1 can be represented [6].

Compiling the three congruences, we get

𝔣 ≡ (d_{1} − 1)a_{1} + (d_{2} − 1)a_{2} + (d_{3} − 1)a_{3} (mod 𝔮).  (10)

The right-hand side of (10) is equal to 3d_{1}d_{2}d_{3} − d_{1}d_{2} − d_{1}d_{3} − d_{2}d_{3} = j_{0}, say.

By Theorem 2.3, we have r_{j_{0}}(n) = r_{0}(n) for all n, so that we have an explicit formula for r on the class containing 𝔣, namely 𝔮^{2}R_{j_{0}}(N) =

\frac{1}{2}N^{2} + \frac{2a_{1} + 2a_{2} + 2a_{3} − 3𝔮}{2}N + 𝔮^{2} − \frac{3}{2}(a_{1} + a_{2} + a_{3})𝔮 + \frac{1}{2}(a_{1}^{2} + a_{2}^{2} + a_{3}^{2}) + 𝔮(d_{1} + d_{2} + d_{3}).

Hence R_{j_{0}}(j_{0} − L) = R_{j_{0}}(j_{0} − 2L) = 0. Since R_{j_{0}}(N) is a quadratic polynomial, it can have no further zeros, so 𝔣(a_{1}, a_{2}, a_{3}) = j_{0} − L.

Here is a second, more conceptual proof: we know that r(j_{0}) = r_{j_{0}}(0) = r_{0}(0) = 1, so 𝔣 ≠ j_{0}. In general, since r(L) > 0, the function r(N) is nondecreasing on any given congruence class modulo L. Here L = 𝔮 = a_{i}d_{i}, so we conclude that 𝔣 < j_{0} and it is enough to show that r(j_{0} − L) = 0. But, by our usual recursion we have

1 = r(j_{0}) = r(j_{0} − d_{1}a_{1}) + ∑_{i=0}^{d_{1}−1} r(a_{2}, a_{3}; j_{0} − ia_{i}).

Clearly r(j_{0} − L) = r(j_{0} − d_{1}a_{1}) ∈ {0, 1} and is zero if and only if any one of the terms of the sum is nonzero. But taking i = d_{1} − 1, we have

r(a_{2}, a_{3}; j_{0} − (d_{1} − 1)a_{i}) = r(a_{2}, a_{3}; (d_{2} − 1)a_{2} + (d_{3} − 1)a_{3}) > 0.

Third proof: Let us recall the following formula, due to Johnson [4]:

Lemma 7.3. For any primitive system (a_{1}, a_{2}, a_{3}), one has

𝔣(a_{1}, a_{2}, a_{3}) = d_{3}𝔣(\frac{a_{1}}{d_{3}} , \frac{a_{2}}{d_{3}} , a_{3}) + (d_{3} − 1)a_{3}.  (11)

Proof. Let 𝔣 = 𝔣(a_{1}, a_{2}, a_{3}). By lemma 7.2, we have 𝔣 ≡ −a_{3} (mod d_{3}). For any number N satisfying N ≡ −a_{3} (mod d_{3}), in any representation of N as x_{1}a_{1} +x_{2}a_{2} +x_{3}a_{3} we must have x_{3} ≡ −1 (mod d_{3}), hence N is representable by a_{1}, a_{2} and a_{3} if and only if N − (d_{3} − 1)a_{3} is representable by a_{1}, a_{2} and d_{3}a_{3}. This is equivalent to (N −(d_{3}−1)a_{3})/d_{3} being representable by \frac{a_{1}}{d_{3}} , \frac{a_{2}}{d_{3}} and a_{3}, whence the result.

This leads to an explicit formula for 𝔣 whenever a_{1} = d_{2}d_{3}:^{3}

𝔣(d_{2}d_{3}, a_{2}, a_{3}) = d_{3}𝔣(d_{2}, \frac{a_{2}}{d_{3}} , a_{3}) + (d_{3} − 1)a_{3} = d_{3}𝔣(d_{2}, \frac{a_{2}}{d_{3}} ) + (d_{3} − 1)a_{3} =

3This holds in particular for the “McNuggets” system (6, 9, 20), and so can be used to answer the brainteaser.

d_{2}a_{2} − d_{2}d_{3} − a_{2} + d_{3}a_{3} − a_{3} = a_{2}d_{2} + a_{3}d_{3} − a_{1} − a_{2} − a_{3},

where the second equality uses the fact that, since the weight a_{3} is a multiple of the weight d_{2}, it can be omitted without changing the Frobenius number.

Finally, Proposition 7.1 is a consequence of the following beautiful result of Alfred Brauer [2].

Theorem 7.4. Given a primitive set of weights (a_{1}, …, a_{k}), for 1 ≤ i ≤ k let e_{i} = gcd(a_{1}, …, a_{i}). Then

(a) 𝔣(a_{1}, …, a_{k}) ≤ ∑_{i=2}^{k} a_{i} \frac{e_{i−1}}{e_{i}} − ∑_{i=1}^{k} a_{i} + 1.

(b) One has equality in part (a) if and only if, for all i ≥ 2, \frac{e_{i−1}}{e_{i}} a_{i} can be represented by the system (a_{1}, …, a_{i}).

There is an analogue of Proposition 7.1 for arbitrary k ≥ 2: let d_{1}, …, d_{k} be a set of pairwise coprime positive integers, define D = ∏_{j} d_{j}, and for 1 ≤ i ≤ k put a_{i} = \frac{D}{d_{i}}. Then we say (a_{1}, …, a_{k}) is an extremal system of weights.

Proposition 7.5. Let (a_{1}, …, a_{k}) be the extremal system formed from the pairwise coprime system (d_{1}, …, d_{k}). Then:

𝔣(a_{1}, …, a_{k}) = (k − 1)(d_{1} ⋯ d_{k}) − ∑_{i=1}^{k} a_{i}.  (12)

The result is again a consequence of Brauer’s Theorem 7.4. We leave to the interested reader the task of investigating which of the other proofs of Proposition 7.1 can be made to go through.

We end with an explanation of the term “extremal.” For this, let r : ℕ → ℂ be any function given by a quasipolynomial mod L, of total degree at most d, and which is not identically zero on any residue class. Then we can define 𝔣(r) as the largest N for which r(N) = 0. Indeed, since r can have at most d zeros on any given residue class, we have 𝔣(r) ≤ dL − 1. By Theorem 2.1, we can apply this to any primitive system of weights (a_{1}, …, a_{k}), getting the bound

𝔣(a_{1}, …, a_{k}) ≤ (k − 1)L − 1.

In fact this bound is never sharp, as can be seen by comparing to Brauer’s bound. This is not so surprising, since the quasipolynomial associated with a set of weights has many special properties.

Notice however that this bound differs from the right hand side of (12) by precisely a_{1} + … + a_{k} − 1. This can be explained as follows: for a primitive system (a_{1}, …, a_{k}), define 𝔣^{+}(a_{1}, …, a_{k}) to be the largest positive integer N such that the equation x_{1}a_{1}+…+x_{k}a_{k} = N has no solution in positive integers x_{i}. This is closely related to the Frobenius number defined above; indeed, we have

𝔣^{+}(a_{1}, …, a_{k}) = 𝔣(a_{1}, …, a_{k}) + a_{1} + … + a_{k}.

Moreover, we can define

r^{+}(a_{1}, …, a_{k}; N) = #{(x_{1}, …, x_{k}) ∈ (ℤ^{+})^{k} | x_{1}a_{1} + … + x_{k}a_{k} = N}.

The associated generating function R^{+}(x) is easily computed:

∑_{n≥0} r^{+}(n)x^{n} = (x^{a_{1}} + x^{2a_{1}} + …) ⋯ (x^{a_{k}} + x^{2a_{k}} + …) = \frac{x^{a_{1}+...+a_{k}}}{(1 − x^{a_{1}}) ⋯ (1 − x^{a_{k}})}.

This is very nearly the generating function of a quasipolynomial: the only problem is that the degree of the numerator is equal to the degree of the denominator. Thus

x^{−1}R^{+}(x) = ∑_{n≥0} a_{n+1}x^{n}

is a quasipolynomial, so that r^{+}(n) is a quasipolynomial modulo L when restricted to positive integral values, of degree k − 1 on each residue class. From this information alone we deduce as above the bound

𝔣^{+}(a_{1}, …, a_{k}) ≤ (k − 1)L

and thus the bound

𝔣(a_{1}, …, a_{k}) ≤ (k − 1)L − ∑_{i=1}^{k} a_{i}.

It is remarkable that this bound is attained, by all extremal systems. Comparing with Brauer’s bound, it is easily seen that the bound is only attained for extremal systems, whence the name.

References

[1] M. Beck, I. Gessel and T. Komatsu, The polynomial part of a restricted partition function related to the Frobenius problem, Electronic J. Comb. 8 (2001), N7.

[2] A. Brauer, On a problem of partitions, Amer. J. Math. 64 (1942), 299–312.

[3] P. Erdos and J. Suranyi, Topics in the theory of numbers , Springer, 2003.

[4] S. M. Johnson, A linear diophantine problem, Canad. J. Math. 12 (1960), 390–398.

[5] R. Kannan, Lattice translates of a polytope and the Frobenius problem, Combinatorica 12 (1992), 161–177.

[6] A. Nijenhuis and H. Wilf, Representations of integers by linear forms in non-negative integers, J. Number Theory 4 (1972), 98–106.

[7] T. Popoviciu, Asupra unei probleme de patitie a numerelor, Acad. Republicii Populare Romane, Filiala Cluj, Studii si cercetari stiintifice 4 (1953), 7–58.

[8] J. L. Ramirez-Alfonsin, Complexity of the Frobenius problem, Combinatorica 16 (1996), 143–147.

[9] S. Sertoz, On the number of solutions of the Diophantine equation of Frobenius, Diskret. Mat. 10 (1998), 62–71.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 52C07. Keywords: Frobenius problem, quasi-polynomial, representation numbers, Pick’s theorem.

Received June 23 2005; revised version received October 19 2005. Published in Journal of Integer Sequences, October 20 2005.

Return to Journal of Integer Sequences home page.