A394927 a(n) is the minimal sum of squares over partitions of n into distinct parts.

0, 1, 4, 5, 10, 13, 14, 21, 26, 29, 30, 39, 46, 51, 54, 55, 66, 75, 82, 87, 90, 91, 104, 115, 124, 131, 136, 139, 140, 155, 168, 179, 188, 195, 200, 203, 204, 221, 236, 249, 260, 269, 276, 281, 284, 285, 304, 321, 336, 349, 360, 369, 376, 381, 384, 385, 406, 425

Offset

0,3

Comments

To construct the partition of n into distinct positive parts that minimizes the sum of squares: let k = A003056(n) and r = n - A000217(k); start with 1, 2, ..., k and increase the largest r parts by 1. Proof: Since x^2 is strictly convex, splitting a part x >= 2 into (x - 1, 1) lowers the sum of squares; thus the global minimum uses the maximal feasible number of parts, namely k = A003056(n). Now fix this k and write a1 < ... < ak with sum n. If a consecutive gap aj - ai (j = i + 1) is >= 3, replace (ai, aj) by (ai + 1, aj - 1); parts stay distinct and the sum of squares drops by (ai + 1)^2 + (aj - 1)^2 - (ai^2 + aj^2) = -2*(aj - ai - 1) < 0. Iterating leaves only gaps 1 or 2. Any 2-gap below a 1-gap can be bubbled upward by successive (x, y) -> (x + 1, y - 1) moves; each step preserves distinctness and strictly decreases the sum of squares, since (x + 1)^2 + (y - 1)^2 - (x^2 + y^2) = -2*(y - x - 1) < 0 for y >= x + 2; thus all 2-gaps end up at the top. Therefore the k-part minimizer is exactly 1, 2, ..., k with the largest r parts increased by 1.

a(n) has the same parity as n. Proof: Let k = A003056(n) and r = n - A000217(k). Then a(n) = A000330(k) + r(2*k + 2 - r) == A000217(k) + r (mod 2) since i^2 == i (mod 2) and 2*k + 2 == 0 (mod 2). Hence a(n) == A000217(k) + (n - A000217(k)) == n (mod 2).

a(n) is strictly increasing. Proof: Write k = A003056(n), r = n - A000217(k). Then a(n + 1) - a(n) = 2*k + 1 - 2*r for 0 <= r < k, and a(n + 1) - a(n) = 1 when r = k (since k increases to k + 1). In all cases the difference is >= 1, so a(n) is strictly increasing.

Links

Felix Huber, Table of n, a(n) for n = 0..10000

Formula

a(n) = A000330(k) + (n - A000217(k))(2*k + 2 - n + A000217(k)), where k = A003056(n).

Asymptotics: a(n) ~ (2*sqrt(2)/3)*n^(3/2).

Example

a(8) = 26. Here k = A003056(8) = 3 and r = 8 - A000217(3) = 2. Start with 1, 2, 3 and add 1 to the largest two parts -> 1, 3, 4; sum of squares = 1^2 + 3^2 + 4^2 = 26.
a(26) = 136. Here k = A003056(26) = 6 and r = 26 - A000217(6) = 5. Start with 1, 2, 3, 4, 5, 6 and add 1 to the largest five parts -> 1, 3, 4, 5, 6, 7; sum of squares = 1^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 = 136.

Maple

A394927 := n -> (k -> k*(k + 1)*(2*k + 1)/6 + (n - k*(k + 1)/2)*(2*k + 2 - n + k*(k + 1)/2))(floor((sqrt(8*n + 1) - 1)/2)): seq(A394927(n), n = 1 .. 26);

Crossrefs

Cf. A000009, A000217, A000330, A003056.

Sequence in context: A222353 A094415 A114517 * A383682 A283246 A236283

Adjacent sequences: A394924 A394925 A394926 * A394928 A394929 A394930

Keyword

nonn,easy

Author

Felix Huber, Apr 10 2026

Status

approved