Delete some bits and count Consider all 2^n different binary strings of length n and assume n &gt; 2.  You are allowed to delete exactly b &lt; n/2 bits from each of the binary strings, leaving strings of length n-b remaining. The number of distinct strings remaining depends on which bits you delete. Assuming your aim is to leave as few remaining different strings as possible, this challenge is to write code to compute how few can you leave as a function of n.

Example, n=3 and b = 1.  You can leave only the two strings 11 and 00.

For n=9 and b = 1,2,3,4 we have 70,18,6,2

For n=8 and b = 1,2,3 we have 40,10,4

For n=7 and b = 1,2,3 we have 20,6,2

For n=6 and b = 1,2 we have 12,4

For n=5 and b = 1,2 we have 6,2

This question was originally posed by me in 2014 in a different form on MO.

Input and output

Your code should take in an integern and output a single integer for each value of b starting at b = 0 and increasing.

Score

Your score is the largest n for which your code completes for all b &lt; n/2 in under a minute on my Linux based PC.  In case of tie breaks, the largest b your code gets to for the joint largest n wins. In case of tie breaks on that criterion too, the fastest code for the largest values of n and b decides. If the times are within a second or two of each other, the first posted answer wins.

Languages and libraries

You can use any language of library you like. Because I have to run your code, it would help if it was free (as in beer) and worked in Linux.
Python 2.7 / Gurobi n=9

This solution is very straight usage of Gurobi's ILP solver for the boolean Mixed-Integer Problems (MIP).

The only trick is to take out symmetry in 1's complement to halve the problem sizes.

Using Gurobi LLC's limited time "free" licence we are restricted to 2000 constraints, but solving 10 del 1 is well outside the 60 second time-limit anyway on my laptop.

from gurobipy import *
from itertools import combinations

def mincover(n,d):
    bs = pow(2,n-1-d)
    m = Model()
    m.Params.outputFlag = 0
    b = {}
    for i in range(bs):
      b[i] = m.addVar(vtype=GRB.BINARY, name="b%d" % i)
    m.update()
    for row in range(pow(2,n-1)):
      x = {}
      for i in combinations(range(n), n-d):
        v = 0
        for j in range(n-d):
          if row &amp; pow(2,i[j]):
            v += pow(2,j)
        if v &gt;= bs:
          v = 2*bs-1-v
        x[v] = 1
      m.addConstr(quicksum(b[i] for i in x.keys()) &gt;= 1)
    m.setObjective(quicksum(b[i] for i in range(bs) ), GRB.MINIMIZE)
    m.optimize()
    return int(round(2*m.objVal,0))

for n in range(4,10):
    for d in range((n//2)+1):
        print n, d, mincover(n,d)


UPDATE+CORR: 10,2 has optimal solution size 31 (see e.g.) Gurobi shows no symmetric solution of size 30 exists (returns problem infeasible) .. [my attempt to show asymmetric feasibility at 30 remained inconclusive after 9.5hrs runtime]
e.g. bit patterns of integers 0 7 13 14    25 28 35 36 49 56 63 64 95 106 118 128 147 159 170 182 195 196 200 207 225 231 240 243 249 252 255 or 0 7 13 14 19 25 28 35 36 49 56 63 64 95 106 118 128     159 170 182 195 196 200 207 225 231 240 243 249 252 255