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
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.
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
Comments