Writing down harmonic numbers

Thenth harmonic number is the sum of the reciprocals of the firstn positive integers.

H_n = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n

The product of all the denominators isn!, so you could write H_n as a fraction

H_n = p/q

wherep =n! H_n is an integer and q =n!.

While p/qis a way to write H_n as a fraction, it's not the most efficient becausep andn! will have common factors.

If we write H_n as a reduced fraction, the denominator will be the least common multiple of the integers 1 throughn. That number is asymptotically exp(n). That estimate follows from the prime number theorem.

So for large n the denominator will be roughly exp(n), and in baseb it would have around

n/log(b)

digits.

The numerator will be exp(n) H_n, and since H_n is asymptotically log(n) + , the numerator for largen will be roughly

exp(n) (log(n) + )

and will have around

(n + log log(n) ) / log(b)

digits.

Let's see how well our asymptotic estimates work forn = 50. The 50th harmonic number is

H₅₀ = 13943237577224054960759 / 3099044504245996706400.

This fraction has 23 digits in the numerator and 22 in the denominator. We would have predicted around

(50 + log(log(50)))/log(10) = 22.3

digits in the numerator and

50/log(10) = 21.7

digits in the denominator.

Let's try a larger example, looking at the 1000th harmonic number in binary. We'll use the following Python code.

from fractions import Fractiondef bits(n): H = sum(Fraction(i, i+1) for i in range(1, n+1)) p, q = H.numerator, H.denominator # subtract 2 because bin returns a string starting with 0b. return len(bin(p)) - 2, len(bin(q)) - 2print(bits(1000))

This returns 1448 and 1438. We would have estimated

(1000 + log(log(1000)))/log(2) = 1445.4

bits in the numerator and

1000/log(2) = 1442.7

bits in the denominator.

Related posts

• Computing harmonic numbers
• Sums of consecutive reciprocals
• AM over GM

The post Writing down harmonic numbers first appeared on John D. Cook.