Analytical solution solution in Clear category for Feed Pigeons by quarkov
from math import sqrt
The point of this solution is to avoid loop, so it is fast for big n-s.
Sequence of the pigeons amount for the every minute is 1, 3, 6, 10, 15 ...
It's the triangular numbers sequence, which is a(i) = (i+1)*i/2
Sequence of the fed pigeons for the every minute is 1, 4, 10, 20, 35 ...
It's the tetrahedral numbers sequence, which is a(i) = i*(i+1)*(i+2)/6.
Put a(i) = n (amount of the wheat portions)
Get the cubic equation: i*(i+1)*(i+2) - 6*n = 0 which is possible to solve
(have a look into the Cardano's method).
The result is the very moment the wheat should run out.
Be aware it's not working for n = 0.
alpha = (3*n - sqrt(9*(n**2)-1/27)) ** (1/3)
beta = (3*n + sqrt(9*(n**2)-1/27)) ** (1/3)
minute = (alpha + beta - 1) // 1 + 1
last_pigeons = (minute-1)*minute/2
last_feed = (minute**2 - 1)*minute / 6
if n - last_feed > last_pigeons:
last_pigeons = n - last_feed
Below you can see simple loops solution.
pigeons = 0
i = 1
while n > pigeons:
n -= pigeons
pigeons = i*(i+1)/2
i += 1
if n > (i-2)*(i-1)/2:
June 15, 2018