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, 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

1,3

Comments

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

Links

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

Formula

a(n) = A033810(n)-1. - Pontus von Brömssen, Jan 07 2026

Example

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.

Mathematica

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, 1, 86}]; lst (* Arkadiusz Wesolowski, Apr 29 2012 *)

Prog

(Python)
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

Crossrefs

Cf. A033810, A072829.

Sequence in context: A023966 A368942 A373813 * A185283 A214972 A225687

Adjacent sequences: A088138 A088139 A088140 * A088142 A088143 A088144

Keyword

nonn

Author

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

Extensions

Edited by Don Reble, Nov 07 2005

a(1) prepended by Pontus von Brömssen, Jan 07 2026

Status

approved