From: "Michael Kleber" <michael.kleber@gmail.com> --------- You are shooting at a submarine that is moving through Z/nZ at constant velocity -- that is, its position at time t is a+bt (mod n), for some 0 <= a,b < n -- but you don't know a or b. At each time t=0,1,2,..., you can shoot at one position. How quickly can you hit all possible submarines?
For n = one million, I guess you have to shoot about 13815504 shots -- 1e6 * ln( 1e6 ). That is how many times you have to shoot at random before the chance that you've still missed is <= 1/1e6. Here is my back-of-the-envelope calculator: #include <math.h> #include <stdio.h> main () { double remain; long n; long shots; for( n = 10; n <= 1000000; n *= 10 ) { remain = 1.0; shots = 0; while( remain > 1.0/n ) { shots++; remain -= remain / n; } printf( "%7d %8d %f\n", n, shots, shots * 1.0 / n / log(n) ); } } (In the C standard library, log(n) is the natural log.) --Steve