|
|
A308699
|
|
Smallest m >= n such that 1 - m! / ((m-n)!*m^n) < 1/2.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
|
|
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]]]]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|