Harmonic number
In mathematics, the -th harmonic number is the sum of the reciprocals of the first natural numbers: formula_1 Starting from , the sequence of harmonic numbers begins: formula_2 Harmonic numbers are related to the harmonic mean in that the -th harmonic number is also times the reciprocal of the harmonic mean of the first positive integers. Harmonic numbers have been studied since antiquity and are important in various branches of number theory. They are sometimes loosely termed harmonic series, are closely related to the Riemann zeta function, and appear in the expressions of various special functions. The harmonic numbers  roughly approximate the natural logarithm function and thus the associated harmonic series grows without limit, albeit slowly. In 1737, Leonhard Euler used the divergence of the harmonic series to provide a new proof of the infinity of prime numbers. His work was extended into the complex plane by Bernhard Riemann in 1859, leading directly to the celebrated Riemann hypothesis about the distribution of prime numbers. When the value of a large quantity of items has a Zipf's law distribution, the total value of the most-valuable items is proportional to the -th harmonic number. This leads to a variety  of surprising conclusions regarding the long tail and the theory of network value. Bertrand's postulate implies that, except for the case , the harmonic numbers are never integers. Identities involving harmonic numbers. By definition, the harmonic numbers satisfy the recurrence relation formula_3 The harmonic numbers are connected to the Stirling numbers of the first kind by the relation formula_4 The functions formula_5 satisfy the property formula_6 In particular formula_7 is an integral of the logarithmic function. The harmonic numbers satisfy the series identities formula_8 and formula_9 These two results are closely analogous to the corresponding integral results formula_10 and formula_11  Identities involving. There are several infinite summations involving harmonic numbers and powers of : formula_12 formula_13 formula_14 formula_15 Calculation. An integral representation given by Euler is formula_16 The equality above is straightforward by the simple algebraic identity formula_17 Using the substitution , another expression for is formula_18 The th harmonic number is about as large as the natural logarithm of . The reason is that the sum is approximated by the integral formula_19 whose value is . The values of the sequence decrease monotonically towards the limit formula_20 where is the Euler–Mascheroni constant. The corresponding asymptotic expansion is formula_21 where are the Bernoulli  numbers. Generating functions. A generating function for the harmonic numbers is formula_22 where ln("z") is the natural logarithm. An exponential generating function is formula_23 where Ein("z") is the entire exponential integral. The exponential integral may also be expressed as formula_24 where Γ(0, "z") is the incomplete gamma function. Arithmetic properties. The harmonic numbers have several interesting arithmetic properties. It is well-known that formula_25 is an integer if and only if formula_26, a result often attributed to Taeisinger. Indeed, using 2-adic valuation, it is not difficult to prove that for formula_27 the numerator of formula_25 is an odd number  while the denominator of formula_25 is an even number. More precisely, formula_30 with some odd integers formula_31 and formula_32. As a consequence of Wolstenholme's theorem, for any prime number formula_33 the numerator of formula_34is divisible by formula_35. Furthermore, Eisenstein proved that for all odd prime number formula_36 it holds formula_37 where formula_38 is a Fermat quotient, with the consequence that formula_36 divides the numerator of formula_40 if and only if formula_36 is a Wieferich prime. In 1991, Eswarathasan and Levine defined formula_42 as the set of all positive integers formula_43 such that the numerator of formula_44 is divisible by  a prime number formula_45 They proved that formula_46 for all prime numbers formula_47 and they defined "harmonic primes" to be the primes formula_36 such that formula_42 has exactly 3 elements. Eswarathasan and Levine also conjectured that formula_42 is a finite set for all primes formula_51 and that there are infinitely many harmonic primes. Boyd verified that formula_42 is finite for all prime numbers up to formula_53 except 83, 127, and 397; and he gave a heuristic suggesting that the density of the harmonic primes in the set of all primes should be formula_54. Sanna showed that formula_42 has zero asymptotic  density, while Bing-Ling Wu and Yong-Gao Chen proved that the number of elements of formula_42 not exceeding formula_57 is at most formula_58, for all formula_59. Applications. The harmonic numbers appear in several calculation formulas, such as the digamma function formula_60 This relation is also frequently used to define the extension of the harmonic numbers to non-integer "n". The harmonic numbers are also frequently used to define using the limit introduced earlier: formula_61 although formula_62 converges more quickly. In 2002, Jeffrey Lagarias proved that the Riemann hypothesis is equivalent to the statement that formula_63 is true for every  integer with strict inequality if ; here denotes the sum of the divisors of . The eigenvalues of the nonlocal problem formula_64 are given by formula_65, where by convention formula_66, and the corresponding eigenfunctions are given by the Legendre polynomials formula_67. Generalizations. Generalized harmonic numbers. The generalized harmonic number of order "m" of "n" is given by formula_68 Other notations occasionally used include formula_69 The special case of "m" = 0 gives formula_70 The special case of "m" = 1 is simply called a harmonic number and is frequently written without the "m", as formula_71 The limit as is finite if , with  the generalized harmonic number bounded by and converging to the Riemann zeta function formula_72 The smallest natural number "k" such that "k" does not divide the denominator of generalized harmonic number "H"("k", "n") nor the denominator of alternating generalized harmonic number "H′"("k", "n") is, for "n"=1, 2, ... : The related sum formula_73 occurs in the study of Bernoulli numbers; the harmonic numbers also appear in the study of Stirling numbers. Some integrals of generalized harmonic numbers are formula_74 and formula_75 where "A" is Apéry's constant "ζ"(3), and formula_76 Every generalized harmonic number of order "m" can be written as a  function of harmonic numbers of order formula_77 using formula_78   for example: formula_79 A generating function for the generalized harmonic numbers is formula_80 where formula_81 is the polylogarithm, and . The generating function given above for is a special case of this formula. A fractional argument for generalized harmonic numbers can be introduced as follows: For every formula_82 integer, and formula_83 integer or not, we have from polygamma functions: formula_84 where formula_85 is the Riemann zeta function. The relevant recurrence relation is formula_86 Some special values are formula_87 where "G" is Catalan's constant, formula_88 formula_89 formula_90 formula_91 formula_92 In the special  case that formula_93, we get formula_94 where formula_95 is the Hurwitz zeta function. This relationship is used to calculate harmonic numbers numerically. Multiplication formulas. The multiplication theorem applies to harmonic numbers. Using polygamma functions, we obtain formula_96 formula_97 or, more generally, formula_98 For generalized harmonic numbers, we have formula_99 formula_100 where formula_101 is the Riemann zeta function. Hyperharmonic numbers. The next generalization was discussed by J. H. Conway and R. K. Guy in their 1995 book "The Book of Numbers". Let formula_102 Then the nth hyperharmonic number of order "r" ("r>0") is defined recursively as formula_103 In particular, formula_104 is  the ordinary harmonic number formula_44. Harmonic numbers for real and complex values. The formulae given above, formula_106 are an integral and a series representation for a function that interpolates the harmonic numbers and, via analytic continuation, extends the definition to the complex plane other than the negative integers "x". The interpolating function is in fact closely related to the digamma function formula_107 where is the digamma, and is the Euler–Mascheroni constant. The integration process may be repeated to obtain formula_108 The Taylor series for the harmonic numbers is formula_109 which comes from the Taylor series for the digamma function  (formula_110 is the Riemann zeta function). Approximation using the Taylor series expansion. The harmonic number can be approximated using the first few terms of the Taylor series expansion: formula_111 where formula_112 is the Euler–Mascheroni constant. Alternative, asymptotic formulation. When seeking to approximate  for a complex number , it is effective to first compute  for some large integer . Use that to approximate a value for  and then use the recursion relation backwards  times, to unwind it to an approximation for . Furthermore, this approximation is exact in the limit as  goes to infinity. Specifically, for a fixed integer , it is the case  that formula_113 If  is not an integer then it is not possible to say whether this equation is true because we have not yet (in this section) defined harmonic numbers for non-integers. However, we do get a unique extension of the harmonic numbers to the non-integers by insisting that this equation continue to hold when the arbitrary integer  is replaced by an arbitrary complex number . formula_114 Swapping the order of the two sides of this equation and then subtracting them from  gives formula_115 This infinite series converges for all complex numbers  except the negative integers, which fail because  trying to use the recursion relation backwards through the value  involves a division by zero. By this construction, the function that defines the harmonic number for complex values is the unique function that simultaneously satisfies (1) , (2) for all complex numbers  except the non-positive integers, and (3) for all complex values . Note that this last formula can be used to show that formula_116 where  is the Euler–Mascheroni constant or, more generally, for every  we have: formula_117 Special values for fractional arguments. There are the following special analytic values for fractional arguments between 0 and 1, given by the  integral formula_118 More values may be generated from the recurrence relation formula_119 or from the reflection relation formula_120 For example: formula_121 formula_122 formula_123 formula_124 formula_125 formula_126 formula_127 formula_128 For positive integers "p" and "q" with "p" < "q", we have: formula_129 Relation to the Riemann zeta function. Some derivatives of fractional harmonic numbers are given by formula_130 And using Maclaurin series, we have for "x" < 1 that formula_131 For fractional arguments between 0 and 1 and for "a" > 1, formula_132