By Warren D. Smith 1 Oct 2006
Puzzle: Let the set {0,1,2,...,N-1} be covered by sums of exactly 2 elements (not necessarily distinct) of a subset Q containing q elements. For each N: what is the minimal q?
Example: N=9, q=4, set={0,1,3,4} means {0,1,2,...,8} is covered thus by pair-sums: 0=0+0, 1=0+1, 2=1+1, 3=0+3, 4=0+4=1+3, 5=1+4, 6=3+3, 7=3+4, 8=4+4 and the cardinality q=4 is minimal since (by the pigeonhole principle) no 3-element subset of {0,1,2,...,8} can work.
| N | q | set |
|---|---|---|
| 3 | 2 | 0,1 |
| 4 | 3 | 0,1,2 |
| 5 | 3 | 0,1,2 |
| 6 | 4 | 0,1,2,3 |
| 7 | 4 | 0,1,2,3 |
| 8 | 4 | 0,1,3,4 |
| 9 | 4 | 0,1,3,4 |
| 10 | 5 | 0,1,2,4,5 |
| 11 | 5 | 0,1,2,4,5 |
| 12 | 5 | 0,1,3,5,6 |
| 13 | 5 | 0,1,3,5,6 |
| 14 | 6 | 0,1,2,4,6,7 |
| 15 | 6 | 0,1,2,4,6,7 |
| 16 | 6 | 0,1,3,5,7,8 |
| 17 | 6 | 0,1,3,5,7,8 |
| 18 | 7 | 0,1,2,4,6,8,9 |
| 19 | 7 | 0,1,2,4,6,8,9 |
| 20 | 7 | 0,1,3,5,7,9,10 |
| 21 | 7 | 0,1,3,5,7,9,10 |
| 22 | 8 | 0,1,2,4,6,8,10,11 |
| 23 | 8 | 0,1,2,4,6,8,10,11 |
| 24 | 8 | 0,1,3,5,7,9,11,12 |
| 25 | 8 | 0,1,3,5,7,9,11,12 |
| 26 | 8 | 0,1,3,4,9,10,12,13 |
| 27 | 8 | 0,1,3,4,9,10,12,13 |
| 28 | 9 | 0,1,3,5,7,9,11,13,14 |
| 29 | 9 | 0,1,3,5,7,9,11,13,14 |
| 30 | 9 | 0,1,3,4,9,10,12,14,15 |
| 31 | 9 | 0,1,3,4,9,10,12,14,15 |
| 32 | 9 | 0,1,2,5,8,11,14,15,16 |
| 33 | 9 | 0,1,2,5,8,11,14,15,16 |
| 34 | 10 | 0,1,3,4,9,10,12,14,16,17 |
| 35 | 10 | 0,1,3,4,9,10,12,14,16,17 |
| 36 | 10 | 0,1,3,5,6,12,13,15,17,18 |
| 37 | 10 | 0,1,3,5,6,12,13,15,17,18 |
| 38 | 10 | 0,1,3,5,6,13,14,16,18,19 |
| 39 | 10 | 0,1,3,5,6,13,14,16,18,19 |
| 40 | 10 | 0,1,3,4,9,11,16,17,19,20 |
| 41 | 10 | 0,1,3,4,9,11,16,17,19,20 |
| 42 | 11 | 0,1,3,5,6,13,14,16,18,20,21 |
| 43 | 11 | 0,1,3,5,6,13,14,16,18,20,21 |
| 44 | 11 | 0,1,3,4,6,11,13,18,19,21,22 |
| 45 | 11 | 0,1,3,4,6,11,13,18,19,21,22 |
| 46 | 11 | 0,1,2,3,7,11,15,19,21,22,24 |
| 47 | 11 | 0,1,2,3,7,11,15,19,21,22,24 |
| 48 | 12 | 0,1,3,5,7,8,16,17,19,21,23,24 |
| 49 | 12 | 0,1,3,5,7,8,16,17,19,21,23,24 |
| 50 | 12 | 0,1,3,5,7,8,17,18,20,22,24,25 |
| 51 | 12 | 0,1,3,5,7,8,17,18,20,22,24,25 |
| 52 | 12 | 0,1,3,5,6,12,13,20,21,23,25,26 |
| 53 | 12 | 0,1,3,5,6,12,13,20,21,23,25,26 |
| 54 | 12 | 0,1,3,5,6,13,14,21,22,24,26,27 |
| 55 | 12 | 0,1,3,5,6,13,14,21,22,24,26,27 |
| 56 | 13 | 0,1,3,4,8,9,11,20,21,23,25,27,28 |
| 57 | 13 | 0,1,3,4,8,9,11,20,21,23,25,27,28 |
| 58 | 13 | 0,1,3,5,6,13,14,21,22,24,26,28,29 |
| 59 | 13 | 0,1,3,5,6,13,14,21,22,24,26,28,29 |
| 60 | 13 | 0,1,3,5,6,13,15,17,24,25,27,29,30 |
| 61 | 13 | 0,1,3,5,6,13,15,17,24,25,27,29,30 |
| 62 | 13 | 0,2,3,5,9,13,17,21,25,26,28,30,31 |
| 63 | 13 | 0,1,2,3,7,11,15,19,23,27,29,30,32 |
| 64 | 13 | 0,1,3,4,9,11,16,21,23,28,29,31,32 |
| 65 | 13 | 0,1,3,4,9,11,16,21,23,28,29,31,32 |
The sequence 3, 5, 9, 13, 17, 21, 27, 33, 41, 47, 55, ... does not match anything previously in the Online Encyclopedia of Integer Sequences. Note the N=46, N=47 and N=63 lines in the table above, which are the first known examples where it is necessary for Q-cardinality-minimality that Q include a number greater than N/2 (shown blue).
Asymptotics: We can easily bound N(q) between two quadratics:
A least-squares fit of a quadratic in q=2,3,4,...,12 to the data N=3,5,9,...,55 yields N = 0.291*q2 + 1.139*q - 0.527 approximately, suggesting that perhaps the lower bound on N is closer to the truth than the upper bound, i.e. indicating the trivial 2-digit construction is actually not so bad.