HOME

TheInfoList



OR:

In mathematics, the harmonic series is the
infinite series In mathematics, a series is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. The study of series is a major part of calculus and its generalization, mat ...
formed by summing all positive
unit fraction A unit fraction is a rational number written as a fraction where the numerator is one and the denominator is a positive integer. A unit fraction is therefore the reciprocal of a positive integer, 1/''n''. Examples are 1/1, 1/2, 1/3, 1/4, 1/5, e ...
s: \sum_^\infty\frac = 1 + \frac + \frac + \frac + \frac + \cdots. The first n terms of the series sum to approximately \ln n + \gamma, where \ln is the
natural logarithm The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
and \gamma\approx0.577 is the
Euler–Mascheroni constant Euler's constant (sometimes also called the Euler–Mascheroni constant) is a mathematical constant usually denoted by the lowercase Greek letter gamma (). It is defined as the limiting difference between the harmonic series and the natural lo ...
. Because the logarithm has arbitrarily large values, the harmonic series does not have a finite limit: it is a
divergent series In mathematics, a divergent series is an infinite series that is not convergent, meaning that the infinite sequence of the partial sums of the series does not have a finite limit. If a series converges, the individual terms of the series mu ...
. Its divergence was proven in the 14th century by
Nicole Oresme Nicole Oresme (; c. 1320–1325 – 11 July 1382), also known as Nicolas Oresme, Nicholas Oresme, or Nicolas d'Oresme, was a French philosopher of the later Middle Ages. He wrote influential works on economics, mathematics, physics, astrology ...
using a precursor to the Cauchy condensation test for the convergence of infinite series. It can also be proven to diverge by comparing the sum to an
integral In mathematics, an integral assigns numbers to functions in a way that describes displacement, area, volume, and other concepts that arise by combining infinitesimal data. The process of finding integrals is called integration. Along with ...
, according to the
integral test for convergence In mathematics, the integral test for convergence is a method used to test infinite series of monotonous terms for convergence. It was developed by Colin Maclaurin and Augustin-Louis Cauchy and is sometimes known as the Maclaurin–Cauchy t ...
. Applications of the harmonic series and its partial sums include Euler's proof that there are infinitely many prime numbers, the analysis of the coupon collector's problem on how many random trials are needed to provide a complete range of responses, the connected components of
random graph In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs l ...
s, the block-stacking problem on how far over the edge of a table a stack of blocks can be
cantilevered A cantilever is a rigid structural element that extends horizontally and is supported at only one end. Typically it extends from a flat vertical surface such as a wall, to which it must be firmly attached. Like other structural elements, a canti ...
, and the average case analysis of the
quicksort Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
algorithm.


History

The name of the harmonic series derives from the concept of
overtone An overtone is any resonant frequency above the fundamental frequency of a sound. (An overtone may or may not be a harmonic) In other words, overtones are all pitches higher than the lowest pitch within an individual sound; the fundamental i ...
s or harmonics in music: the
wavelength In physics, the wavelength is the spatial period of a periodic wave—the distance over which the wave's shape repeats. It is the distance between consecutive corresponding points of the same phase on the wave, such as two adjacent crests, tro ...
s of the overtones of a vibrating string are etc., of the string's fundamental wavelength. Every term of the harmonic series after the first is the
harmonic mean In mathematics, the harmonic mean is one of several kinds of average, and in particular, one of the Pythagorean means. It is sometimes appropriate for situations when the average rate is desired. The harmonic mean can be expressed as the recipr ...
of the neighboring terms, so the terms form a harmonic progression; the phrases ''harmonic mean'' and ''harmonic progression'' likewise derive from music. Beyond music, harmonic sequences have also had a certain popularity with architects. This was so particularly in the
Baroque The Baroque (, ; ) is a style of architecture, music, dance, painting, sculpture, poetry, and other arts that flourished in Europe from the early 17th century until the 1750s. In the territories of the Spanish and Portuguese empires including th ...
period, when architects used them to establish the proportions of floor plans, of elevations, and to establish harmonic relationships between both interior and exterior architectural details of churches and palaces. The divergence of the harmonic series was first proven in 1350 by
Nicole Oresme Nicole Oresme (; c. 1320–1325 – 11 July 1382), also known as Nicolas Oresme, Nicholas Oresme, or Nicolas d'Oresme, was a French philosopher of the later Middle Ages. He wrote influential works on economics, mathematics, physics, astrology ...
. Oresme's work, and the contemporaneous work of
Richard Swineshead Richard Swineshead (also Suisset, Suiseth, etc.; fl. c. 1340 – 1354) was an English mathematician, logician, and natural philosopher. He was perhaps the greatest of the Oxford Calculators of Merton College, where he was a fellow certainly by 1344 ...
on a different series, marked the first appearance of infinite series other than the
geometric series In mathematics, a geometric series is the sum of an infinite number of terms that have a constant ratio between successive terms. For example, the series :\frac \,+\, \frac \,+\, \frac \,+\, \frac \,+\, \cdots is geometric, because each su ...
in mathematics. However, this achievement fell into obscurity. Additional proofs were published in the 17th century by
Pietro Mengoli Pietro Mengoli (1626, Bologna – June 7, 1686, Bologna) was an Italian mathematician and clergyman from Bologna, where he studied with Bonaventura Cavalieri at the University of Bologna, and succeeded him in 1647. He remained as professor there f ...
and by
Jacob Bernoulli Jacob Bernoulli (also known as James or Jacques; – 16 August 1705) was one of the many prominent mathematicians in the Bernoulli family. He was an early proponent of Leibnizian calculus and sided with Gottfried Wilhelm Leibniz during the Le ...
. Bernoulli credited his brother
Johann Bernoulli Johann Bernoulli (also known as Jean or John; – 1 January 1748) was a Swiss mathematician and was one of the many prominent mathematicians in the Bernoulli family. He is known for his contributions to infinitesimal calculus and educating Leo ...
for finding the proof, and it was later included in Johann Bernoulli's collected works. The partial sums of the harmonic series were named
harmonic number In mathematics, the -th harmonic number is the sum of the reciprocals of the first natural numbers: H_n= 1+\frac+\frac+\cdots+\frac =\sum_^n \frac. Starting from , the sequence of harmonic numbers begins: 1, \frac, \frac, \frac, \frac, \dot ...
s, and given their usual notation H_n, in 1968 by
Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sci ...
.


Definition and divergence

The harmonic series is the infinite series \sum_^\infty\frac = 1 + \frac + \frac + \frac + \frac + \cdots in which the terms are all of the positive
unit fraction A unit fraction is a rational number written as a fraction where the numerator is one and the denominator is a positive integer. A unit fraction is therefore the reciprocal of a positive integer, 1/''n''. Examples are 1/1, 1/2, 1/3, 1/4, 1/5, e ...
s. It is a
divergent series In mathematics, a divergent series is an infinite series that is not convergent, meaning that the infinite sequence of the partial sums of the series does not have a finite limit. If a series converges, the individual terms of the series mu ...
: as more terms of the series are included in
partial sum In mathematics, a series is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. The study of series is a major part of calculus and its generalization, mat ...
s of the series, the values of these partial sums grow arbitrarily large, beyond any finite limit. Because it is a divergent series, it should be interpreted as a formal sum, an abstract mathematical expression combining the unit fractions, rather than as something that can be evaluated to a numeric value. There are many different proofs of the divergence of the harmonic series, surveyed in a 2006 paper by S. J. Kifowit and T. A. Stamps. Two of the best-known are listed below.


Comparison test

One way to prove divergence is to compare the harmonic series with another divergent series, where each denominator is replaced with the next-largest
power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negative ...
: \begin 1 & + \frac && + \frac && + \frac && + \frac && + \frac && + \frac && + \frac && + \frac && + \cdots \\ pt \geq 1 & + \frac && + \frac && + \frac && + \frac && + \frac && + \frac && + \frac && + \frac && + \cdots \\ pt \end Grouping equal terms shows that the second series diverges (because every grouping of convergent series is only convergent): \begin & 1 + \left(\frac\right) + \left(\frac + \frac\right) + \left(\frac + \frac + \frac + \frac\right) + \left(\frac + \cdots + \frac\right) + \cdots \\ pt = & 1 + \frac + \frac + \frac + \frac + \cdots. \end Because each term of the harmonic series is greater than or equal to the corresponding term of the second series (and the terms are all positive), it follows (by the comparison test) that the harmonic series diverges as well. The same argument proves more strongly that, for every
positive Positive is a property of positivity and may refer to: Mathematics and science * Positive formula, a logical formula not containing negation * Positive number, a number that is greater than 0 * Plus sign, the sign "+" used to indicate a posi ...
\sum_^ \frac \geq 1 + \frac This is the original proof given by
Nicole Oresme Nicole Oresme (; c. 1320–1325 – 11 July 1382), also known as Nicolas Oresme, Nicholas Oresme, or Nicolas d'Oresme, was a French philosopher of the later Middle Ages. He wrote influential works on economics, mathematics, physics, astrology ...
in around 1350. The Cauchy condensation test is a generalization of this argument.


Integral test

It is possible to prove that the harmonic series diverges by comparing its sum with an
improper integral In mathematical analysis, an improper integral is the limit of a definite integral as an endpoint of the interval(s) of integration approaches either a specified real number or positive or negative infinity; or in some instances as both endpoi ...
. Specifically, consider the arrangement of rectangles shown in the figure to the right. Each rectangle is 1 unit wide and \tfrac1n units high, so if the harmonic series converged then the total area of the rectangles would be the sum of the harmonic series. The curve y=\tfrac1x stays entirely below the upper boundary of the rectangles, so the area under the curve (in the range of x from one to infinity that is covered by rectangles) would be less than the area of the union of the rectangles. However, the area under the curve is given by a divergent
improper integral In mathematical analysis, an improper integral is the limit of a definite integral as an endpoint of the interval(s) of integration approaches either a specified real number or positive or negative infinity; or in some instances as both endpoi ...
, \int_1^\infty\frac\,dx = \infty. Because this integral does not converge, the sum cannot converge either. Replacing each rectangle by the next one in the sequence would produce a sequence of rectangles whose boundary lies below the curve rather than above it. This shows that the partial sums of the harmonic series differ from the integral by an amount that is bounded above and below by the unit area of the first rectangle: \int_1^\frac1x\,dx<\sum_^N\frac1i<\int_1^\frac1x\,dx+1. Generalizing this argument, any infinite sum of values of a monotone decreasing positive function (like the harmonic series) has partial sums that are within a bounded distance of the values of the corresponding integrals. Therefore, the sum converges if and only if the integral over the same range of the same function converges. When this equivalence is used to check the convergence of a sum by replacing it with an easier integral, it is known as the
integral test for convergence In mathematics, the integral test for convergence is a method used to test infinite series of monotonous terms for convergence. It was developed by Colin Maclaurin and Augustin-Louis Cauchy and is sometimes known as the Maclaurin–Cauchy t ...
.


Partial sums

Adding the first n terms of the harmonic series produces a
partial sum In mathematics, a series is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. The study of series is a major part of calculus and its generalization, mat ...
, called a
harmonic number In mathematics, the -th harmonic number is the sum of the reciprocals of the first natural numbers: H_n= 1+\frac+\frac+\cdots+\frac =\sum_^n \frac. Starting from , the sequence of harmonic numbers begins: 1, \frac, \frac, \frac, \frac, \dot ...
and H_n = \sum_^n \frac.


Growth rate

These numbers grow very slowly, with
logarithmic growth In mathematics, logarithmic growth describes a phenomenon whose size or cost can be described as a logarithm function of some input. e.g. ''y'' = ''C'' log (''x''). Note that any logarithm base can be used, since one can be convert ...
, as can be seen from the integral test. More precisely, by the
Euler–Maclaurin formula In mathematics, the Euler–Maclaurin formula is a formula for the difference between an integral and a closely related sum. It can be used to approximate integrals by finite sums, or conversely to evaluate finite sums and infinite series using ...
, H_n = \ln n + \gamma + \frac - \varepsilon_n where \gamma\approx 0.5772 is the
Euler–Mascheroni constant Euler's constant (sometimes also called the Euler–Mascheroni constant) is a mathematical constant usually denoted by the lowercase Greek letter gamma (). It is defined as the limiting difference between the harmonic series and the natural lo ...
and 0\le\varepsilon_n\le 1/8n^2 which approaches 0 as n goes to infinity.


Divisibility

No harmonic numbers are integers, except for One way to prove that H_n is not an integer is to consider the highest
power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negative ...
2^k in the range from If M is the
least common multiple In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bo ...
of the numbers from then H_k can be rewritten as a sum of fractions with equal denominators H_n=\sum_^n \tfrac in which only one of the numerators, is odd and the rest are even, and M is itself even. Therefore, the result is a fraction with an odd numerator and an even denominator, which cannot be an integer. More strongly, any sequence of consecutive integers has a unique member divisible by a greater power of two than all the other sequence members, from which it follows by the same argument that no two harmonic numbers differ by an integer. Another proof that the harmonic numbers are not integers observes that the denominator of H_n must be divisible by all
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s greater than n/2, and uses
Bertrand's postulate In number theory, Bertrand's postulate is a theorem stating that for any integer n > 3, there always exists at least one prime number p with :n < p < 2n - 2. A less restrictive formulation is: for every n > 1, there is always ...
to prove that this set of primes is non-empty. The same argument implies more strongly that, except for H_1=1, H_2=1.5, and H_6=2.45, no harmonic number can have a
terminating decimal A repeating decimal or recurring decimal is decimal representation of a number whose digits are periodic (repeating its values at regular intervals) and the infinitely repeated portion is not zero. It can be shown that a number is rational if a ...
representation. It has been conjectured that every prime number divides the numerators of only a finite subset of the harmonic numbers, but this remains unproven.


Interpolation

The
digamma function In mathematics, the digamma function is defined as the logarithmic derivative of the gamma function: :\psi(x)=\frac\ln\big(\Gamma(x)\big)=\frac\sim\ln-\frac. It is the first of the polygamma functions. It is strictly increasing and strictl ...
is defined as the
logarithmic derivative In mathematics, specifically in calculus and complex analysis, the logarithmic derivative of a function ''f'' is defined by the formula \frac where f' is the derivative of ''f''. Intuitively, this is the infinitesimal relative change in ''f' ...
of the
gamma function In mathematics, the gamma function (represented by , the capital letter gamma from the Greek alphabet) is one commonly used extension of the factorial function to complex numbers. The gamma function is defined for all complex numbers except t ...
\psi(x)=\frac\ln\big(\Gamma(x)\big)=\frac. Just as the gamma function provides a continuous
interpolation In the mathematical field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points. In engineering and science, one often has a ...
of the
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) ...
s, the digamma function provides a continuous interpolation of the harmonic numbers, in the sense that This equation can be used to extend the definition to harmonic numbers with rational indices.


Applications

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


Crossing a desert

The
jeep problem The jeep problem, desert crossing problem or exploration problem"Exploration problems. Another common question is concerned with the maximum distance into a desert which could be reached from a frontier settlement by an explorer capable of carryi ...
or desert-crossing problem is included in a 9th-century problem collection by
Alcuin Alcuin of York (; la, Flaccus Albinus Alcuinus; 735 – 19 May 804) – also called Ealhwine, Alhwin, or Alchoin – was a scholar, clergyman, poet, and teacher from York, Northumbria. He was born around 735 and became the student o ...
, ''
Propositiones ad Acuendos Juvenes The medieval Latin manuscript ''Propositiones ad Acuendos Juvenes'' ( en, Problems to Sharpen the Young) is one of the earliest known collections of recreational mathematics problems. 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 In physics, the center of mass of a distribution of mass in space (sometimes referred to as the balance point) is the unique point where the weighted relative position of the distributed mass sums to zero. This is the point to which a force may ...
of the top two block 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, 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 Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ...
observed that, as a
formal sum In mathematics, a formal sum, formal series, or formal linear combination may be: *In group theory, an element of a free abelian group, a sum of finitely many elements from a given basis set multiplied by integer coefficients. *In linear algebra, an ...
, the harmonic series is equal to an
Euler product In number theory, an Euler product is an expansion of a Dirichlet series into an infinite product indexed by prime numbers. The original such product was given for the sum of all positive integers raised to a certain power as proven by Leonhard Eul ...
in which each term comes from a
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
: \sum_^\frac=\prod_\left(1+\frac1p+\frac1+\cdots\right)=\prod_ \frac, where \mathbb denotes the set of prime numbers. The left equality comes from applying the
distributive law In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmetic ...
to the product and recognizing the resulting terms as the
prime factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are su ...
s of the terms in the harmonic series, and the right equality uses the standard formula for a
geometric series In mathematics, a geometric series is the sum of an infinite number of terms that have a constant ratio between successive terms. For example, the series :\frac \,+\, \frac \,+\, \frac \,+\, \frac \,+\, \cdots is geometric, because each su ...
. The product is divergent, just like the sum, but if it converged one could take logarithms and obtain \ln \prod_ \frac=\sum_\ln\frac=\sum_\left(\frac1p+\frac1+\frac1+\cdots\right)=\sum_\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 In number theory, Mertens' theorems are three 1874 results related to the density of prime numbers proved by Franz Mertens.F. Mertens. J. reine angew. Math. 78 (1874), 46–6Ein Beitrag zur analytischen Zahlentheorie/ref> "Mertens' theorem" may ...
, and can be seen as a precursor to the
prime number theorem In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying ...
. Another problem in
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathe ...
closely related to the harmonic series concerns the average number of
divisor In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
s of the numbers in a range from 1 to n, formalized as the average order of the
divisor function In mathematics, and specifically in number theory, a divisor function is an arithmetic function related to the divisors of an integer. When referred to as ''the'' divisor function, it counts the ''number of divisors of an integer'' (includi ...
, \frac1n\sum_^n\left\lfloor\fraci\right\rfloor\le\frac1n\sum_^n\fraci=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 Johann Peter Gustav Lejeune Dirichlet (; 13 February 1805 – 5 May 1859) was a German mathematician who made deep contributions to number theory (including creating the field of analytic number theory), and to the theory of Fourier series and ...
showed more precisely that the average number of divisors is \ln n+2\gamma-1+O(1/\sqrt) (expressed in
big O notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Land ...
). 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 card A trading card (or collectible card) is a small card, usually made out of paperboard or thick paper, which usually contains an image of a certain person, place or thing (fictional or real) and a short description of the picture, along with other ...
s and the completion of
parkrun Parkrun (stylised as parkrun) is a collection of events for walkers, runners and volunteers that take place every Saturday morning at more than 2,000 locations in 23 countries across six continents. Junior Parkrun (stylised as junior 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 Quality control (QC) is a process by which entities review the quality of all factors involved in production. ISO 9000 defines quality control as "a part of quality management focused on fulfilling quality requirements". This approach places ...
, and the connectivity of
random graph In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs l ...
s. 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 Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
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 In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case comp ...
(with the assumption that all input permutations are equally likely) or in its
expected time In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case comp ...
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. 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_^n\sum_^\frac2=\sum_^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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
.


Related series


Alternating harmonic series

The series \sum_^\infty \frac = 1 - \frac + \frac - \frac + \frac - \cdots is known as the alternating harmonic series. It is
conditionally convergent In mathematics, a series or integral is said to be conditionally convergent if it converges, but it does not converge absolutely. Definition More precisely, a series of real numbers \sum_^\infty a_n is said to converge conditionally if \lim_\,\ ...
by the
alternating series test In mathematical analysis, the alternating series test is the method used to show that an alternating series is convergent when its terms (1) decrease in absolute value, and (2) approach zero in the limit. The test was used by Gottfried Leibniz ...
, but not
absolutely convergent In mathematics, an infinite series of numbers is said to converge absolutely (or to be absolutely convergent) if the sum of the absolute values of the summands is finite. More precisely, a real or complex series \textstyle\sum_^\infty a_n is sa ...
. Its sum is the
natural logarithm of 2 The decimal value of the natural logarithm of 2 is approximately :\ln 2 \approx 0.693\,147\,180\,559\,945\,309\,417\,232\,121\,458. The logarithm of 2 in other bases is obtained with the formula :\log_b 2 = \frac. The common logarithm in particula ...
. Explicitly, the asymptotic expansion of the series is \frac - \frac +\cdots + \frac - \frac = H_ - H_n = \ln 2 - \frac + O(n^) Using alternating signs with only odd unit fractions produces a related series, the Leibniz formula for \sum_^\infty \frac = 1 - \frac + \frac - \frac + \cdots = \frac.


Riemann zeta function

The
Riemann zeta function The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
is defined for real x>1 by the convergent series \zeta(x)=\sum_^\frac=\frac1+\frac1+\frac1+\cdots, which for x=1 would be the harmonic series. It can be extended by
analytic continuation In complex analysis, a branch of mathematics, analytic continuation is a technique to extend the domain of definition of a given analytic function. Analytic continuation often succeeds in defining further values of a function, for example in a ...
to a
holomorphic function In mathematics, a holomorphic function is a complex-valued function of one or more complex variables that is complex differentiable in a neighbourhood of each point in a domain in complex coordinate space . The existence of a complex deriva ...
on all complex numbers where the extended function has a simple pole. Other important values of the zeta function include the solution to the
Basel problem The Basel problem is a problem in mathematical analysis with relevance to number theory, concerning an infinite sum of inverse squares. It was first posed by Pietro Mengoli in 1650 and solved by Leonhard Euler in 1734, and read on 5 December 1735 ...
,
Apéry's constant In mathematics, Apéry's constant is the sum of the reciprocals of the positive cubes. That is, it is defined as the number : \begin \zeta(3) &= \sum_^\infty \frac \\ &= \lim_ \left(\frac + \frac + \cdots + \frac\right), \end ...
proved by
Roger Apéry Roger Apéry (; 14 November 1916, Rouen – 18 December 1994, Caen) was a French mathematician most remembered for Apéry's theorem, which states that is an irrational number. Here, denotes the Riemann zeta function. Biography Apéry was born ...
to be an
irrational number In mathematics, the irrational numbers (from in- prefix assimilated to ir- (negative prefix, privative) + rational) are all the real numbers that are not rational numbers. That is, irrational numbers cannot be expressed as the ratio of two inte ...
, and the "critical line" of complex numbers with conjectured by the Riemann hypothesis to be the only values other than negative integers where the function can be zero.


Random harmonic series

The random harmonic series is \sum_^\frac, where the values s_n are
independent and identically distributed random variables In probability theory and statistics, a collection of random variables is independent and identically distributed if each random variable has the same probability distribution as the others and all are mutually independent. This property is usual ...
that take the two values +1 and -1 with equal It converges with probability 1, as can be seen by using the Kolmogorov three-series theorem or of the closely related Kolmogorov maximal inequality. The sum of the series is a
random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...
whose
probability density function In probability theory, a probability density function (PDF), or density of a continuous random variable, is a function whose value at any given sample (or point) in the sample space (the set of possible values taken by the random variable) can ...
is for values between and decreases to near-zero for values greater or less Intermediate between these ranges, at the the probability density is \tfrac18-\varepsilon for a nonzero but very small value


Depleted harmonic series

The depleted harmonic series where all of the terms in which the digit 9 appears anywhere in the denominator are removed can be shown to converge to the value . In fact, when all the terms containing any particular string of digits (in any base) are removed, the series converges.


References


External links

* {{Series (mathematics) Divergent series