A395941 - OEIS

%I #13 May 18 2026 21:57:11

%S 1,0,1,2,3,15,28,150,301,567,1012,5957,11194,67220,131110,246180,

%T 446634,2790246,5228831,32849241,63172839,118285288,216048937,

%U 1389019151,2597508627,4752887314,8521006425,14986211764,25885275427,172796271571,305289220115,2029750359569

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

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

%e a(1) = 0 since 1 has no partitions into prime parts.

%e a(2) = 1 since 4 = (2 + 2).

%e a(3) = 2 since 9 = (2 + 2 + 2 + 3) or (3 + 3 + 3).

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

%o (Python)

%o from sympy import primerange

%o def a(n):

%o     # Count partitions of n^2 into prime parts not exceeding n.

%o     # b[k] stores the number of ways to make total k using the prime parts processed so far.

%o     # Processing one prime at a time ensures that order is ignored, so 2+2+3 and 2+3+2 are not counted separately.

%o     s=n*n; b=[1]+[0]*s

%o     for p in primerange(n+1):

%o         for k in range(p,s+1): b[k]+=b[k-p]

%o     return b[s]

%o print([a(n) for n in range(32)])

%Y Cf. A000607, A394668, A395942, A395943.

%K nonn

%O 0,4

%A _Chuck Seggelin_, May 11 2026