A380129 Strong Birthday Problem: Number of people needed so that probability of everyone sharing a birthday out of n possible days is at least 1/2.

2, 4, 8, 12, 16, 21, 26, 31, 36, 41, 47, 52, 58, 64, 69, 75, 81, 87, 93, 100, 106, 112, 119, 125, 131, 138, 144, 151, 158, 164, 171, 178, 184, 191, 198, 205, 212, 219, 226, 233, 240, 247, 254, 261, 268, 275, 283, 290, 297, 304, 312, 319, 326, 334, 341, 348, 356

Offset: 1

Author

Mike Sheppard, Jan 13 2025

Keywords

• nonn

Comments

The answer to the strong birthday problem is 3064, that is, a(365) = 3064. This is the number of people that need to be gathered together before there is a 50% chance that everyone in the gathering shares their birthday with at least one other person.

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..1000
• (Note: OEIS uses definition of m and n which are switched from original references)
• Mario Cortina Borja, The strong birthday problem, Significance 10.6 (2013): 18-20.
• Anirban DasGupta, The matching, birthday and the strong birthday problem: a contemporary review, Journal of Statistical Planning and Inference 130.1-2 (2005): 377-389.

Crossrefs

Cf. A014088, A033810.

Programs

Mathematica

(* a(n)=m, n number of days, m number of people *)
p[n_, m_] :=Sum[((-1)^i*n^(-m)*((-i + n)^((-i) + m))*n!*m!)/(i!*((-i + n)!)*((-i + m)!)), {i, 0, m}];
a[n_] := Module[{m = n + 1, prob = 0}, While[prob < 0.5, prob = p[n, m]; m++;]; m - 1];
Table[a[n], {n, 1, 20}]

PARI

p(n,m) = sum(i=0, n, (-1)^i*(n-i)^(m-i)*binomial(n,i)*m!/(m-i)!)/n^m;
a(n) = my(ma, mb=n+1, md); while(2*p(n,mb)<1, mb<<=1); ma=mb\2; while(mb>ma, md=(ma+mb)\2; if(2*p(n,md)<1, ma=md+1, mb=md)); ma; \\ Jinyuan Wang, Jan 24 2025

Python

from math import comb, factorial
def A380129(n):
    def p(m): return sum((-1 if i&1 else 1)*comb(m,i)*comb(n,i)*factorial(i)*(n-i)**(m-i) for i in range(m+1))<<1
    kmin, kmax = n, n+1
    while p(kmax) < n**kmax: kmax<<=1
    while kmax-kmin > 1:
        kmid = kmax+kmin>>1
        if p(kmid) >= n**kmid:
            kmax = kmid
        else:
            kmin = kmid
    return kmax # Chai Wah Wu, Jan 21 2025

Formula

a(n) ~ -n LambertW(-1, -Log(2)/n).