login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

CROSSREFS

Cf. A033810, A072829.

Sequence in context: A291986 A094272 A236326 * A286304 A005045 A189376

Adjacent sequences:  A308696 A308697 A308698 * A308700 A308701 A308702

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Jun 17 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 14 02:29 EDT 2019. Contains 327995 sequences. (Running on oeis4.)