A387389 a(n) is the smallest positive integer for which there exists a strict partition that can be partitioned into two disjoint subsets with equal sum in n ways.

6, 22, 32, 28, 40, 38, 36, 52, 50, 48, 46, 66, 64, 64, 62, 62, 60, 58, 56, 80, 80, 78, 78, 76, 78, 76, 74, 74, 72, 72, 70, 70, 68, 96, 66, 96, 94, 96, 92, 94, 92, 92, 90, 92, 90, 88, 88, 90, 86, 88, 86, 86, 84, 84, 84, 82, 82, 82, 80, 80, 110, 78, 112, 114

Offset

1,1

Comments

Finding ways in which a set can be partitioned into two disjoint subsets with equal sum is often referred to as the "partition search problem".

All the numbers in the sequence are even because for odd numbers there is no solution to the partition search problem.

Links

Jesús Bellver Arnau, Table of n, a(n) for n = 1..100

Wikipedia, Partition problem.

Example

a(1) = 6, because S={3,2,1} is a strict partition of 6 and there is a way to partition S into two disjoint subsets of equal sum: {3}={2,1}. It is not possible to do this for any strict partition of integers smaller than 6.
a(2) = 22, because S={7, 5, 4, 3, 2, 1} is a strict partition of 22 and there are two ways to partition S into two disjoint subsets of equal sum: {7,4}={5,3,2,1} and {7,3,1}={5,4,2}. There are no strict partitions of any smaller number for which this can be done.
a(3) = 32, because S={11, 6, 5, 4, 3, 2, 1} is a strict partition of 32 and there are three ways to partition S into two disjoint subsets of equal sum: {11,5}={6,4,3,2,1}, {11,4,1}={6,5,3,2} and {11,3,2}={6,5,4,1}. There are no strict partitions of any smaller number for which this can be done.

Prog

(Python)
def partitions_distinct(n):
    def _build(remaining, max_next):
        if remaining == 0:
            return [[]]
        res = []
        for k in range(min(remaining, max_next), 0, -1):
            for tail in _build(remaining - k, k - 1):
                res.append([k] + tail)
        return res
    return _build(n, n//2) # The biggest number in the subset can't be bigger than n/2
def count_half_subsets(partition, n):
    if n % 2:
        return 0
    half = n // 2
    dp = [0] * (half + 1)
    dp[0] = 1
    for x in partition:
        for s in range(half, x - 1, -1):
            dp[s] += dp[s - x]
    return int(dp[half]/2) #-> to not count {X}={Y} and {Y}={X} as two different solutions
#---- Generate Sequence -----
max_n = 15 #number of terms
sequence = []
for n in range(1, max_n):
    p_N_exists = False
    N=1
    while p_N_exists==False:
        partes = partitions_distinct(2*N)
        for p in partes:
            subsets = count_half_subsets(p, 2*N)
            if subsets == n:
                sequence.append(2*N)
                p_N_exists = True
                break
        N = N+1

Crossrefs

Cf. A000009, A387388, A083206, A237258, A321452, A305551, A371791.

Sequence in context: A276795 A037204 A296981 * A035285 A069824 A015709

Adjacent sequences: A387386 A387387 A387388 * A387390 A387391 A387392

Keyword

nonn

Author

Jesús Bellver Arnau, Aug 28 2025

Status

approved