From: "Michael Kleber" <michael.kleber@gmail.com>

Steve Witham wrote:

...

For n = one million, I guess you have to shoot about 13815504 shots -- 1e6 * ln( 1e6 ).

But surely the structure of the problem should give us some leverage and let us do better than that, right?

Right?

(SPOILOIDS)

From: "Fred lunnon" <fred.lunnon@gmail.com> Consider the special case n prime: [...] Total cost (at most) 2n-1 slugs.

For n = 2, 3 and 4, all of which have one prime factor, 2n-1 is the minimum. So... one stage per prime factor, plus a cleanup stage? So, for n=1000000, 2999998 shots? But for n = 510510 = 2 * 3 * 5 * 7 * 11 * 17 it would be 510510 + 510509 + 510508 ... + 510104 = 3573549? If that's true the worst cases are something like n * the, er, inverse-prime-torial function, which is < O(log n). --Steve