On 10/11/07, Steve Witham <sw@tiac.net> wrote:
... 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? ...
Er, this still doesn't look quite right to me. For composite number n of cells, the problem may be partitioned according to the HCF m of n and the target velocity b. Suppose the factors m_i (including m_1 = 1 and m_k = n) are arranged in increasing order [and define m_0 = 0]. For the subproblem corresponding to a factor m of n, the player must target each of m (consecutive) cells with n/m (possibly nonconsecutive) shots. We might as well choose consecutive blocks of cells, each starting from cell 0. Now it gets rather murky. At stage i > 0, the first m_{i-1} cells have already been targetted; is it possible to schedule the remaining shots so that they do not overlap orbits previously excluded? [This must be possible if we are allowed to miss turns without penalty.] If so, the number of shots is in total \sum_i (m_i - m_{i-1}) n/m_i , summed over (all) the divisors m_i of n. For example for n = pq a product of two primes p < q, this comes to 4n - 2q - p^2. Finally, all the above assumes that we know n and its factorisation; but suppose on the other hand that we don't even know n --- what is a good strategy now? Enough --- no more! [T'is not as sweet as t'were before.] Fred Lunnon