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

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

Formula

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

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)<log(2.0)+lnGAMMA(1.0+m)-lnGAMMA(1.0+m-n)
         then break fi od fi; m
    end:
seq(a(n), n=0..55);

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 *)

Prog

(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

Crossrefs

Cf. A033810, A072829.

Sequence in context: A360889 A094272 A236326 * A286304 A005045 A189376

Adjacent sequences: A308696 A308697 A308698 * A308700 A308701 A308702

Keyword

nonn,changed

Author

Alois P. Heinz, Jun 17 2019

Status

approved