Find the smallest set of non-negative integers such that all non-negative integers up to n can be represented as a sum of two elements; see https://math.stackexchange.com/questions/2835313.

Question2835313.java

public class Question2835313 {
	public static void main (String [] args) {
		int min = 1;
		int binom = 1;
		int [] set = {};
		int l = 2;
		
		for (int n = 2;n <= 100;n++) {
			if (binom <= n) {
				min++;
				binom = (min * (min + 1)) / 2;
				if (binom <= n)
					throw new InternalError ();
			}
			int s = (int) Math.sqrt (n + 4);
			int r = n + 4 - s * s;
			int delta = s & 1;
			int max = ((int) Math.ceil ((r + delta) / (double) (s + delta)) + 2 * s - 3);

			if (!generates (set,n)) {
				for (l = Math.max (l,min);l <= max;l++) {
					set = new int [l];
					int [] coveringCounts = new int [n + 1];
					coveringCounts [0] = 1;
					coveringCounts [1] = 2;
					coveringCounts [2] = 1;
					set [1] = 1;
					if (recurse (set,coveringCounts,3,2,l,n,n / 2 + 2))
						break;
					long start = System.currentTimeMillis ();
					try {
						System.out.println ("trying " + n);
						if (recurse (set,coveringCounts,3,2,l,n,n))
							break;
					}
					finally {
						long stop = System.currentTimeMillis ();
						System.out.println ("time: " + n + " : " + (stop - start) / 1000);
					}
				}
			}
			System.out.print (n + "&" + min + "&" + max + "&" + set.length + "&\\{");
			for (int i : set) {
				if (i != 0)
					System.out.print (',');
				System.out.print (i);
			}
			System.out.println ("\\}\\\\");
		}
	}
	
	static boolean generates (int [] set,int n) {
		int nuncovered = n + 1;
		boolean [] covered = new boolean [nuncovered];
		for (int i : set)
			for (int j : set) {
				int sum = i + j;
				if (sum <= n && !covered [sum]) {
					if (--nuncovered == 0)
						return true;
					covered [sum] = true;
				}
			}
		return false;
	}
	
	static boolean recurse (int [] set,int [] coveringCounts,int ncovered,int index,int l,int n,int max) {
		if (index == l)
			return ncovered == n + 1;

		if ((l * (l + 1)) / 2 - (index * (index + 1)) / 2 > n - ncovered)
			for (set [index] = set [index - 1] + 1;set [index] <= max - l + index + 1;set [index]++) {
				for (int i = 0;i <= index;i++) {
					int sum = set [i] + set [index];
					if (sum <= n) {
						if (coveringCounts [sum] == 0)
							ncovered++;
						coveringCounts [sum]++;
					}
				}
				if (recurse (set,coveringCounts,ncovered,index + 1,l,n,max))
					return true;
				for (int i = 0;i <= index;i++) {
					int sum = set [i] + set [index];
					if (sum <= n) {
						coveringCounts [sum]--;
						if (coveringCounts [sum] == 0)
							ncovered--;
					}
				}
			}
		return false;
	}
}