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.
In private email, NJAS was kind enough to point out that the usual formulation is "maximal distance between integers relatively prime to n" -- that is, I was off by 1. The correct sequence is A048669, known as the "Jacobsthal function". More pleasant name indeed. Let's call it J(n). So my bound on the submarine problem for n is n*J(n). (Well, I suppose n*J(n) - (J(n)-1), if you want to shave off the corners.) Thanks, Neil. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.