[seqfan] Re: The weight puzzle sequence

[Richard Mathar]

http://list.seqfan.eu/pipermail/seqfan/2010-August/005802.html

coputed maximum set sizes of grams agree with the assumptions.
List generated with "n" followed by a maximum subset  as specified:

1, [1]
2, [1, 2]
3, [1, 2]
4, [1, 2, 4]
5, [1, 2, 4]
6, [1, 2, 4]
7, [3, 5, 6, 7]
8, [1, 2, 4, 8]
9, [1, 2, 4, 8]
10, [1, 2, 4, 8]
11, [1, 2, 4, 8]
12, [1, 2, 4, 8]
13, [3, 6, 11, 12, 13]
14, [1, 6, 10, 12, 14]
15, [1, 6, 10, 12, 14]
16, [1, 2, 4, 8, 16]

So the size-sequence starts 1,2,2,3,3,3,4,4,4,4,4,4,5,5,5,5

Independent confirmations certainly desired!

# Maple implementation:
# is any subset of L uniquely determined by the total weight?
iswts := proc(L)
	local wtset,s,c,subL,thiswt ;
	# the weight sums are to be unique, so sufficient to remember the set
	wtset := {} ;

	# loop over all subsets of weights generated by L
	for s from 1 to nops(L) do
		c := combinat[choose](L,s) ;
		for subL in c do
			# compute the weight sum in this subset
			thiswt := add(i,i=subL) ;
			# if this weight sum already appeared: not a candidate
			if thiswt in wtset then
				return false;
			else
				wtset := wtset union {thiswt} ;
			end if;
		end do:
	end do:
	# All different subset weights were different: success
	return true;
end proc:

# main sequence: given grams 1 to n, determine a subset L
# such that each subset of this subset as a different sum.
wts := proc(n)
	local s,c,L ;
	# select sizes from n (largest size first) down to 1,
	# so the largest is detected first.
	for s from n to 1 by -1 do
		# all combinations of subsets of s different grams
		c := combinat[choose]([seq(i,i=1..n)],s) ;
		for L in c do
			# check if any of these meets the requir, print if yes
			# and return
			if iswts(L) then
				print(n,L) ;
				return nops(L) ;
			end if;
		end do:
	end do:
	print(n,"-") ;
end proc:

# loop for weights with maximum n
for n from 1 do
	wts(n) ;
end do: