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

0, 1, 3, 6, 10, 17, 24, 33, 43, 55, 69, 83, 100, 117, 136, 157, 179, 202, 227, 253, 281, 310, 341, 373, 407, 442, 478, 516, 555, 596, 638, 682, 727, 773, 821, 870, 921, 974, 1027, 1082, 1139, 1197, 1257, 1317, 1380, 1444, 1509, 1576, 1644, 1713, 1784, 1857, 1931

Offset: 0

Author

Alois P. Heinz, Jun 17 2019

Keywords

• nonn

Comments

a(n) is the minimum size of a hash table such that for n items the probability of collision is smaller than 50%.

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.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..20000
• Wikipedia, Birthday problem
• Wikipedia, Hash table

Crossrefs

Cf. A033810, A072829.

Programs

Maple

a:= proc(n) option remember; local m; Digits:= 20;
      if n<2 then m:= n else for m from 2*a(n-1)-a(n-2) do
      if n*log(0.0+m)
				

Mathematica

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]]]]];
a /@ Range[0, 55] (* Jean-François Alcover, Apr 19 2021, after Alois P. Heinz *)

Python

from math import comb, factorial
def A308699(n):
    f = factorial(n)
    def p(m): return comb(m,n)*f<<1
    kmin, kmax = n-1, n
    while p(kmax) <= kmax**n: kmax<<=1
    while kmax-kmin > 1:
        kmid = kmax+kmin>>1
        if p(kmid) > kmid**n:
            kmax = kmid
        else:
            kmin = kmid
    return kmax # Chai Wah Wu, Jan 21 2025

Formula

a(n) = A072829(n)+1 for n>1.