From: "Michael Kleber" <michael.kleber@gmail.com>

Therefore, for n=10^6, you can:

a) Take n shots at square 1. This hits all subs with s=1. b) Then take n/2 shots at square 2. This hits half of the subs with s=2; the other half were already hit by the more-than-n/2 shots taken at square 1. c) Then take n/4 shots at square 3, followed by n/4 shots at square 4. If n were a multiple of 3, you'd need n/3 shots at square 3, but a million ain't. [...] Now the big question: Is this optimal?

If I'm following, with that plan for n = 4 you would shoot at 1, 1, 1, 1, 2, 2, 3, 4 -- 8 shots-- but you only need 7, e.g.: 1, 1, 2, 2, 3, 3, 4. --Steve