Number of people needed to cover all year with birthdays with p=50%

# Calculate minimum number of people required, so that the probability
# that their birthdays cover all days of the year is at least 50%

BUCKETS=365
p = [0]*(BUCKETS+1)
people = 1
scale = 1
p[1] = 1

# p[n] holds probability that after "people" birthdays were randomly selected
# the number of days covered is n. All probabilities are represented as integers
# with the scale factor of BUCKETS**(people-1)
#
# Initial condition: we have one person: people=1
# their birthday covers 1 day with 100% probability: p[1] == 1
# For any other n, p[n] == 0

while p[BUCKETS]*2 < scale:
    p1 = [0]*(BUCKETS+1)
    p1[1] = 1
    for n in range(2,BUCKETS+1):
        # Calculate probability that the birthdays cover n days after we pick
        # on more person. This may happen if either
        # - all birthdays previously covered n-1 days and new person's birthday
        #   falls onto a new day; the probability of that is p[n-1] multiplied
        #   by (BUCKETS-(n-1))/BUCKETS
        # - all birthdays already covered n days, and new day is one of the existing
        #   days; the probability of that is p[n]*n/BUCKETS
        #
        # We omit division by BUCKETS to keep the calculation in integers
        p1[n] = p[n-1]*(BUCKETS-n+1) + p[n]*n
    p = p1
    scale *= BUCKETS
    people += 1
    assert sum(p) == scale
    print(people, p[BUCKETS]/scale)