cp's OEIS Frontend

A033810 Number of people needed so that probability of at least two sharing a birthday out of n possible days is at least 50%.

%I A033810 #96 Feb 16 2025 08:32:36
%S A033810 2,2,3,3,3,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,8,8,
%T A033810 8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,
%U A033810 10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,12,12,12
%N A033810 Number of people needed so that probability of at least two sharing a birthday out of n possible days is at least 50%.
%C A033810 a(365) = 23 is the solution to the Birthday Problem.
%H A033810 T. D. Noe and Charles R Greathouse IV, <a href="/A033810/b033810.txt">Table of n, a(n) for n = 1..10000</a> (366 terms from T. D. Noe)
%H A033810 S. E. Ahmed and R. J. McIntosh, <a href="https://cms.math.ca/crux/v26/n3/page151-155.pdf">An Asymptotic Approximation for the Birthday Problem</a>, Crux Mathematicorum 26(3) 151-5 2000 CMS.
%H A033810 D. Brink, <a href="http://dx.doi.org/10.1007/s11139-011-9343-9">A (probably) exact solution to the Birthday Problem</a>, Ramanujan Journal, June 2012, Volume 28, Issue 2, pp. 223-238. - From _N. J. A. Sloane_, Oct 08 2012
%H A033810 Mathforum, <a href="http://mathforum.org/dr.math/faq/faq.birthdayprob.html">The Birthday Problem</a>.
%H A033810 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/BirthdayProblem.html">Birthday Problem</a>.
%F A033810 a(n) = ceiling(sqrt(2*n*log(2)) + (3 - 2*log(2))/6 + (9 - 4*log(2)^2) / (72*sqrt(2*n*log(2))) - 2*log(2)^2/(135*n)) for all n up to 10^18. It is conjectured that this formula holds for all n.
%t A033810 lst = {}; s = 1; Do[Do[If[Product[(n - i + 1)/n, {i, j}] <= 1/2, If[j > s, s = j]; AppendTo[lst, j]; Break[]], {j, s, s + 1}], {n, 86}]; lst (* _Arkadiusz Wesolowski_, Apr 29 2012 *)
%t A033810 A033810[n_] := Catch@Do[If[1/2 >= n!/(n - m)!/n^m, Throw[m]], {m, 2, Infinity}]; Array[A033810, 86] (* _JungHwan Min_, Mar 27 2017 *)
%o A033810 (Python)
%o A033810 from math import comb, factorial
%o A033810 def A033810(n):
%o A033810     def p(m): return comb(n,m)*factorial(m)<<1
%o A033810     kmin, kmax = 0, 1
%o A033810     while p(kmax) > n**kmax: kmax<<=1
%o A033810     while kmax-kmin > 1:
%o A033810         kmid = kmax+kmin>>1
%o A033810         if p(kmid) <= n**kmid:
%o A033810             kmax = kmid
%o A033810         else:
%o A033810             kmin = kmid
%o A033810     return kmax # _Chai Wah Wu_, Jan 21 2025
%Y A033810 Essentially the same as A088141. See also A182008, A182009, A182010.
%Y A033810 Cf. A014088 (n people on 365 days), A225852 (3 on n days), A225871 (4 people on n days).
%Y A033810 Cf. A380129 (Strong Birthday Problem).
%K A033810 nonn,easy,nice
%O A033810 1,1
%A A033810 _Eric W. Weisstein_