A369786 Number of different coefficient values in expansion of Product_{k=1..n} (1+x^(k^2)).

1, 1, 2, 2, 2, 3, 3, 4, 6, 7, 10, 15, 21, 33, 50, 83, 126, 208, 321, 498, 688, 934, 1208, 1496, 1798, 2140, 2482, 2862, 3268, 3690, 4145, 4619, 5142, 5687, 6265, 6880, 7530, 8214, 8937, 9700, 10489, 11339, 12218, 13142, 14112, 15123, 16181, 17288, 18438, 19639, 20888

Offset: 0

Author

Seiichi Manyama, Feb 01 2024

Keywords

• nonn

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..500

Crossrefs

Cf. A033461, A039822.

Programs

Mathematica

p = 1; Join[{1}, Table[p = Expand[p*(1 + x^(n^2))]; Length[Union[CoefficientList[p, x]]], {n, 1, 50}]] (* or *)
nmax = 50; poly = ConstantArray[0, nmax*(nmax + 1)*(2*nmax + 1)/6 + 1]; poly[[1]] = 1; poly[[2]] = 1; Flatten[{{1, 1}, Table[Do[poly[[j + 1]] += poly[[j - k^2 + 1]], {j, k*(k + 1)*(2*k + 1)/6, k^2, -1}]; Length[Union[poly]], {k, 2, nmax}]}] (* Vaclav Kotesovec, Feb 01 2024 *)

PARI

a(n) = #Set(Vec(prod(k=1, n, 1+x^k^2)));

Python

from collections import Counter
def A369786(n):
    c = {0:1}
    for k in range(1,n+1):
        m, d = k**2, Counter(c)
        for j in c:
            d[j+m] += c[j]
        c = d
    return len(set(c.values()))+int(max(c)+1>len(c)) # Chai Wah Wu, Feb 01 2024

Formula

Conjecture: a(n) ~ n^3/6. - Vaclav Kotesovec, Feb 02 2024