Okay, Fred has pretty much arrived at the solution I wanted to talk about. Let me summarize, and answer his "rather murky" question in the positive. For a submarine with velocity b, let's say it has "step size" s = gcd(b,n): its route eventually passes through every s'th square, with period n/s. (So if you shoot at any square it passes through for n/s, you're guaranteed to hit it.) 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. Etc: pass through the squares in order, shooting at square k for n/d shots, where d is the smallest divisor of n that is greater than or equal to k. If you instead shoot for n/k shots, ignoring the question of which were divisors, you'd end up taking n*ln(n) shots, just as Steve Witham's heuristic predicted. So we're within that upper bound. And note that when n is prime, this reproduces the 2p-1 shots that Fred mentioned earlier: p shots at 1, then one shot at each other square. Now the big question: Is this optimal? I haven't even been able to prove optimality for the prime case, which really feels like it ought to be easy... --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.