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

Author

M. F. Hasler, Nov 29 2007

Keywords

• easy
• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A060293, A052488, A050502-A050504.

Programs

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

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

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