Editing Harmonic series (mathematics) (section)

==Applications==
Many well-known mathematical problems have solutions involving the harmonic series and its partial sums.

===Crossing a desert===
{{main|Jeep problem}}
[[File:Jeep problem 1.png|thumb|Solution to the jeep problem for <math>n=3</math>, showing the amount of fuel in each depot and in the jeep at each step]]
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.{{r|alcuin}} The problem asks how far into the desert a jeep can travel and return, starting from a base with <math>n</math> 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 <math>\tfrac{r}{2n}, \tfrac{r}{2(n-1)}, \tfrac{r}{2(n-2)}, \dots</math> from the starting point and each other, where <math>r</math> 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 <math>n</math>th trip is <math display=block>\frac{r}{2n}+\frac{r}{2(n-1)}+\frac{r}{2(n-2)}+\cdots=\frac{r}{2} H_n,</math>
where <math>H_n</math> is the {{nowrap|<math>n</math>th}} harmonic number. The divergence of the harmonic series implies that crossings of any length are possible with enough fuel.{{r|gale}}

For instance, for Alcuin's version of the problem, <math>r=30</math>: 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 {{convert|2.3|km|mi}}. The problem has <math>n=3</math>: 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 <math>\tfrac{30}{2}\bigl(\tfrac13+\tfrac12+\tfrac11)=27.5</math> 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 a slightly different question, how much grain can be transported a distance of 30 leucas without a final return trip, and either strands some camels in the desert or fails to account for the amount of grain consumed by a camel on its return trips.{{r|alcuin}}

===Stacking blocks===
{{main|Block-stacking problem}}
[[File:Block_stacking_problem.svg|thumb|250px|The [[block-stacking problem]]: 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 <math>n</math> 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 <math>\tfrac12</math> 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 <math>\tfrac12\cdot\tfrac12</math> 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 <math>\tfrac12\cdot\tfrac13</math> 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 <math>n</math> blocks in such a way that they extend <math>\tfrac12 H_n</math> lengths beyond the table, where <math>H_n</math> is the {{nowrap|<math>n</math>th}} harmonic number.{{r|graham|sharp}} The divergence of the harmonic series implies that there is no limit on how far beyond the table the block stack can extend.{{r|sharp}} 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.{{r|overhang}}

===Counting primes and divisors===
{{main|Divergence of the sum of the reciprocals of the primes}}
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]]: <math display=block>\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},</math> where <math>\mathbb{P}</math> 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 factorization]]s 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 <math display=block>\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.</math>
Here, each logarithm is replaced by its [[Taylor series]], and the constant <math>K</math> 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 [[Euclid's theorem|there are infinitely many prime numbers]], because a finite sum cannot diverge.{{r|euler}} 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.{{r|rubsal}} 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]],{{r|pollack}} and can be seen as a precursor to the [[prime number theorem]].{{r|rubsal}}

Another problem in [[number theory]] closely related to the harmonic series concerns the average number of [[divisor]]s of the numbers in a range from 1 to <math>n</math>, formalized as the [[Average order of an arithmetic function|average order]] of the [[divisor function]],
<math display=block>\frac1n\sum_{i=1}^n\left\lfloor\frac{n}i\right\rfloor\le\frac1n\sum_{i=1}^n\frac{n}i=H_n.</math>
The operation of rounding each term in the harmonic series to the next smaller integer multiple of <math>\tfrac1n</math> 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 <math>\ln n+2\gamma-1+O(1/\sqrt{n})</math> (expressed in [[big O notation]]). Bounding the final error term more precisely remains an open problem, known as [[Dirichlet's divisor problem]].{{r|tsang}}

===Collecting coupons===
{{main|Coupon collector's problem}}
[[File:Coupon collector problem.svg|thumb|Graph of number of items versus the expected number of trials needed to collect all items]]
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 card]]s{{r|maunsell|gerke}} 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.{{r|parkrun}} More serious applications of this problem include sampling all variations of a manufactured product for its [[quality control]],{{r|luko}} and the [[Connectivity (graph theory)|connectivity]] of [[random graph]]s.{{r|frikar}} In situations of this form, once there are <math>k</math> items remaining to be collected out of a total of <math>n</math> equally-likely items, the probability of collecting a new item in a single random choice is <math>k/n</math> and the expected number of random choices needed until a new item is collected {{nowrap|is <math>n/k</math>.}} Summing over all values of <math>k</math> from <math>n</math> {{nowrap|down to 1}} shows that the total expected number of random choices needed to collect all items {{nowrap|is <math>nH_n</math>,}} where <math>H_n</math> is the {{nowrap|<math>n</math>th}} harmonic number.{{r|isaac}}

===Analyzing algorithms===
{{main|Quicksort}}
[[File:Sorting quicksort anim.gif|thumb|Animation of the average-case version of quicksort, with recursive subproblems indicated by shaded arrows and with pivots (red items and blue lines) chosen as the last item in each subproblem]]
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 <math>x</math> and <math>y</math> are separated by <math>k</math> other items, then the algorithm will make a comparison between <math>x</math> and <math>y</math> only when, as the recursion progresses, it picks <math>x</math> or <math>y</math> as a pivot before picking any of the other <math>k</math> items between them. Because each of these <math>k+2</math> items is equally likely to be chosen first, this happens with probability <math>\tfrac2{k+2}</math>. 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{{r|clrs}} <math display=block>\sum_{i=2}^n\sum_{k=0}^{i-2}\frac2{k+2}=\sum_{i=1}^{n-1}2H_i=O(n\log n).</math>
The divergence of the harmonic series corresponds in this application to the fact that, in the [[comparison sort|comparison model of sorting]] used for quicksort, it is not possible to sort in [[linear time]].{{sfnp|Cormen|Leiserson|Rivest|Stein|2009|loc=Section 8.1, "Lower bounds for sorting", pp. 191–193}}