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&gt;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 &gt;= M:
        break
    T += (xs - T % xs).min()
return T


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