Many well-known mathematical problems have solutions involving the harmonic series and its partial sums.
Crossing a desert The
jeep problem or desert-crossing problem is included in a 9th-century problem collection by
Alcuin,
Propositiones ad Acuendos Juvenes (formulated in terms of camels rather than jeeps), but with an incorrect solution. The problem asks how far into the desert a jeep can travel and return, starting from a base with n loads of fuel, by carrying some of the fuel into the desert and leaving it in depots. The optimal solution involves placing depots spaced at distances \tfrac{r}{2n}, \tfrac{r}{2(n-1)}, \tfrac{r}{2(n-2)}, \dots from the starting point and each other, where r is the range of distance that the jeep can travel with a single load of fuel. On each trip out and back from the base, the jeep places one more depot, refueling at the other depots along the way, and placing as much fuel as it can in the newly placed depot while still leaving enough for itself to return to the previous depots and the base. Therefore, the total distance reached on the nth trip is \frac{r}{2n}+\frac{r}{2(n-1)}+\frac{r}{2(n-2)}+\cdots=\frac{r}{2} H_n, where H_n is the harmonic number. The divergence of the harmonic series implies that crossings of any length are possible with enough fuel. For instance, for Alcuin's version of the problem, r=30: a camel can carry 30 measures of grain and can travel one leuca while eating a single measure, where a leuca is a unit of distance roughly equal to . The problem has n=3: there are 90 measures of grain, enough to supply three trips. For the standard formulation of the desert-crossing problem, it would be possible for the camel to travel \tfrac{30}{2}\bigl(\tfrac13+\tfrac12+\tfrac11)=27.5 leucas and return, by placing a grain storage depot 5 leucas from the base on the first trip and 12.5 leucas from the base on the second trip. However, Alcuin instead asks how much grain can be transported a distance of 30 leucas without a final return trip, either stranding some camels in the desert or failing to account for the amount of grain consumed by camels on their return trips.
Stacking blocks : blocks aligned according to the harmonic series can overhang the edge of a table by the harmonic numbers In the
block-stacking problem, one must place a pile of n identical rectangular blocks, one per layer, so that they hang as far as possible over the edge of a table without falling. The top block can be placed with \tfrac12 of its length extending beyond the next lower block. If it is placed in this way, the next block down needs to be placed with at most \tfrac12\cdot\tfrac12 of its length extending beyond the next lower block, so that the
center of mass of the top two blocks is supported and they do not topple. The third block needs to be placed with at most \tfrac12\cdot\tfrac13 of its length extending beyond the next lower block, so that the center of mass of the top three blocks is supported and they do not topple, and so on. In this way, it is possible to place the n blocks in such a way that they extend \tfrac12 H_n lengths beyond the table, where H_n is the harmonic number. The divergence of the harmonic series implies that there is no limit on how far beyond the table the block stack can extend. For stacks with one block per layer, no better solution is possible, but significantly more overhang can be achieved using stacks with more than one block per layer.
Counting primes and divisors In 1737,
Leonhard Euler observed that, as a
formal sum, the harmonic series is equal to an
Euler product in which each term comes from a
prime number: \sum_{i=1}^{\infty}\frac{1}{i}=\prod_{p\in\mathbb{P}}\left(1+\frac1p+\frac1{p^2}+\cdots\right)=\prod_{p\in\mathbb{P}} \frac{1}{1-1/p}, where \mathbb{P} denotes the set of prime numbers. The left equality comes from applying the
distributive law to the product and recognizing the resulting terms as the
prime factorizations of the terms in the harmonic series, and the right equality uses the standard formula for a
geometric series. The product is divergent, just like the sum, but if it converged one could take logarithms and obtain \ln \prod_{p\in\mathbb{P}} \frac{1}{1-1/p}=\sum_{p\in\mathbb{P}}\ln\frac{1}{1-1/p}=\sum_{p\in\mathbb{P}}\left(\frac1p+\frac1{2p^2}+\frac1{3p^3}+\cdots\right)=\sum_{p\in\mathbb{P}}\frac1p+K. Here, each logarithm is replaced by its
Taylor series, and the constant K on the right is the evaluation of the convergent series of terms with exponent greater than one. It follows from these manipulations that the sum of reciprocals of primes, on the right hand of this equality, must diverge, for if it converged these steps could be reversed to show that the harmonic series also converges, which it does not. An immediate corollary is that
there are infinitely many prime numbers, because a finite sum cannot diverge. Although Euler's work is not considered adequately rigorous by the standards of modern mathematics, it can be made rigorous by taking more care with limits and error bounds. Euler's conclusion that the partial sums of reciprocals of primes grow as a
double logarithm of the number of terms has been confirmed by later mathematicians as one of
Mertens' theorems, and can be seen as a precursor to the
prime number theorem. Another problem in
number theory closely related to the harmonic series concerns the average number of
divisors of the numbers in a range from 1 to n, formalized as the
average order of the
divisor function, \frac1n\sum_{i=1}^n\left\lfloor\frac{n}i\right\rfloor\le\frac1n\sum_{i=1}^n\frac{n}i=H_n. The operation of rounding each term in the harmonic series to the next smaller integer multiple of \tfrac1n causes this average to differ from the harmonic numbers by a small constant, and
Peter Gustav Lejeune Dirichlet showed more precisely that the average number of divisors is \ln n+2\gamma-1+O(1/\sqrt{n}) (expressed in
big O notation). Bounding the final error term more precisely remains an open problem, known as
Dirichlet's divisor problem.
Collecting coupons Several common games or recreations involve repeating a random selection from a set of items until all possible choices have been selected; these include the collection of
trading cards and the completion of
parkrun bingo, in which the goal is to obtain all 60 possible numbers of seconds in the times from a sequence of running events. More serious applications of this problem include sampling all variations of a manufactured product for its
quality control, and the
connectivity of
random graphs. In situations of this form, once there are k items remaining to be collected out of a total of n equally-likely items, the probability of collecting a new item in a single random choice is k/n and the expected number of random choices needed until a new item is collected Summing over all values of k from n shows that the total expected number of random choices needed to collect all items where H_n is the harmonic number.
Analyzing algorithms The
quicksort algorithm for sorting a set of items can be analyzed using the harmonic numbers. The algorithm operates by choosing one item as a "pivot", comparing it to all the others, and recursively sorting the two subsets of items whose comparison places them before the pivot and after the pivot. In either its
average-case complexity (with the assumption that all input permutations are equally likely) or in its
expected time analysis of worst-case inputs with a random choice of pivot, all of the items are equally likely to be chosen as the pivot. For such cases, one can compute the probability that two items are ever compared with each other, throughout the recursion, as a function of the number of other items that separate them in the final sorted order. If items x and y are separated by k other items, then the algorithm will make a comparison between x and y only when, as the recursion progresses, it picks x or y as a pivot before picking any of the other k items between them. Because each of these k+2 items is equally likely to be chosen first, this happens with probability \tfrac2{k+2}. The total expected number of comparisons, which controls the total running time of the algorithm, can then be calculated by summing these probabilities over all pairs, giving \sum_{i=2}^n\sum_{k=0}^{i-2}\frac2{k+2}=\sum_{i=1}^{n-1}2H_i=O(n\log n). The divergence of the harmonic series corresponds in this application to the fact that, in the
comparison model of sorting used for quicksort, it is not possible to sort in
linear time. ==Related series==