Skip to content
Omnikalc

Harmonic number calculator: H(n), coupon collector, book stack and quicksort

Enter n to get the harmonic number H(n) and its main applications: the draws to collect n coupons, the overhang of a stack of books and the average comparisons of quicksort.

Updated on
Your inputs

Value out of range

Results

Harmonic number H(n) = 1 + 1/2 + ... + 1/n

4.4992

Expected draws to collect n coupons (n × H(n))
225.0
Book stack overhang, in book lengths (H(n) / 2)
2.250
Average comparisons of quicksort (2(n+1)H(n) − 4n)
259
H(n) minus ln(n) (tends to 0.5772)
0.5872

The harmonic number H(n) is the sum 1 + 1/2 + 1/3 + … + 1/n, a number that grows like the logarithm. The harmonic number calculator gives H(n) and three classic uses: the draws to collect n coupons, the overhang of a stack of books and the average comparisons of quicksort.

How the calculation works

  • Enter the number n of terms: for a coupon collection, the number of different coupons, for a stack, the number of books, for a sort, the number of items.
  • The calculator computes the harmonic number H(n) = 1 + 1/2 + 1/3 + … + 1/n with the asymptotic formula ln n + γ + 1/(2n) − 1/(12n²) + 1/(120n⁴), where γ = 0.5772 is the Euler-Mascheroni constant.
  • The formula is accurate to about 8 digits from n = 5, and the error falls fast as n grows.
  • Read the harmonic number and its uses: the coupon collector, the overhang of a stack of books and the average cost of quicksort.

Example

Take n = 50. The harmonic number is H(50) = ln 50 + 0.5772 + 1/100 − 1/30,000 = 4.4992. A collector who wants all 50 different cards from random packs needs on average 50 × 4.4992 = 225.0 draws. A stack of 50 identical books, each balanced on the next, can overhang the table by H(50) / 2 = 2.250 book lengths. A quicksort on 50 items makes on average 2 × 51 × 4.4992 − 200 = 259 comparisons. H(50) − ln 50 is 0.5872, close to the constant of Euler 0.5772.

Why it matters

The calculator helps students of probability, computer science and analysis, and curious people, to compute a harmonic number for a large n without adding all the terms, and to see where it shows up. It is useful for the analysis of algorithms, for estimating the size of a collection, and for the puzzle of the leaning stack.

Good to know

Use the result for n of 5 or more, where the formula is very accurate. For a small n, add the inverses by hand. Remember that the coupon collector result is an average: the real number of draws varies a lot, and the last coupons take the most time, since the final one alone needs about n draws on average.

The coupon collector calculator gives the details of the collection problem with the probabilities, the harmonic mean calculator uses the inverses in an average, the logarithm calculator gives ln n, and the expected value calculator covers the averages of random variables.

Frequently asked questions

What is a harmonic number?

The harmonic number H(n) is the sum of the inverses of the first n integers: 1 + 1/2 + 1/3 + ... + 1/n. It grows without bound, but very slowly, like the natural logarithm: H(n) is about ln n + 0.5772. The sum of the first 1,000 terms is only 7.49, and it takes about 12,367 terms to pass 10, and 1.5 × 10⁴³ terms to reach 100.

Where do harmonic numbers appear?

They appear in the coupon collector problem, where the expected number of draws to get all n coupons is n × H(n). They give the expected number of records in a random sequence, the average cost of quicksort, the overhang of a stack of blocks (the harmonic stacking problem) and the expected time of many random processes. Each time, the sum 1/k comes from a waiting time or a probability of 1/k.

How is H(n) computed without a sum?

For large n, the Euler-Maclaurin formula gives H(n) = ln n + γ + 1/(2n) − 1/(12n²) + 1/(120n⁴) − ..., where γ = 0.5772156649 is the Euler-Mascheroni constant. The calculator uses the first five terms. The error is less than 1/(252 n⁶), which is tiny: at n = 5 the result is 2.283334 against the exact 2.283333.

Does the stack of books really overhang that much?

In theory yes: n identical blocks stacked with the best offsets reach an overhang of H(n) / 2 block lengths, and with 4 blocks, it is already more than one block length. The overhang grows without limit, but very slowly, as half the logarithm of n. In practice, it needs a perfect balance, so the result is the ideal limit, not a recipe for a stable tower.

Was this calculator helpful?

Thanks for your feedback!

Results are estimates provided for information purposes. They do not replace professional advice.