A395941 Number of partitions of n^2 into prime parts not exceeding n.

1, 0, 1, 2, 3, 15, 28, 150, 301, 567, 1012, 5957, 11194, 67220, 131110, 246180, 446634, 2790246, 5228831, 32849241, 63172839, 118285288, 216048937, 1389019151, 2597508627, 4752887314, 8521006425, 14986211764, 25885275427, 172796271571, 305289220115, 2029750359569

Offset

0,4

Comments

This is a restricted version of A000607(n^2), allowing only prime parts p <= n.

Links

Table of n, a(n) for n=0..31.

Example

a(1) = 0 since 1 has no partitions into prime parts.
a(2) = 1 since 4 = (2 + 2).
a(3) = 2 since 9 = (2 + 2 + 2 + 3) or (3 + 3 + 3).
a(4) = 3 since 16 = (2 + 2 + 2 + 2 + 2 + 2 + 2 + 2) or (2 + 2 + 2 + 2 + 2 + 3 + 3) or (2 + 2 + 3 + 3 + 3 + 3).

Prog

(Python)
from sympy import primerange
def a(n):
    # Count partitions of n^2 into prime parts not exceeding n.
    # b[k] stores the number of ways to make total k using the prime parts processed so far.
    # Processing one prime at a time ensures that order is ignored, so 2+2+3 and 2+3+2 are not counted separately.
    s=n*n; b=[1]+[0]*s
    for p in primerange(n+1):
        for k in range(p, s+1): b[k]+=b[k-p]
    return b[s]
print([a(n) for n in range(32)])

Crossrefs

Cf. A000607, A394668, A395942, A395943.

Sequence in context: A030072 A064219 A244377 * A244330 A378109 A342867

Adjacent sequences: A395938 A395939 A395940 * A395942 A395943 A395944

Keyword

nonn

Author

Chuck Seggelin, May 11 2026

Status

approved