A337566 a(n) is the number of possible decompositions of the polynomial n * (x + x^2 + ... + x^q), where q > 1, into a sum of k polynomials, not necessarily all different; each of these polynomials is to be of the form b_1 * x + b_2 * x^2 + ... + b_q * x^q where each b_i is one of the numbers 1, 2, 3, ..., q and no two b_i are equal.

0, 0, 1, 1, 1, 3, 1, 2, 3, 3, 1, 5, 1, 3, 5, 3, 1, 6, 1, 5, 5, 3, 1, 7, 3, 3, 5, 5, 1, 9, 1, 4, 5, 3, 5, 9, 1, 3, 5, 7, 1, 9, 1, 5, 9, 3, 1, 9, 3, 6, 5, 5, 1, 9, 5, 7, 5, 3, 1, 13, 1, 3, 9, 5, 5, 9, 1, 5, 5, 9, 1, 12, 1, 3, 9, 5, 5, 9, 1, 9, 7, 3, 1, 13, 5, 3, 5, 7, 1, 15, 5, 5

Offset: 1

Author

Bernard Schott, Sep 01 2020

Keywords

• nonn

Comments

Inspired by the 6th problem of the 13th British Mathematical Olympiad in 1977 (see the link BMO) where the problem asked to find for n = 26 all the values of q for which this decomposition is possible (see 2nd example).

As mentioned by Tony Gardiner in his book (see reference), "the wording" of this problem "is very strange". Letter n in Olympiad exercise becomes q in the Name.

If a solution is the sum of k polynomials of degree q, then, the relation between (n,k,q) is: k*(q+1) = 2*n with q > 1 (as in the problem) and q < n (because one proves there is no solution when q >= n); then, a(n) is the number of pairs (k,q) that are solutions of this last relation.

Examples

			For n = 3, the only solution, that corresponds to q = 2 and k = 2, is:
    3 * (x + x^2) = (x + 2x^2) + (2x + x^2).
For n = 26 as in the British Olympiad problem, a(26) = 3, and these three possible decompositions are:
   for k = 2, q = 25:
     26 * (x +   x^2 +   x^3 + ... +   x^24 +   x^25) =
          (x +  2x^2 +  3x^3 + ... + 24x^24 + 25x^25) +
        (25x + 24x^2 + 23x^3 + ... +  2x^24 +   x^25);
   for k = 4, q = 12:
     26 * (x +   x^2 +   x^3 + ... +   x^11 +   x^12) =
          (x +  2x^2 +  3x^3 + ... + 11x^11 + 12x^12) +
        (12x + 11x^2 + 10x^3 + ... +  2x^11 +   x^12) +
          (x +  2x^2 +  3x^3 + ... + 11x^11 + 12x^12) +
        (12x + 11x^2 + 10x^3 + ... +  2x^11 +   x^12);
   for  k = 13, q = 3:
      26 *  (x +  x^2 +  x^3) =
       4 *  (x + 2x^2 + 3x^3) +
       4 * (2x + 3x^2 +  x^3) +
       3 * (3x +  x^2 + 2x^3) +
           (2x +  x^2 + 3x^3) +
           (3x + 2x^2 +  x^3).
		

References

• A. Gardiner, The Mathematical Olympiad Handbook: An Introduction to Problem Solving, Oxford University Press, 1997, reprinted 2011, Problem 6 pp. 212-213 (1977).

Links

• Antti Karttunen, Table of n, a(n) for n = 1..20000
• British Mathematical Olympiad 1977, Problem 6.
• Index to sequences related to Olympiads.

Crossrefs

Cf. A065091, A099777.

Programs

Maple

with(numtheory):
Data:= 0, seq(tau(2*n)-3, n=2..150);

Mathematica

MapAt[# + 1 &, Array[DivisorSigma[0, 2 #] - 3 &, 92], 1] (* Michael De Vlieger, Dec 12 2021 *)

PARI

a(n) = if (n==1, 0, numdiv(2*n)-3); \\ Michel Marcus, Sep 06 2020

Formula

a(1) = 0 then, for n >= 2, a(n) = tau(2n) - 3 = A099777(n) - 3.

a(n) = 1 iff n = 4 or n = p odd prime (A065091).

a(n) = p-3, p odd prime > 3 iff n = 2^(p-2).