In case anyone (other than me) is still interested in the submarine problem, I have a new point of view to share. In particular, I can now construct a sequence of shots for the original n=1,000,000 instance of the problem that destroys all submarines in time 4n. (This is much better than the 12 million or so shots that the n log n algorithm required.) (Oh, and there's an integer sequence that comes up along the way -- so if you're not interested in subs but your initials are NJAS, keep reading anyway. :-) Definition: A "v-sweep" for the n-submarine problem is a sequence of n shots which hit every submarine with velocity v. Note that you can't accomplish this with fewer than n shots, since the n subs with velocity v are parallel -- that is, their paths never intersect, so no single shot can hit two of them. Moreover there are exactly n! v-sweeps (for a given n and v) -- you can hit the n subs in any order. To create a v-sweep, write down any permutation of 1..n and add v*i to the ith element (mod n) -- you're transforming the list of initial positions of the subs you're going to hit into their positions at the times you hit them. Example 1: The permutations are exactly the 0-sweeps: to hit the stationary subs, shoot at every site (in any order). Example 2: The sequence of n 0's is a v-sweep for every v such that gcd(v,n)=1. These are the subs whose trajectories touch every site, so they will pass through 0 once in every n time steps. So one (very limiting) strategy for hitting all the subs is to partition the set of possible velocities V into, say, V1 union V2, and then find a sweep that is a v-sweep for all v in V1 and another sweep that works for all v in V2. If n is a prime, for example, then the two examples above go together to reproduce our old 2p-1 solution. (The "-1" in "2n-1" is because sweeps are translation-invariant -- that is, you can freely add a constant to each term -- so if we're going to shoot one sweep and then another, we can translate one so that the final shot of the first sweep also serves as the initial shot of the second sweep.) Claim: if the sequence (s_i), i=1..n, is a v-sweep, then the sequence ((s_i + w*i) mod n), i=1..n, is a ((v+w) mod n)-sweep. Proof: The map taking the submarine with initial position p and velocity v to the one with initial position p and velocity v+w (mod n) is an automorphism of the original problem. If you think about the subs swimming in a circular ocean, this corresponds to placing the ocean on a lazy susan and spinning it with velocity -w. (Yes, the submarine metaphor seems to be wearing thin.) This is the same logic which allowed the exhaustive search folks to assume WLOG that the first *two* shots are at 0, instead of just the first one shot. Construction: Phase 0: take n shots at 0 Phase 1: take n shots at 0,1,2,...,n-1 Phase 2: take n shots at 0,2,4,6,...,2n-2 (mod n) ... Phase k: take n shots at 0,k,2k,3k,...,k(n-1) (mod n) This will hit all submarines with velocities v such that at least one of v,v+1,v+2,...,v+k is relatively prime to n. So how many phases do you need? Set k to be the length of the longest sequence of consecutive numbers not relatively prime to n. For example: -- For n a prime or prime power, you need two phases (0 and 1), since no two consecutive numbers are both divisible by p. This reproduces the 00...012...n-1 construction that takes 2n-1 shots. -- For n = p^a q^b for odd primes p,q, you can do it with three phases (0,1,2). Certainly if p|i and q|i+1, then neither p nor q can divide i+2. -- For 2^a q^b for odd prime q, you can do it with four phases. The length-3 sequence q-1, q, q+1 is the longest sequence of non-relatively-primes. This does it for n=1,000,000 in 4 million shots (well, 4million-3). -- For n=210=2*3*5*7, for instance, this construction is very bad: you need 10 phases. None of the numbers in the length-9 sequence 2,3,4,5,6,7,8,9,10 is prime to 210. (This means we can solve the n=210 sub problem in 10n-9 = 2091 shots, but the old n log n algorithm does it in 1118.) It seems to me that this "shifts of 00000" strategy doesn't benefit from choosing shifts more complicated than 0,1,2,...k: the Chinese Remainder Theorem says that all that matter are the residue classes of your shifts mod each prime dividing n, since you'll always be able to find a worst-case scenario for each prime individually. I was happy to realize this, because it spared me from having to think about cleverer ways to cover Z/nZ with translates of the set of primitive elements -- but in my relief I didn't think through this as carefully as necessary, so maybe I'm wrong. Integer sequence alert: surely the function "longest gap between numbers relatively prime to n" has a more pleasant name? For n=1,2,3,4,...,20 it has values 0,1,1,1,1,3,1,1,1,3,1,3,1,3,2,1,1,3,1,3, with 1 at every prime power, 3 at 2^a q^b, and the unique 2 at 15. This certainly isn't generally optimal. And it's not an upper bound linear in n, either; pity. But for all that, it's pretty good. --Michael Kleber