A135736 Nearest integer to n*Sum_{k=1..n} 1/k = rounded expected coupon collection numbers.

0, 1, 3, 6, 8, 11, 15, 18, 22, 25, 29, 33, 37, 41, 46, 50, 54, 58, 63, 67, 72, 77, 81, 86, 91, 95, 100, 105, 110, 115, 120, 125, 130, 135, 140, 145, 150, 155, 161, 166, 171, 176, 182, 187, 192, 198, 203, 209, 214, 219, 225, 230, 236, 242, 247, 253, 258, 264, 269, 275

Offset

0,3

Comments

Somewhat more realistic than A052488 but more optimistic than A060293, the expected number of boxes that must be bought to get the full collection of N objects, if each box contains any one of them at random. See also comments in A060293, A052488.

Links

Adam Hugill, Table of n, a(n) for n = 0..10000 (terms 0..999 from G. C. Greubel)

Formula

a(n) = round(n*A001008(n)/A002805(n)) = either A052488(n) or A060293(n).

a(n) ~ A060293(n) ~ A052488(n) ~ A050502(n) ~ A050503(n) ~ A050504(n) (asymptotically)

Conjecture: a(n) = round(n*(log(n) + gamma) + 1/2) for n > 0, where gamma = A001620. - Ilya Gutkovskiy, Oct 31 2016

The conjecture is false: a(2416101) = 36905656 while round(2416101*(log(2416101) + gamma) + 1/2) = 36905657, with the unrounded numbers being 36905656.499999982... and 36905656.500000016.... Heuristically this should happen infinitely often. - Charles R Greathouse IV, Oct 31 2016

Example

a(0) = 0 since nothing needs to be bought if nothing is to be collected.
a(1) = 1 since only 1 box needs to be bought if only 1 object is to be collected.
a(2) = 3 since the chance of getting the other object at the second purchase is only 1/2, so it takes 2 boxes on the average to get it.
a(3) = 6 since the chance of getting a new object at the second purchase is 2/3 so it takes 3/2 boxes in the mean, then the chance becomes 1/3 to get the 3rd, i.e., 3 other boxes on the average to get the full collection and the rounded value of 1 + 3/2 + 3 = 11/2 = 5.5 is 6.

Maple

seq(round(n*harmonic(n)), n=1..100); # Robert Israel, Oct 31 2016

Mathematica

Table[Round[n*Sum[1/k, {k, 1, n}]], {n, 0, 25}] (* G. C. Greubel, Oct 29 2016 *)

Prog

(PARI) A135736(n)=round(n*sum(i=1, n, 1/i))
(Python)
n=100 #set the number of terms you want to calculate here
ans=0
finalans = []
finalans.append(0) #continuity with A135736
for i in range(1, n+1):
    ans+=(1/i)
    finalans.append(int(round(ans*i)))
print(finalans)
# Adam Hugill, Feb 14 2022

Crossrefs

Cf. A060293, A052488, A050502-A050504.

Sequence in context: A085197 A164910 A276583 * A036434 A298795 A140400

Adjacent sequences: A135733 A135734 A135735 * A135737 A135738 A135739

Keyword

easy,nonn

Author

M. F. Hasler, Nov 29 2007

Status

approved