cp's OEIS Frontend

A308699 Smallest m >= n such that 1 - m! / ((m-n)!*m^n) < 1/2.

%I A308699 #45 Jan 21 2025 22:29:41
%S A308699 0,1,3,6,10,17,24,33,43,55,69,83,100,117,136,157,179,202,227,253,281,
%T A308699 310,341,373,407,442,478,516,555,596,638,682,727,773,821,870,921,974,
%U A308699 1027,1082,1139,1197,1257,1317,1380,1444,1509,1576,1644,1713,1784,1857,1931
%N A308699 Smallest m >= n such that 1 - m! / ((m-n)!*m^n) < 1/2.
%C A308699 a(n) is the minimum size of a hash table such that for n items the probability of collision is smaller than 50%.
%C A308699 The probability that, in a set of n randomly chosen people, some pair of them will have the same birthday is less than 50% if there are at least a(n) days in a year.
%H A308699 Alois P. Heinz, <a href="/A308699/b308699.txt">Table of n, a(n) for n = 0..20000</a>
%H A308699 Wikipedia, <a href="https://en.wikipedia.org/wiki/Birthday_problem">Birthday problem</a>
%H A308699 Wikipedia, <a href="https://en.wikipedia.org/wiki/Hash_table">Hash table</a>
%F A308699 a(n) = A072829(n)+1 for n>1.
%p A308699 a:= proc(n) option remember; local m; Digits:= 20;
%p A308699       if n<2 then m:= n else for m from 2*a(n-1)-a(n-2) do
%p A308699       if n*log(0.0+m)<log(2.0)+lnGAMMA(1.0+m)-lnGAMMA(1.0+m-n)
%p A308699          then break fi od fi; m
%p A308699     end:
%p A308699 seq(a(n), n=0..55);
%t A308699 a[n_] := a[n] = If[n < 2, n, Module[{m}, For[m = 2*a[n-1] - a[n-2], True, m++, If[n*Log[m] < Log[2.`20.] + LogGamma[1.`20. + m] - LogGamma[1.`20. + m - n], Return[m]]]]];
%t A308699 a /@ Range[0, 55] (* _Jean-François Alcover_, Apr 19 2021, after _Alois P. Heinz_ *)
%o A308699 (Python)
%o A308699 from math import comb, factorial
%o A308699 def A308699(n):
%o A308699     f = factorial(n)
%o A308699     def p(m): return comb(m,n)*f<<1
%o A308699     kmin, kmax = n-1, n
%o A308699     while p(kmax) <= kmax**n: kmax<<=1
%o A308699     while kmax-kmin > 1:
%o A308699         kmid = kmax+kmin>>1
%o A308699         if p(kmid) > kmid**n:
%o A308699             kmax = kmid
%o A308699         else:
%o A308699             kmin = kmid
%o A308699     return kmax # _Chai Wah Wu_, Jan 21 2025
%Y A308699 Cf. A033810, A072829.
%K A308699 nonn
%O A308699 0,3
%A A308699 _Alois P. Heinz_, Jun 17 2019