Editing Birthday problem (section)

===Arbitrary number of days===
Given a year with {{mvar|d}} days, the '''generalized birthday problem''' asks for the minimal number {{math|''n''(''d'')}} such that, in a set of {{mvar|n}} randomly chosen people, the probability of a birthday coincidence is at least 50%. In other words, {{math|''n''(''d'')}} is the minimal integer {{mvar|n}} such that

:<math>1-\left(1-\frac{1}{d}\right)\left(1-\frac{2}{d}\right)\cdots\left(1-\frac{n-1}{d}\right)\geq \frac{1}{2}.</math>

The classical birthday problem thus corresponds to determining {{math|''n''(365)}}. The first 99 values of {{math|''n''(''d'')}} are given here {{OEIS|id=A033810}}:

:{| class="wikitable" style="text-align:center;"
|-
! scope="row" | {{mvar|d}}
| 1–2 || 3–5 || 6–9 || 10–16 || 17–23 || 24–32 || 33–42 || 43–54 || 55–68 || 69–82 || 83–99
|-
! scope="row" | {{math|''n''(''d'')}}
| 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12
|}

A similar calculation shows that {{math|''n''(''d'')}} = 23 when {{mvar|d}} is in the range 341–372.

A number of bounds and formulas for {{math|''n''(''d'')}} have been published.<ref>{{wikicite|ref={{Harvid|Brink|2012}}|reference=D. Brink, A (probably) exact solution to the Birthday Problem, Ramanujan Journal, 2012, [https://link.springer.com/article/10.1007/s11139-011-9343-9].}}</ref>
For any {{math|''d'' ≥ 1}}, the number {{math|''n''(''d'')}} satisfies<ref>{{Harvard citations|author=Brink|year=2012|nb=yes|loc=Theorem 2}}</ref>

:<math>\frac{3-2\ln2}{6}<n(d)-\sqrt{2d\ln2}\leq 9-\sqrt{86\ln2}.</math>

These bounds are optimal in the sense that the sequence {{math|''n''(''d'') − {{sqrt|2''d'' ln 2}}}}
gets arbitrarily close to
:<math>\frac{3-2\ln2}{6} \approx 0.27,</math>
while it has
:<math>9-\sqrt{86\ln2}\approx 1.28</math>
as its maximum, taken for {{math|''d'' {{=}} 43}}.

The bounds are sufficiently tight to give the exact value of {{math|''n''(''d'')}} in most of the cases. For example, for {{math|''d'' {{=}}}} 365 these bounds imply that {{math|22.7633 < ''n''(365) < 23.7736}} and 23 is the only [[integer]] in that range. In general, it follows from these bounds that {{math|''n''(''d'')}} always equals either
:<math>\left\lceil\sqrt{2d\ln2}\,\right\rceil \quad\text{or}\quad \left\lceil\sqrt{2d\ln2}\,\right\rceil+1</math>
where {{math|⌈ · ⌉}} denotes the [[Floor and ceiling functions|ceiling function]].
The formula

:<math>n(d) = \left\lceil\sqrt{2d\ln2}\,\right\rceil</math>

holds for 73% of all integers {{mvar|d}}.<ref name=Brink>{{Harvard citations|author=Brink|year=2012|nb=yes|loc=Theorem 3}}</ref> The formula

:<math>n(d) = \left\lceil\sqrt{2d\ln2}+\frac{3-2\ln2}{6}\right\rceil</math>

holds for [[almost all]] {{mvar|d}}, i.e., for a set of integers {{mvar|d}} with [[asymptotic density]] 1.<ref name=Brink/>

The formula

:<math>n(d)=\left\lceil \sqrt{2d\ln2}+\frac{3-2\ln2}{6}+\frac{9-4(\ln2)^2}{72\sqrt{2d\ln2}}\right\rceil</math>

holds for all {{math|''d'' ≤ {{val|e=18}}}}, but it is conjectured that there are infinitely many counterexamples to this formula.<ref name="ReferenceA">{{Harvard citations|author=Brink|year=2012|nb=yes|loc=Table 3, Conjecture 1}}</ref>

The formula

:<math>n(d)=\left\lceil \sqrt{2d\ln2}+\frac{3-2\ln2}{6}+\frac{9-4(\ln2)^2}{72\sqrt{2d\ln2}}-\frac{2(\ln2)^2}{135d}\right\rceil</math>

holds for all {{math|''d'' ≤ {{val|e=18}}}}, and it is conjectured that this formula holds for all {{mvar|d}}.<ref name="ReferenceA"/>