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

Author

Jesús Bellver Arnau, Aug 28 2025

Keywords

• nonn
• new

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.

Examples

			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.
		

Links

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

Crossrefs

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

Programs

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