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,1

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.

Formula

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

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}]

Prog

(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
(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

Crossrefs

Cf. A014088, A033810.

Sequence in context: A256409 A256403 A308013 * A260090 A351873 A256941

Adjacent sequences: A380126 A380127 A380128 * A380130 A380131 A380132

Keyword

nonn

Author

Mike Sheppard, Jan 13 2025

Status

approved