Pigeon and grain problem: find time until all the grain is eaten

Problem:


There are \$n\$ pigeons and \$m\$ grains. Pigeon \$i\$ eats a single grain every \$x_i\$ seconds. Find the time until all the grain is eaten.


Input:


A line with the integer \$m\$ giving the number of grains, followed by a line with \$n\$ integers \$x_1, x_2, \ldots, x_n\$ giving the time taken by each pigeon to eat one grain.

Currently I am doing a loop over each second and finding how many grains in that seconds are eaten. This with numpy I am able to get a good performance but for large inputs (\$m=10^{25}\$ and \$n=300000\$) the program runs forever.

What can I do mathematically to solve this?

import numpy

def melt(grains,birdTimes):
    counter=0
    counts = numpy.zeros(len(birdTimes,),dtype=numpy.int) 
    birdTimes = numpy.array(birdTimes)
    while (grains>0):
        counts=counts+1
        temp=birdTimes-counts       
        zeroA = numpy.where(temp==0)[0] 
        grains = grains - len(zeroA)
        counts[zeroA] =0
        counter+=1
    return counter

Basically we're looking for the smallest value of \$T\$ which satisfies the discrete equation

$$ \left\lfloor {T \over x_1} \right\rfloor + \left\lfloor {T \over x_2} \right\rfloor + \dots + \left\lfloor {T \over x_n} \right\rfloor \ge m $$

where \$\lfloor {x \over y} \rfloor\$ is the floor division operation (// in Python). So we know the regular division operation (/ in Python) will also be a valid solution to this, albeit not necessarily with the smallest possible \$T\$:

$$ {T \over x_1} + {T \over x_2} + \dots + {T \over x_n} \ge m $$

If we factor out the \$T\$ time value, we see this is just an inequality of the form:

$$ \mathrm{Time} × \mathrm{Rate\ of\ consumption} \ge \mathrm{Amount\ consumed} $$

and thus

$$ \mathrm{Time} \ge {\mathrm{Amount\ consumed} \over \mathrm{Rate\ of\ consumption}}$$

We know the rate of consumption and amount consumed, and so by refactoring the earlier inequality we get this:

$$ T\left( {1 \over x_1} + {1 \over x_2} + \dots + {1 \over x_n} \right) \ge m $$

and thus

$$ T \ge {m \over \left( {1 \over x_1} + {1 \over x_2} + \dots + {1 \over x_n} \right)} $$

You can use this as a heuristic which will get you close to your desired value of \$T\$, now your search space just needs to check values greater than the above result. Start by

T = int(M / ((1. / xs).sum()))

Then iterate upwards to the correct value using your method of choice. How about filling the smallest available remainder to the next multiple? Like so:

while True:
    v = (T // xs).sum()
    if v >= M:
        break
    T += (xs - T % xs).min()
return T

I'm sure there's a closer-to-closed-form solution to this.

StackExchange Code Review Q#139326, answer score: 12