""" This program calculates smallest subset of {0, 1,...,n} such that for any element in [n] we can find 2 distinct elements that add to it """ import math def check(Set, desired_val): #check if a Set of values can be pairwise added to hit all the elements in desired_val copy = set() for i in desired_val: copy.add(i) for i in range(len(Set)): if(2*Set[i] > len(desired_val)): break for j in range(i, len(Set)): if(Set[i] + Set[j] > len(desired_val)): break copy.discard(Set[i] + Set[j]) if(len(copy)==0): return True return False def optimize(available_val, desired_val, Set, max_num, final_set): #iterates through via backtracking all the possible Sets (subsets of available_val) of size max_num if (len(Set) == max_num): if(check(Set, desired_val) and len(final_set)== 0): for i in Set: final_set.append(i) #final_set is the first found desired set else: for i in range(len(available_val)): if(len(final_set) > 0): #if final_set is found, break out of loop break Set.append(available_val[i]) optimize(available_val[i+1:], desired_val, Set, max_num, final_set) Set.pop() def minimize(available_val, desired_val): #finds minimal length of desired subset starting with considering max_num at 1 and going up until a desired subset is found final_set = [] n = len(available_val) i = math.ceil(((1+8*n)**.5-1)/2) while(len(final_set)==0): optimize(available_val, desired_val, [], i, final_set) i=i+1 return final_set def count_minimum_helper(available_val, desired_val, Set, max_num, final_count): #Number of sets S of size A066063(n) such that {1, 2, ..., n} is a subset of S + S if (len(Set) == max_num): if(check(Set, desired_val)): final_count.append(0) else: for i in range(len(available_val)): Set.append(available_val[i]) count_minimum_helper(available_val[i+1:], desired_val, Set, max_num, final_count) Set.pop() def count_minimum(n): #Number of sets S of size A066063(n) such that {1, 2, ..., n} is a subset of S + S available_val = list(range(n+1)) desired_val = list(range(1, n+1)) final_set = [] i = len(minimize(available_val, desired_val)) count_minimum_helper(available_val, desired_val, [], i, final_set) return len(final_set) #run count_minimum to get the number of sets S of size A066063(n) such that {1, 2, ..., n} is a subset of S + S #Example for n = 3: print(count_minimum(3))