%I #40 Dec 13 2021 16:13:11

%S 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,

%T 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,

%U 5,9,1,12,1,3,9,5,5,9,1,9,7,3,1,13,5,3,5,7,1,15,5,5

%N 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.

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

%C 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.

%C 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.

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

%H Antti Karttunen, <a href="/A337566/b337566.txt">Table of n, a(n) for n = 1..20000</a>

%H British Mathematical Olympiad 1977, <a href="https://bmos.ukmt.org.uk/home/bmo-1977.pdf">Problem 6</a>.

%H <a href="/index/O#Olympiads">Index to sequences related to Olympiads</a>.

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

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

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

%e For n = 3, the only solution, that corresponds to q = 2 and k = 2, is:

%e 3 * (x + x^2) = (x + 2x^2) + (2x + x^2).

%e For n = 26 as in the British Olympiad problem, a(26) = 3, and these three possible decompositions are:

%e for k = 2, q = 25:

%e 26 * (x + x^2 + x^3 + ... + x^24 + x^25) =

%e (x + 2x^2 + 3x^3 + ... + 24x^24 + 25x^25) +

%e (25x + 24x^2 + 23x^3 + ... + 2x^24 + x^25);

%e for k = 4, q = 12:

%e 26 * (x + x^2 + x^3 + ... + x^11 + x^12) =

%e (x + 2x^2 + 3x^3 + ... + 11x^11 + 12x^12) +

%e (12x + 11x^2 + 10x^3 + ... + 2x^11 + x^12) +

%e (x + 2x^2 + 3x^3 + ... + 11x^11 + 12x^12) +

%e (12x + 11x^2 + 10x^3 + ... + 2x^11 + x^12);

%e for k = 13, q = 3:

%e 26 * (x + x^2 + x^3) =

%e 4 * (x + 2x^2 + 3x^3) +

%e 4 * (2x + 3x^2 + x^3) +

%e 3 * (3x + x^2 + 2x^3) +

%e (2x + x^2 + 3x^3) +

%e (3x + 2x^2 + x^3).

%p with(numtheory):

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

%t MapAt[# + 1 &, Array[DivisorSigma[0, 2 #] - 3 &, 92], 1] (* _Michael De Vlieger_, Dec 12 2021 *)

%o (PARI) a(n) = if (n==1, 0, numdiv(2*n)-3); \\ _Michel Marcus_, Sep 06 2020

%Y Cf. A065091, A099777.

%K nonn

%O 1,6

%A _Bernard Schott_, Sep 01 2020