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,6

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.

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.

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).

Example

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).

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 *)

Prog

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

Crossrefs

Cf. A065091, A099777.

Sequence in context: A327239 A322849 A322850 * A106601 A325533 A110030

Adjacent sequences: A337563 A337564 A337565 * A337567 A337568 A337569

Keyword

nonn

Author

Bernard Schott, Sep 01 2020

Status

approved