On Mon, 15 Oct 2007, Scott Huddleston wrote:
For p an odd prime, I give a solution for the size N = 2p submarine problem in 2N-1 = 4p-1 steps using 2N-2 shots.
At t = 0, 2, ... , N-2 shoot square 0. At t = 1, 3, ... , N-3 shoot square t+1. At t = N-1 shoot your foot (this shot is not needed for the submarines). At t = N, N+2, ... , 2N-2 shoot square p = N/2. At t = N+1, N+3, ... , 2N-3 shoot square (t+1+p) mod N.
Although I cannot prove it, computations lead me to conjecture that this strategy for shooting also works if you let p be any power of an odd prime. (In my computations I shoot square 0 instead of my foot.) In addition, computations show that for n up to 500 the shooting schedule with 2n-1 shots mentioned by Richard Schroeppel: (0,0,...,0, 1,2,...,n-1) [with n zeros] manages to kill the sub IFF n has only one prime factor. Of course, I'm not claiming that 2n-1 is minimum. We know this is not the case.