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

%I A088141 #22 Jan 21 2025 22:28:15
%S A088141 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,
%T A088141 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,
%U A088141 10,10,10,10,10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,11
%N 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).
%C A088141 Related to the birthday paradox. This is essentially the same as A033810.
%H A088141 Arkadiusz Wesolowski, <a href="/A088141/b088141.txt">Table of n, a(n) for n = 2..10000</a>
%e A088141 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.
%t A088141 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 *)
%o A088141 (Python)
%o A088141 from math import comb, factorial
%o A088141 def A088141(n):
%o A088141     def p(m): return comb(n,m)*factorial(m)<<1
%o A088141     kmin, kmax = 0, 1
%o A088141     while p(kmax) > n**kmax: kmax<<=1
%o A088141     while kmax-kmin > 1:
%o A088141         kmid = kmax+kmin>>1
%o A088141         if p(kmid) <= n**kmid:
%o A088141             kmax = kmid
%o A088141         else:
%o A088141             kmin = kmid
%o A088141     return kmin # _Chai Wah Wu_, Jan 21 2025
%Y A088141 Cf. A033810, A072829.
%K A088141 nonn
%O A088141 2,2
%A A088141 Artemario Tadeu Medeiros da Silva (artemario(AT)uol.com.br), Nov 06 2003
%E A088141 Edited by _Don Reble_, Nov 07 2005