A033810 -id:A033810 - cp's OEIS frontend

A014088 Minimal number of people to give a 50% probability of having at least n coincident birthdays in one year.

1, 23, 88, 187, 313, 460, 623, 798, 985, 1181, 1385, 1596, 1813, 2035, 2263, 2494, 2730, 2970, 3213, 3459, 3707, 3959, 4213, 4470, 4728, 4989, 5252, 5516, 5783, 6051, 6320, 6592, 6864, 7138, 7413, 7690, 7968, 8247, 8527, 8808, 9090, 9373, 9657, 9942, 10228

Offset: 1

Steven Finch

nonn

Stig Blücher Brink, Table of n, a(n) for n = 1..10000 (terms 1..61 from Hiroaki Yamanouchi, terms 62..250 from Rob Cook)
Patrice Le Conte, Coincident Birthdays.
P. Diaconis and F. Mosteller, Methods of studying coincidences, J. Amer. Statist. Assoc. 84 (1989), pp. 853-861.
Bruce Levin, Exact Solutions of the Generalized Birthday Problem.
B. Martin, Coincidence:Remarkable or Random, Skeptical Inquirer Volume 22.5, September / October 1998.
I. Peterson, Mathtrek, Birthday Surprises [Archived version from Jun 28 2013]
Maksym Petkus, Efficient (Non-)Membership Tree from Multicollision-Resistance with Applications to Zero-Knowledge Proofs, Cryptology ePrint Archive (2024). See pp. 6, 34.
Eric Weisstein's World of Mathematics, Birthday Problem.

Cf. A033810 (2 people on n days), A225852 (3 people on n days), A225871 (4 people on n days).

Cf. A088141, A182008, A182009, A182010.

q[1][n_, d_] := q[1][n, d] = d!/((d-n)!*d^n) // N; q[k_][n_, d_] := q[k][n, d] = Sum[ n!*d!/(d^(i* k)*i!*(k!)^i*(n-i*k)!*(d-i)!)*Sum[ q[j][n-i*k, d-i]*(d-i)^(n-i* k)/d^(n-i*k), {j, 1, k-1}], {i, 1, Floor[n/k]}] // N; p[k_][n_, d_] := 1 - Sum[q[i][n, d], {i, 1, k-1}]; a[1] = 1; a[k_] := a[k] = For[n = a[k-1], True, n++, If[p[k][n, 365] >= 1/2, Return[n]]]; Table[ Print["a(", k, ") = ", a[k]]; a[k], {k, 1, 15}] (* Jean-François Alcover, Jun 12 2013, after Eric W. Weisstein *)

Broken links corrected by Steven Finch, Jan 27 2009

a(16)-a(45) from Hiroaki Yamanouchi, Mar 19 2015

A088141 a(n) = the largest k such that, if k samples are taken from a group of n items, with replacement, a duplication is unlikely (p<1/2).

Original entry on oeis.org

1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11

Offset: 2

Artemario Tadeu Medeiros da Silva (artemario(AT)uol.com.br), Nov 06 2003

nonn

Related to the birthday paradox. This is essentially the same as A033810.

			a(365)=22 because if 22 people are sampled, it is unlikely that two have the same birthday; but if 23 are sampled, it is likely.

Arkadiusz Wesolowski, Table of n, a(n) for n = 2..10000

Cf. A033810, A072829.

lst = {}; s = 1; Do[Do[If[Product[(n - i)/n, {i, j}] <= 1/2, If[j > s, s = j]; AppendTo[lst, j]; Break[]], {j, s, s + 1}], {n, 2, 86}]; lst (* Arkadiusz Wesolowski, Apr 29 2012 *)

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

Edited by Don Reble, Nov 07 2005

A225852 The number of people required for there to be at least a 50% chance that at least 3 share a birthday in a year with n days.

Original entry on oeis.org

3, 4, 5, 6, 7, 7, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 14, 15, 15, 16, 16, 16, 17, 17, 18, 18, 18, 19, 19, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 24, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 28, 28, 28, 29, 29, 29, 29, 30, 30

Offset: 1

Kevin L. Schwartz and Christian N. K. Anderson, May 17 2013

nonn

a(365) = 88.

For n <= 1000, a(n) = 1.436 + 1.812*n^0.654 - 0.817/n^3 provides an estimate accurate to 0.6 units.

			The probability that out of 87 people 3 share a birthday in a year with 365 days is 0.4994549. The corresponding probability for 88 people is 0.5110651. Therefore a(365)=88.

Christian N. K. Anderson, Table of n, a(n) for n = 1..1000
Christian N. K. Anderson, Table of n and exact probabilities of a(n)-1 and a(n) for n = 1..1000
Patrice Le Conte, Coincident Birthdays

Cf. A014088 (n people on 365 days), A033810 (2 people on n days), A225871 (4 people on n days).

Cf. A088141, A182008, A182009, A182010.

library(gmp);#prob of a maximum of exactly k coincident birthdays is
BigQ<-function(nday,p,k) { #nday=days in a year; p=people
    if(p1,sum(sapply(2:k-1,function(j) BigQ(nday-i,p-k*i,j))),1)
    }
    tot
}
BDaySharedByAtLeast<-function(nday,people,k) {
    if(nday<1 | people

A182008 a(n) = ceiling(sqrt(2nlog(2))).

Original entry on oeis.org

2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11

Offset: 1

David Brink, Apr 06 2012

nonn

This sequence approximates the sequence of solutions to the Birthday Problem, A033810. The two sequences agree on a set of integers n with density (3+2 log 2)/6 = 0.731...

Gheorghe Coserea, Table of n, a(n) for n = 1..10000
D. Brink, A (probably) exact solution to the Birthday Problem, Ramanujan Journal, 2012, pp 223-238.

Approximates A033810.

[Ceiling(Sqrt(2*n*Log(2))): n in [1..100]]; // Vincenzo Librandi, Aug 23 2015

Table[Ceiling[Sqrt[2 n Log[2]]], {n, 100}] (* Vincenzo Librandi, Aug 23 2015 *)

a(n) = { ceil(sqrt(2*n*log(2))) };
apply(n->a(n), vector(88, i, i))  \\ Gheorghe Coserea, Aug 23 2015

A182009 a(n) = ceiling(sqrt(2nlog(2))+(3-2log(2))/6).

Original entry on oeis.org

2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11

Offset: 1

David Brink, Apr 06 2012

nonn

This sequence approximates the sequence of solutions to the Birthday Problem, A033810. The two sequences agree for almost all n, i.e., on a set of integers n with density 1.

Gheorghe Coserea, Table of n, a(n) for n = 1..10000
D. Brink, A (probably) exact solution to the Birthday Problem, Ramanujan Journal, 2012, pp 223-238.

Approximates A033810.

seq(ceil((2*n*log(2))^(1/2) + (3-2*log(2))/6), n=1..1000); # Robert Israel, Aug 23 2015

Table[Ceiling[Sqrt[2 n Log[2] + (3 - 2 Log[2])/6]], {n, 82}] (* Michael De Vlieger, Aug 24 2015 *)

a(n) = { ceil((2*n*log(2))^(1/2) + (3-2*log(2))/6) };
apply(n->a(n), vector(84, i, i))  \\ Gheorghe Coserea, Aug 23 2015

A225871 Number of people required for there to be a 50% probability that at least 4 share a birthday in a year with n days.

Original entry on oeis.org

4, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 18, 19, 20, 21, 22, 23, 24, 25, 25, 26, 27, 28, 28, 29, 30, 31, 32, 32, 33, 34, 34, 35, 36, 37, 37, 38, 39, 39, 40, 41, 41, 42, 43, 43, 44, 45, 45, 46, 46, 47, 48, 48, 49, 50, 50, 51, 51, 52, 53, 53, 54, 54, 55, 56

Offset: 1

Kevin L. Schwartz and Christian N. K. Anderson, May 18 2013

nonn

a(365)=187.

For n<1000, the formula a(n) = 2.79 + 2.456*n^0.732 - 1.825/n provides an estimate of a(n) accurate to 0.82.

			For a year with 365 days, a(365), the probability that out of 186 people 4 of them share a birthday is 0.495825. The corresponding probability for 187 people is 0.502685, and therefore a(365)=187.

Christian N. K. Anderson, Table of n, a(n) for n = 1..1000
Christian N. K. Anderson, Table of n, exact probabilities of a(n)-1 and a(n) for n = 1..1000.
Patrice Le Conte, Coincident Birthdays

Cf. A014088 (n people on 365 days), A033810 (2 people on n days), A225852 (3 on n days).

Cf. A088141, A182008, A182009, A182010.

library(gmp);#prob of a maximum of exactly k coincident birthdays is
BigQ<-function(nday,p,k) { #nday=days in a year; p=people
    if(p1,sum(sapply(2:k-1,function(j) BigQ(nday-i,p-k*i,j))),1)
    }
    tot
}
BDaySharedByAtLeast<-function(nday,people,k) {
    if(nday<1 | people

A072829 Greatest m such that Product_{k=1..n-1} (1 - k/m) <= 1/2.

Original entry on oeis.org

2, 5, 9, 16, 23, 32, 42, 54, 68, 82, 99, 116, 135, 156, 178, 201, 226, 252, 280, 309, 340, 372, 406, 441, 477, 515, 554, 595, 637, 681, 726, 772, 820, 869, 920, 973, 1026, 1081, 1138, 1196, 1256, 1316, 1379, 1443, 1508, 1575, 1643, 1712, 1783, 1856, 1930, 2005

Offset: 2

Lekraj Beedassy, Jul 22 2002

nonn

Among n randomly selected dates over an interval of m days (or less), the odds are even (or better than even) for two or more of them to coincide.

			Thus a(7)=32 for instance implies that among 7 persons bearing the same astrological sign(extending over 30 days or so) the odds are trifle better than even for at least two of them further sharing a common birthday.

Cf. A033810, A064619.

f[n_] := (k = 1; While[ Product[1 - i/k, {i, 1, (n - 1)}] <= 1/2, k++ ]; Return[k - 1]); Table[ f[n], {n, 2, 53}]

from math import factorial, comb
def A072829(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 kmin # Chai Wah Wu, Jan 21 2025

Corresponds to the ultimate occurrence of n in A033810. For large n, m has magnitude n^2 / 2 * log(2).

Edited and extended by Robert G. Wilson v, Jul 23 2002

More terms from David Terr, Jan 03 2005

A380129 Strong Birthday Problem: Number of people needed so that probability of everyone sharing a birthday out of n possible days is at least 1/2.

Original entry on oeis.org

2, 4, 8, 12, 16, 21, 26, 31, 36, 41, 47, 52, 58, 64, 69, 75, 81, 87, 93, 100, 106, 112, 119, 125, 131, 138, 144, 151, 158, 164, 171, 178, 184, 191, 198, 205, 212, 219, 226, 233, 240, 247, 254, 261, 268, 275, 283, 290, 297, 304, 312, 319, 326, 334, 341, 348, 356

Offset: 1

Mike Sheppard, Jan 13 2025

nonn

The answer to the strong birthday problem is 3064, that is, a(365) = 3064. This is the number of people that need to be gathered together before there is a 50% chance that everyone in the gathering shares their birthday with at least one other person.

Chai Wah Wu, Table of n, a(n) for n = 1..1000
(Note: OEIS uses definition of m and n which are switched from original references)
Mario Cortina Borja, The strong birthday problem, Significance 10.6 (2013): 18-20.
Anirban DasGupta, The matching, birthday and the strong birthday problem: a contemporary review, Journal of Statistical Planning and Inference 130.1-2 (2005): 377-389.

Cf. A014088, A033810.

(* a(n)=m, n number of days, m number of people *)
p[n_, m_] :=Sum[((-1)^i*n^(-m)*((-i + n)^((-i) + m))*n!*m!)/(i!*((-i + n)!)*((-i + m)!)), {i, 0, m}];
a[n_] := Module[{m = n + 1, prob = 0}, While[prob < 0.5, prob = p[n, m]; m++;]; m - 1];
Table[a[n], {n, 1, 20}]

p(n,m) = sum(i=0, n, (-1)^i*(n-i)^(m-i)*binomial(n,i)*m!/(m-i)!)/n^m;
a(n) = my(ma, mb=n+1, md); while(2*p(n,mb)<1, mb<<=1); ma=mb\2; while(mb>ma, md=(ma+mb)\2; if(2*p(n,md)<1, ma=md+1, mb=md)); ma; \\ Jinyuan Wang, Jan 24 2025

from math import comb, factorial
def A380129(n):
    def p(m): return sum((-1 if i&1 else 1)*comb(m,i)*comb(n,i)*factorial(i)*(n-i)**(m-i) for i in range(m+1))<<1
    kmin, kmax = n, n+1
    while p(kmax) < n**kmax: kmax<<=1
    while kmax-kmin > 1:
        kmid = kmax+kmin>>1
        if p(kmid) >= n**kmid:
            kmax = kmid
        else:
            kmin = kmid
    return kmax # Chai Wah Wu, Jan 21 2025

a(n) ~ -n LambertW(-1, -Log(2)/n).

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

Original entry on oeis.org

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

Alois P. Heinz, Jun 17 2019

nonn

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.

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

Cf. A033810, A072829.

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)

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

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

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

A099600 Inventory application: Numerator of the probability (rounded to the nearest trillionth: (10^-12)-th) of at least one shortage per month when n customers each request one item on one independently-chosen random day of a 30-day month, but when only exactly one such item is available per day.

Original entry on oeis.org

0, 0, 33333333333, 97777777778, 188000000000, 296266666667, 413555555556, 530844444444, 640314074074, 736230320988, 815361224691, 876907483128, 922041405981, 953224843588, 973494078033, 985863508285, 992931754142, 996701485266, 998570643615, 999428257446, 999790361064, 999930120355, 999979036106, 999994409628, 999998695580, 999999739116, 999999956519, 999999994203, 999999999420, 999999999961, 999999999999, 1000000000000

Offset: 0

Rick L. Shepherd, Oct 24 2004

A shortage occurs each time a customer cannot immediately be provided the item (that is, on the day it is requested). The denominator is always 10^12 here. Inspired by just-in-time inventory considerations for pharmacies, where new prescriptions and refills are usually for 30-day supplies, many medications are expensive and it is important to minimize cost of inventory and inconvenience of shortages to patients, pharmacists and supply clerks. Of course similar sequences can be computed for probabilities of at least (or exactly) m shortages per month under the same conditions and/or with higher item availabilities.

			a(2) = 33333333333, so if only two customers each request the item on random days during the month, there is only a .033(3333...) or ~3.3% probability that they would do so on the same day - causing a shortage for the second customer. However, "collisions" of needs/wants go up rapidly with the number of customers.
a(7) = 530844444444, so 7 = A033810(30) is the least number of customers for which the probability of at least one shortage during the month, 0.530844444444, exceeds 0.5 or 50%. This corresponds to the solution of the Birthday Problem, where A014088(2) = 23 = A033810(365), on a planet (or moon) with a 30-day "year".

Eric Weisstein's World of Mathematics, Birthday Problem.

Cf. A014088, A033810.

a(n) = if(n>30, 10^12, round(10^12*(1.-30!/((30-n)!*30^n))))
for(k=0,31,print1(a(k),","))

a(n) = round(10^12 * (1. - 30!/ ((30-n)! * 30^n) )) for 0 <= n <= 30. This corresponds, with d=30, to P_2(n, d) at the MathWorld Birthday Problem link. Clearly the probability is 1 and so a(n) = 10^12 here for all n > 30.

cp's OEIS Frontend

A014088 Minimal number of people to give a 50% probability of having at least n coincident birthdays in one year.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A088141 a(n) = the largest k such that, if k samples are taken from a group of n items, with replacement, a duplication is unlikely (p<1/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A225852 The number of people required for there to be at least a 50% chance that at least 3 share a birthday in a year with n days.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

R

A182008 a(n) = ceiling(sqrt(2*n*log(2))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

A182009 a(n) = ceiling(sqrt(2n*log(2))+(3-2*log(2))/6).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A225871 Number of people required for there to be a 50% probability that at least 4 share a birthday in a year with n days.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

R

A072829 Greatest m such that Product_{k=1..n-1} (1 - k/m) <= 1/2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A380129 Strong Birthday Problem: Number of people needed so that probability of everyone sharing a birthday out of n possible days is at least 1/2.

Views

Author

Keywords

A182008 a(n) = ceiling(sqrt(2nlog(2))).

A182009 a(n) = ceiling(sqrt(2nlog(2))+(3-2log(2))/6).