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

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

Author

Lekraj Beedassy, Jul 22 2002

Keywords

• nonn

Comments

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.

Examples

			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.
		

Crossrefs

Cf. A033810, A064619.

Programs

Mathematica

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}]

Python

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

Formula

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

Extensions

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

More terms from David Terr, Jan 03 2005