A387389 - OEIS

%I #19 Sep 03 2025 23:51:03

%S 6,22,32,28,40,38,36,52,50,48,46,66,64,64,62,62,60,58,56,80,80,78,78,

%T 76,78,76,74,74,72,72,70,70,68,96,66,96,94,96,92,94,92,92,90,92,90,88,

%U 88,90,86,88,86,86,84,84,84,82,82,82,80,80,110,78,112,114

%N 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.

%C 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".

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

%H Jesús Bellver Arnau, <a href="/A387389/b387389.txt">Table of n, a(n) for n = 1..100</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_problem">Partition problem</a>.

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

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

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

%o (Python)

%o def partitions_distinct(n):

%o     def _build(remaining, max_next):

%o         if remaining == 0:

%o             return [[]]

%o         res = []

%o         for k in range(min(remaining, max_next), 0, -1):

%o             for tail in _build(remaining - k, k - 1):

%o                 res.append([k] + tail)

%o         return res

%o     return _build(n, n//2) # The biggest number in the subset can't be bigger than n/2

%o def count_half_subsets(partition, n):

%o     if n % 2:

%o         return 0

%o     half = n // 2

%o     dp = [0] * (half + 1)

%o     dp[0] = 1

%o     for x in partition:

%o         for s in range(half, x - 1, -1):

%o             dp[s] += dp[s - x]

%o     return int(dp[half]/2) #-> to not count {X}={Y} and {Y}={X} as two different solutions

%o #---- Generate Sequence -----

%o max_n = 15 #number of terms

%o sequence = []

%o for n in range(1, max_n):

%o     p_N_exists = False

%o     N=1

%o     while p_N_exists==False:

%o         partes = partitions_distinct(2*N)

%o         for p in partes:

%o             subsets = count_half_subsets(p, 2*N)

%o             if subsets == n:

%o                 sequence.append(2*N)

%o                 p_N_exists = True

%o                 break

%o         N = N+1

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

%K nonn

%O 1,1

%A _Jesús Bellver Arnau_, Aug 28 2025