A072829 -id:A072829 - cp's OEIS frontend

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

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

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.

cp's OEIS Frontend

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