Brutish force for MO501100

MO501100.py

#!/usr/bin/pypy3

def vecs(n, width):
	# width should be chosen so 2^width > n.
	if n == 0:
		yield 0
		return

	for hd in vecs(n-1, width):
		yield hd << width
		yield (hd << width) + 1


def search(n):
	vs = list(vecs(n, n.bit_length()))
	best = []
	def inner(i, inc, sums):
		# i: index reached in vs
		# inc: included vectors
		# sums: set of pairwise sums
		nonlocal best
		if i == len(vs):
			if len(inc) > len(best):
				best = inc
				print("  * lb ", len(best), best)
			return

		# Optimisation
		if len(inc) + len(vs) - i < len(best):
			# Can't improve
			return

		v = vs[i]
		new_sums = set([v + v] + [v + prev for prev in inc])
		if len(new_sums) == len(inc) + 1 and len(sums & new_sums) == 0:
			inner(i+1, inc + [v], sums | new_sums)

		inner(i+1, inc, sums)


	inner(0, [], set())
	return len(best), best


from time import perf_counter
for n in range(1, 7):
	start = perf_counter()
	print(n, search(n), "in", perf_counter() - start)