Writing down harmonic numbers

(832) 422-8646

Contact

The nth harmonic number is the sum of the reciprocals of the first n positive integers.

Hn = 1 + 1/2 + 1/3 + 1/4 + … + 1/n

The product of all the denominators is n!, so you could write Hn as a fraction

Hn = p/q

where p = n! Hn is an integer and q = n!.

While p/q is a way to write Hn as a fraction, it’s not the most efficient because p and n! will have common factors.

If we write Hn as a reduced fraction, the denominator will be the least common multiple of the integers 1 through n. 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 base b it would have around

n/log(b)

digits.

The numerator will be exp(n) Hn, and since Hn is asymptotically log(n) + γ, the numerator for large n 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 for n = 50. The 50th harmonic number is

H50 = 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 Fraction

def bits(n):<br>H = sum(Fraction(i, i+1) for i in range(1, n+1))<br>p, q = H.numerator, H.denominator<br># subtract 2 because bin returns a string starting with 0b.<br>return len(bin(p)) - 2, len(bin(q)) - 2

print(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.

Update : See the next post for plots as a function of n.

Related posts

Computing harmonic numbers

Sums of consecutive reciprocals

AM over GM

Leave a Reply<br>Your email address will not be published. Required fields are marked *<br>Comment *<br>Name *

Email *

Website

Search for:

John D. Cook, PhD

My colleagues and I have decades of consulting experience helping companies solve complex problems involving data privacy, applied math, and statistics.

Let’s talk. We look forward to exploring the opportunity to help your company too.