Editing Harmonic number

{{Short description|Sum of the first n whole number reciprocals; 1/1 + 1/2 + 1/3 + ... +  1/n}}
{{other uses}}
{{Use American English|date = March 2019}}

[[Image:HarmonicNumbers.svg|right|thumb|400px|The harmonic number <math>H_n</math> with <math>n=\lfloor x \rfloor</math> (red line) with its asymptotic limit <math>\gamma+\ln(x)</math> (blue line) where <math>\gamma</math> is the [[Euler–Mascheroni constant]].]]

In [[mathematics]], the {{mvar|n}}-th '''harmonic number''' is the sum of the [[Multiplicative inverse|reciprocals]] of the first {{mvar|n}} [[natural number]]s:<ref>{{Cite book |last=Knuth |first=Donald |title=The Art of Computer Programming |publisher=Addison-Wesley |year=1997 |isbn=0-201-89683-4 |edition=3rd |pages=75–79 |language=en}}</ref>
<math display="block">H_n= 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n} =\sum_{k=1}^n \frac{1}{k}.</math>

Starting from {{math|1=''n'' = 1}}, the sequence of harmonic numbers begins:
<math display="block">1, \frac{3}{2}, \frac{11}{6}, \frac{25}{12}, \frac{137}{60}, \dots</math>

Harmonic numbers are related to the [[harmonic mean]] in that the {{mvar|n}}-th harmonic number is also {{mvar|n}} times the reciprocal of the harmonic mean of the first {{mvar|n}} 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 (mathematics)|harmonic series]], are closely related to the [[Riemann zeta function]], and appear in the expressions of various [[special function]]s.

The harmonic numbers roughly approximate the [[natural logarithm|natural logarithm function]]<ref name=ConwayGuy/>{{rp|143}} and thus the associated [[harmonic series (mathematics)|harmonic series]] grows without limit, albeit slowly. In 1737, [[Leonhard Euler]] used the [[Divergence of the sum of the reciprocals of the primes|divergence of the harmonic series]] to provide a new proof of the [[Euclid's theorem|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 [[Prime number theorem|distribution of prime numbers]].

When the value of a large quantity of items has a [[Zipf's law]] distribution, the total value of the {{mvar|n}} most-valuable items is proportional to the {{mvar|n}}-th harmonic number. This leads to a variety of surprising conclusions regarding the [[long tail]] and [[Andrew Odlyzko#Network value|the theory of network value]].

The [[Bertrand's postulate|Bertrand-Chebyshev theorem]] implies that, except for the case {{math|1=''n'' = 1}}, the harmonic numbers are never integers.<ref name = 'ConcreteMath'>{{Cite book
| first1 = Ronald L. | last1 = Graham
| first2 = Donald E. | last2 = Knuth
| first3 = Oren | last3 = Patashnik
| title = Concrete Mathematics
| year = 1994
| publisher = Addison-Wesley
| title-link = Concrete Mathematics
}}</ref>
{| class="wikitable infobox collapsible collapsed" style="line-height:0.8;text-align:left;white-space:nowrap;"
|+ The first 40 harmonic numbers
! rowspan="2" style="padding-top:1em;"|''n'' !! colspan="4"|Harmonic number, ''H<sub>n</sub>''
|-
! colspan="2"|expressed as a fraction !! decimal !! relative size
|-
| style="text-align:right;"|1 || style="text-align:center;" colspan="2"|1 || {{bartable|1||20}}
|-

| style="text-align:right;"|2 || style="border-right:none;padding-right:0;text-align:right;"|3 || style="border-left:none;padding-left:0;"|/2 || {{bartable|1.5||20}}
|-
| style="text-align:right;"|3 || style="border-right:none;padding-right:0;text-align:right;"|11 || style="border-left:none;padding-left:0;"|/6 || ~{{bartable|1.83333||20}}
|-
| style="text-align:right;"|4 || style="border-right:none;padding-right:0;text-align:right;"|25 || style="border-left:none;padding-left:0;"|/12 || ~{{bartable|2.08333||20}}
|-
| style="text-align:right;"|5 || style="border-right:none;padding-right:0;text-align:right;"|137 || style="border-left:none;padding-left:0;"|/60 || ~{{bartable|2.28333||20}}
|-
| style="text-align:right;"|6 || style="border-right:none;padding-right:0;text-align:right;"|49 || style="border-left:none;padding-left:0;"|/20 || {{bartable|2.45||20}}
|-
| style="text-align:right;"|7 || style="border-right:none;padding-right:0;text-align:right;"|363 || style="border-left:none;padding-left:0;"|/140 || ~{{bartable|2.59286||20}}
|-
| style="text-align:right;"|8 || style="border-right:none;padding-right:0;text-align:right;"|761 || style="border-left:none;padding-left:0;"|/280 || ~{{bartable|2.71786||20}}
|-
| style="text-align:right;"|9 || style="border-right:none;padding-right:0;text-align:right;"|7&thinsp;129 || style="border-left:none;padding-left:0;"|/2&thinsp;520 || ~{{bartable|2.82897||20}}
|-
| style="text-align:right;"|10 || style="border-right:none;padding-right:0;text-align:right;"|7&thinsp;381 || style="border-left:none;padding-left:0;"|/2&thinsp;520 || ~{{bartable|2.92897||20}}
|-
| style="text-align:right;"|11 || style="border-right:none;padding-right:0;text-align:right;"|83&thinsp;711 || style="border-left:none;padding-left:0;"|/27&thinsp;720 || ~{{bartable|3.01988||20}}
|-
| style="text-align:right;"|12 || style="border-right:none;padding-right:0;text-align:right;"|86&thinsp;021 || style="border-left:none;padding-left:0;"|/27&thinsp;720 || ~{{bartable|3.10321||20}}
|-
| style="text-align:right;"|13 || style="border-right:none;padding-right:0;text-align:right;"|1&thinsp;145&thinsp;993 || style="border-left:none;padding-left:0;"|/360&thinsp;360 || ~{{bartable|3.18013||20}}
|-
| style="text-align:right;"|14 || style="border-right:none;padding-right:0;text-align:right;"|1&thinsp;171&thinsp;733 || style="border-left:none;padding-left:0;"|/360&thinsp;360 || ~{{bartable|3.25156||20}}
|-
| style="text-align:right;"|15 || style="border-right:none;padding-right:0;text-align:right;"|1&thinsp;195&thinsp;757 || style="border-left:none;padding-left:0;"|/360&thinsp;360 || ~{{bartable|3.31823||20}}
|-
| style="text-align:right;"|16 || style="border-right:none;padding-right:0;text-align:right;"|2&thinsp;436&thinsp;559 || style="border-left:none;padding-left:0;"|/720&thinsp;720 || ~{{bartable|3.38073||20}}
|-
| style="text-align:right;"|17 || style="border-right:none;padding-right:0;text-align:right;"|42&thinsp;142&thinsp;223 || style="border-left:none;padding-left:0;"|/12&thinsp;252&thinsp;240 || ~{{bartable|3.43955||20}}
|-
| style="text-align:right;"|18 || style="border-right:none;padding-right:0;text-align:right;"|14&thinsp;274&thinsp;301 || style="border-left:none;padding-left:0;"|/4&thinsp;084&thinsp;080 || ~{{bartable|3.49511||20}}
|-
| style="text-align:right;"|19 || style="border-right:none;padding-right:0;text-align:right;"|275&thinsp;295&thinsp;799 || style="border-left:none;padding-left:0;"|/77&thinsp;597&thinsp;520 || ~{{bartable|3.54774||20}}
|-
| style="text-align:right;"|20 || style="border-right:none;padding-right:0;text-align:right;"|55&thinsp;835&thinsp;135 || style="border-left:none;padding-left:0;"|/15&thinsp;519&thinsp;504 || ~{{bartable|3.59774||20}}
|-
| style="text-align:right;"|21 || style="border-right:none;padding-right:0;text-align:right;"|18&thinsp;858&thinsp;053 || style="border-left:none;padding-left:0;"|/5&thinsp;173&thinsp;168 || ~{{bartable|3.64536||20}}
|-
| style="text-align:right;"|22 || style="border-right:none;padding-right:0;text-align:right;"|19&thinsp;093&thinsp;197 || style="border-left:none;padding-left:0;"|/5&thinsp;173&thinsp;168 || ~{{bartable|3.69081||20}}
|-
| style="text-align:right;"|23 || style="border-right:none;padding-right:0;text-align:right;"|444&thinsp;316&thinsp;699 || style="border-left:none;padding-left:0;"|/118&thinsp;982&thinsp;864 || ~{{bartable|3.73429||20}}
|-
| style="text-align:right;"|24 || style="border-right:none;padding-right:0;text-align:right;font-size:96%;"|1&thinsp;347&thinsp;822&thinsp;955 || style="border-left:none;padding-left:0;font-size:96%;"|/356&thinsp;948&thinsp;592 || ~{{bartable|3.77596||20}}
|-
| style="text-align:right;"|25 || style="border-right:none;padding-right:0;text-align:right;font-size:87%;"|34&thinsp;052&thinsp;522&thinsp;467 || style="border-left:none;padding-left:0;font-size:87%;"|/8&thinsp;923&thinsp;714&thinsp;800 || ~{{bartable|3.81596||20}}
|-
| style="text-align:right;"|26 || style="border-right:none;padding-right:0;text-align:right;font-size:87%;"|34&thinsp;395&thinsp;742&thinsp;267 || style="border-left:none;padding-left:0;font-size:87%;"|/8&thinsp;923&thinsp;714&thinsp;800 || ~{{bartable|3.85442||20}}
|-
| style="text-align:right;"|27 || style="border-right:none;padding-right:0;text-align:right;font-size:80%;"|312&thinsp;536&thinsp;252&thinsp;003 || style="border-left:none;padding-left:0;font-size:80%;"|/80&thinsp;313&thinsp;433&thinsp;200 || ~{{bartable|3.89146||20}}
|-
| style="text-align:right;"|28 || style="border-right:none;padding-right:0;text-align:right;font-size:80%;"|315&thinsp;404&thinsp;588&thinsp;903 || style="border-left:none;padding-left:0;font-size:80%;"|/80&thinsp;313&thinsp;433&thinsp;200 || ~{{bartable|3.92717||20}}
|-
| style="text-align:right;"|29 || style="border-right:none;padding-right:0;text-align:right;font-size:73%;"|9&thinsp;227&thinsp;046&thinsp;511&thinsp;387 || style="border-left:none;padding-left:0;font-size:73%;"|/2&thinsp;329&thinsp;089&thinsp;562&thinsp;800 || ~{{bartable|3.96165||20}}
|-
| style="text-align:right;"|30 || style="border-right:none;padding-right:0;text-align:right;font-size:73%;"|9&thinsp;304&thinsp;682&thinsp;830&thinsp;147 || style="border-left:none;padding-left:0;font-size:73%;"|/2&thinsp;329&thinsp;089&thinsp;562&thinsp;800 || ~{{bartable|3.99499||20}}
|-
| style="text-align:right;"|31 || style="border-right:none;padding-right:0;text-align:right;font-size:64%;"|290&thinsp;774&thinsp;257&thinsp;297&thinsp;357 || style="border-left:none;padding-left:0;font-size:64%;"|/72&thinsp;201&thinsp;776&thinsp;446&thinsp;800 || ~{{bartable|4.02725||20}}
|-
| style="text-align:right;"|32 || style="border-right:none;padding-right:0;text-align:right;font-size:64%;"|586&thinsp;061&thinsp;125&thinsp;622&thinsp;639 || style="border-left:none;padding-left:0;font-size:64%;"|/144&thinsp;403&thinsp;552&thinsp;893&thinsp;600 || ~{{bartable|4.05850||20}}
|-
| style="text-align:right;"|33 || style="border-right:none;padding-right:0;text-align:right;font-size:68%;"|53&thinsp;676&thinsp;090&thinsp;078&thinsp;349 || style="border-left:none;padding-left:0;font-size:68%;"|/13&thinsp;127&thinsp;595&thinsp;717&thinsp;600 || ~{{bartable|4.08880||20}}
|-
| style="text-align:right;"|34 || style="border-right:none;padding-right:0;text-align:right;font-size:68%;"|54&thinsp;062&thinsp;195&thinsp;834&thinsp;749 || style="border-left:none;padding-left:0;font-size:68%;"|/13&thinsp;127&thinsp;595&thinsp;717&thinsp;600 || ~{{bartable|4.11821||20}}
|-
| style="text-align:right;"|35 || style="border-right:none;padding-right:0;text-align:right;font-size:68%;"|54&thinsp;437&thinsp;269&thinsp;998&thinsp;109 || style="border-left:none;padding-left:0;font-size:68%;"|/13&thinsp;127&thinsp;595&thinsp;717&thinsp;600 || ~{{bartable|4.14678||20}}
|-
| style="text-align:right;"|36 || style="border-right:none;padding-right:0;text-align:right;font-size:68%;"|54&thinsp;801&thinsp;925&thinsp;434&thinsp;709 || style="border-left:none;padding-left:0;font-size:68%;"|/13&thinsp;127&thinsp;595&thinsp;717&thinsp;600 || ~{{bartable|4.17456||20}}
|-
| style="text-align:right;"|37 || style="border-right:none;padding-right:0;text-align:right;font-size:60%;"|2&thinsp;040&thinsp;798&thinsp;836&thinsp;801&thinsp;833 || style="border-left:none;padding-left:0;font-size:60%;"|/485&thinsp;721&thinsp;041&thinsp;551&thinsp;200 || ~{{bartable|4.20159||20}}
|-
| style="text-align:right;"|38 || style="border-right:none;padding-right:0;text-align:right;font-size:60%;"|2&thinsp;053&thinsp;580&thinsp;969&thinsp;474&thinsp;233 || style="border-left:none;padding-left:0;font-size:60%;"|/485&thinsp;721&thinsp;041&thinsp;551&thinsp;200 || ~{{bartable|4.22790||20}}
|-
| style="text-align:right;"|39 || style="border-right:none;padding-right:0;text-align:right;font-size:60%;"|2&thinsp;066&thinsp;035&thinsp;355&thinsp;155&thinsp;033 || style="border-left:none;padding-left:0;font-size:60%;"|/485&thinsp;721&thinsp;041&thinsp;551&thinsp;200 || ~{{bartable|4.25354||20}}
|-
| style="text-align:right;"|40 || style="border-right:none;padding-right:0;text-align:right;font-size:60%;"|2&thinsp;078&thinsp;178&thinsp;381&thinsp;193&thinsp;813 || style="border-left:none;padding-left:0;font-size:60%;"|/485&thinsp;721&thinsp;041&thinsp;551&thinsp;200 || ~{{bartable|4.27854||20}}
|}
<!-- Python script to generate n from 2 to 40:
import fractions
numerator = 1; denominator = 1
for i in range(2, 40 + 1):
 numerator = numerator * i + denominator; denominator *= i; gcd = fractions.gcd(numerator, denominator); numerator /= gcd; denominator /= gcd
 decimal   = ('{}' if (i < 3 or i == 6) else '{:.5f}').format(float(numerator) / denominator); exact = '' if (i < 3 or i == 6) else '~'
 numerator_length = len(str(numerator)); size = '' if (numerator_length <= 9) else 'font-size:{:d}%;'.format(960 / numerator_length)
 print('|-\n| style="text-align:right;"|{} || style="border-right:none;padding-right:0;text-align:right;{}"|{:,} || style="border-left:none;padding-left:0;{}"|/{:,} || {}{{{{bartable|{}||20}}}}'.
       format(i, size, numerator, size, denominator, exact, decimal).replace(',', '&thinsp;'))
-->

==Identities involving harmonic numbers==
By definition, the harmonic numbers satisfy the [[recurrence relation]]
<math display="block"> H_{n + 1} = H_{n} + \frac{1}{n + 1}.</math>

The harmonic numbers are connected to the [[Stirling numbers of the first kind]] by the relation
<math display="block"> H_n = \frac{1}{n!}\left[{n+1 \atop 2}\right]. </math>

The harmonic numbers satisfy the series identities
<math display="block"> \sum_{k=1}^n H_k = (n+1) H_{n} - n</math>
and
<math display="block">\sum_{k=1}^n H_k^2 = (n+1)H_{n}^2 - (2 n +1) H_n + 2 n.</math>
These two results are closely analogous to the corresponding integral results
<math display="block">\int_0^x \log y \  d y = x \log x - x</math>
and
<math display="block">\int_0^x (\log y)^2\ d y = x (\log x)^2 - 2 x \log x + 2 x.</math>

===Identities involving {{pi}}===

There are several infinite summations involving harmonic numbers and powers of [[Pi|{{pi}}]]:<ref>{{Cite web |last=Weisstein |first=Eric W. |title=Harmonic Number |url=https://mathworld.wolfram.com/HarmonicNumber.html |access-date=2024-09-30 |website=mathworld.wolfram.com |language=en}}</ref>{{better source|date=February 2022}}
<math display="block">\begin{align}
\sum_{n=1}^\infty \frac{H_n}{n\cdot 2^n} &= \frac{\pi^2}{12} \\
\sum_{n=1}^\infty \frac{H_n^2}{n^2} &= \frac{17}{360}\pi^4 \\
\sum_{n=1}^\infty \frac{H_n^2}{(n+1)^2} &= \frac{11}{360}\pi^4 \\
\sum_{n=1}^\infty \frac{H_n}{n^3} &= \frac{\pi^4}{72}
\end{align}</math>

==Calculation==
An integral representation given by [[Euler]]<ref>{{citation|title=How Euler Did It|series=MAA Spectrum|first=C. Edward|last=Sandifer|publisher=Mathematical Association of America|year=2007|isbn=9780883855638|page=206|url=https://books.google.com/books?id=sohHs7ExOsYC&pg=PA206}}.</ref> is
<math display="block"> H_n = \int_0^1 \frac{1 - x^n}{1 - x}\,dx. </math>

The equality above is straightforward by the simple [[algebraic identity]]
<math display="block"> \frac{1-x^n}{1-x}=1+x+\cdots +x^{n-1}.</math>

Using the substitution {{math|1=''x'' = 1 &minus; ''u''}}, another expression for {{math|''H''<sub>''n''</sub>}} is
<math display="block">\begin{align}
H_n &= \int_0^1 \frac{1 - x^n}{1 - x}\,dx = \int_0^1\frac{1-(1-u)^n}{u}\,du \\[6pt]
&= \int_0^1\left[\sum_{k=1}^n \binom nk (-u)^{k-1}\right]\,du 
= \sum_{k=1}^n \binom nk \int_0^1 (-u)^{k-1}\,du \\[6pt]
&= \sum_{k=1}^n \binom nk \frac{(-1)^{k-1}}{k}.
\end{align}
</math>

[[File:Integral Test.svg|thumb|Graph demonstrating a connection between harmonic numbers and the [[natural logarithm]]. The harmonic number {{math|''H''<sub>''n''</sub>}} can be interpreted as a [[Riemann sum]] of the integral: <math>\int_1^{n+1} \frac{dx}{x} = \ln(n+1).</math>]]
The {{mvar|n}}th harmonic number is about as large as the [[natural logarithm]] of {{mvar|n}}. The reason is that the sum is approximated by the [[integral]]
<math display="block">\int_1^n \frac{1}{x}\, dx,</math>
whose value is {{math|ln ''n''}}.

The values of the sequence {{math|''H''<sub>''n''</sub> − ln ''n''}} decrease monotonically towards the [[Limit of a sequence|limit]]
<math display="block"> \lim_{n \to \infty} \left(H_n - \ln n\right) = \gamma,</math>
where {{math|''γ'' ≈ 0.5772156649}} is the [[Euler–Mascheroni constant]]. The corresponding [[asymptotic expansion]] is
<math display="block">\begin{align}
   H_n &\sim \ln{n}+\gamma+\frac{1}{2n}-\sum_{k=1}^\infty \frac{B_{2k}}{2k n^{2k}}\\
   &=\ln{n}+\gamma+\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}-\cdots,
 \end{align}</math>
where {{math|''B''<sub>''k''</sub>}} are the [[Bernoulli numbers]].

{{Reflist|group=note}}

==Generating functions==
A [[generating function]] for the harmonic numbers is
<math display="block">\sum_{n=1}^\infty z^n H_n = \frac {-\ln(1-z)}{1-z},</math>
where ln(''z'') is the [[natural logarithm]]. An exponential generating function is
<math display="block">\sum_{n=1}^\infty \frac {z^n}{n!} H_n = e^z \sum_{k=1}^\infty \frac{(-1)^{k-1}}{k} \frac {z^k}{k!} = e^z \operatorname{Ein}(z)</math>
where Ein(''z'') is the entire [[exponential integral]]. The exponential integral may also be expressed as
<math display="block">\operatorname{Ein}(z) = \mathrm{E}_1(z) + \gamma + \ln z = \Gamma (0,z) + \gamma + \ln z</math>
where Γ(0, ''z'') is the [[incomplete gamma function]].

== Arithmetic properties ==
The harmonic numbers have several interesting arithmetic properties. It is well-known that <math display="inline">H_n</math> is an integer [[if and only if]] <math display="inline">n=1</math>, a result often attributed to Taeisinger.<ref>{{Cite book|title=CRC Concise Encyclopedia of Mathematics|last=Weisstein|first=Eric W.|publisher=Chapman & Hall/CRC|year=2003|isbn=978-1-58488-347-0|location=Boca Raton, FL|pages=3115}}</ref> Indeed, using [[P-adic valuation|2-adic valuation]], it is not difficult to prove that for <math display="inline">n \ge 2</math> the numerator of <math display="inline">H_n</math> is an odd number while the denominator of <math display="inline">H_n</math> is an even number. More precisely,
<math display="block">H_n=\frac{1}{2^{\lfloor\log_2(n)\rfloor}}\frac{a_n}{b_n}</math>
with some odd integers <math display="inline">a_n</math> and <math display="inline">b_n</math>.

As a consequence of [[Wolstenholme's theorem]], for any prime number <math>p \ge 5</math> the numerator of <math>H_{p-1}</math> is divisible by <math display="inline">p^2</math>. Furthermore, Eisenstein<ref>{{Cite journal|last=Eisenstein|first=Ferdinand Gotthold Max|year=1850|title=Eine neue Gattung zahlentheoretischer Funktionen, welche von zwei Elementen ahhängen und durch gewisse lineare Funktional-Gleichungen definirt werden|journal=Berichte Königl. Preuβ. Akad. Wiss. Berlin|volume=15|pages=36–42}}</ref> proved that for all odd prime number <math display="inline">p</math> it holds
<math display="block">H_{(p-1)/2} \equiv -2q_p(2) \pmod p</math>
where <math display="inline">q_p(2) = (2^{p-1}  -1)/p</math> is a [[Fermat quotient]], with the consequence that <math display="inline">p</math> divides the numerator of <math>H_{(p-1)/2}</math> if and only if <math display="inline">p</math> is a [[Wieferich prime]].

In 1991, Eswarathasan and Levine<ref>{{Cite journal|last1=Eswarathasan|first1=Arulappah|last2=Levine|first2=Eugene|year=1991|title=p-integral harmonic sums|journal=Discrete Mathematics|volume=91|issue=3|pages=249–257|doi=10.1016/0012-365X(90)90234-9|doi-access=free}}</ref> defined <math>J_p</math> as the set of all positive integers <math>n</math> such that the numerator of <math>H_n</math> is divisible by a prime number <math>p.</math> They proved that
<math display="block">\{p-1,p^2-p,p^2-1\}\subseteq J_p</math>
for all prime numbers <math>p \ge 5,</math> and they defined ''harmonic primes'' to be the primes <math display="inline">p</math> such that <math>J_p</math> has exactly 3 elements.

Eswarathasan and Levine also conjectured that <math>J_p</math> is a [[finite set]] for all primes <math>p,</math> and that there are infinitely many harmonic primes. Boyd<ref>{{Cite journal|last=Boyd|first=David W.|year=1994|title=A p-adic study of the partial sums of the harmonic series|url=http://projecteuclid.org/euclid.em/1048515811|journal=Experimental Mathematics|volume=3|issue=4|pages=287–302|doi=10.1080/10586458.1994.10504298|citeseerx=10.1.1.56.7026}}</ref> verified that <math>J_p</math> is finite for all prime numbers up to <math>p = 547</math> except 83, 127, and 397; and he gave a heuristic suggesting that the [[Natural density|density]] of the harmonic primes in the set of all primes should be <math>1/e</math>. Sanna<ref>{{Cite journal|last=Sanna|first=Carlo|year=2016|title=On the p-adic valuation of harmonic numbers|journal=Journal of Number Theory|volume=166|pages=41–46|doi=10.1016/j.jnt.2016.02.020|hdl=2318/1622121|url=https://iris.unito.it/bitstream/2318/1622121/1/padicharm.pdf|doi-access=free}}</ref> showed that <math>J_p</math> has zero [[Natural density|asymptotic density]], while Bing-Ling Wu and Yong-Gao Chen<ref>{{Cite journal|last1=Chen|first1=Yong-Gao|last2=Wu|first2=Bing-Ling|year=2017|title=On certain properties of harmonic numbers|journal=Journal of Number Theory|volume=175|pages=66–86|doi=10.1016/j.jnt.2016.11.027|doi-access=}}</ref> proved that the number of elements of <math>J_p</math> not exceeding <math>x</math> is at most <math>3x^{\frac{2}{3}+\frac1{25 \log p}}</math>, for all <math>x \geq 1</math>.

==Applications==
The harmonic numbers appear in several calculation formulas, such as the [[digamma function]]
<math display="block"> \psi(n) = H_{n-1} - \gamma.</math>
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 {{mvar|γ}} using the limit introduced earlier:
<math display="block"> \gamma = \lim_{n \rightarrow \infty}{\left(H_n - \ln(n)\right)}, </math>
although
<math display="block"> \gamma = \lim_{n \to \infty}{\left(H_n - \ln\left(n+\frac{1}{2}\right)\right)} </math>
converges more quickly.

In 2002, [[Jeffrey Lagarias]] proved<ref>{{cite journal |author=Jeffrey Lagarias |title=An Elementary Problem Equivalent to the Riemann Hypothesis |journal=Amer. Math. Monthly |volume=109 |issue=6 |year=2002 |pages=534–543 |arxiv=math.NT/0008177 |doi=10.2307/2695443|jstor=2695443 }}</ref> that the [[Riemann hypothesis]] is equivalent to the statement that
<math display="block"> \sigma(n) \le H_n + (\log H_n)e^{H_n},</math>
is true for every [[integer]] {{math|''n'' ≥ 1}} with strict inequality if {{math|''n'' > 1}}; here {{math|''σ''(''n'')}} denotes the [[divisor function|sum of the divisors]] of {{mvar|n}}.

The eigenvalues of the nonlocal problem on <math> L^2([-1,1])</math>
<math display="block"> \lambda \varphi(x) = \int_{-1}^{1} \frac{\varphi(x)-\varphi(y)}{|x-y|} \, dy </math>
are given by <math>\lambda = 2H_n</math>, where by convention <math>H_0 = 0</math>, and the corresponding eigenfunctions are given by the [[Legendre polynomials]] <math>\varphi(x) = P_n(x)</math>.<ref>{{cite journal |author=E.O. Tuck |title=Some methods for flows past blunt slender bodies |journal=J. Fluid Mech. |volume=18 |year=1964 |issue=4 |pages=619–635 |doi=10.1017/S0022112064000453|bibcode=1964JFM....18..619T |s2cid=123120978 }}</ref>

==Generalizations==

===Generalized harmonic numbers===
The ''n''th '''generalized harmonic number''' of order ''m'' is given by
<math display="block">H_{n,m}=\sum_{k=1}^n \frac{1}{k^m}.</math>

(In some sources, this may also be denoted by <math display="inline">H_n^{(m)}</math> or <math display="inline">H_m(n).</math>)

The special case ''m'' = 0 gives <math>H_{n,0}= n.</math>  The special case ''m'' = 1 reduces to the usual harmonic number:
<math display="block">H_{n, 1} = H_n = \sum_{k=1}^n \frac{1}{k}.</math>

The limit of <math display="inline">H_{n, m}</math> as {{math|''n'' → ∞}} is finite if {{math|''m'' > 1}}, with the generalized harmonic number bounded by and converging to the [[Riemann zeta function]]
<math display="block">\lim_{n\rightarrow \infty} H_{n,m} = \zeta(m).</math>

The smallest natural number ''k'' such that ''k<sup>n</sup>'' 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, ... :
:77, 20, 94556602, 42, 444, 20, 104, 42, 76, 20, 77, 110, 3504, 20, 903, 42, 1107, 20, 104, 42, 77, 20, 2948, 110, 136, 20, 76, 42, 903, 20, 77, 42, 268, 20, 7004, 110, 1752, 20, 19203, 42, 77, 20, 104, 42, 76, 20, 370, 110, 1107, 20, ... {{OEIS|id=A128670}}

The related sum <math>\sum_{k=1}^n k^m</math> occurs in the study of [[Bernoulli number]]s; the harmonic numbers also appear in the study of [[Stirling number]]s.

Some integrals of generalized harmonic numbers are
<math display="block">\int_0^a H_{x,2} \, dx = a \frac {\pi^2}{6}-H_{a}</math>
and
<math display="block">\int_0^a H_{x,3} \, dx = a A - \frac {1}{2} H_{a,2},</math> where ''A'' is [[Apéry's constant]] ''ζ''(3),
and
<math display="block">\sum_{k=1}^n H_{k,m}=(n+1)H_{n,m}- H_{n,m-1} \text{ for } m \geq 0 .</math>

Every generalized harmonic number of order ''m'' can be written as a function of harmonic numbers of order <math>m-1</math> using
<math display="block">H_{n,m} = \sum_{k=1}^{n-1} \frac {H_{k,m-1}}{k(k+1)} + \frac {H_{n,m-1}}{n} </math> &nbsp; for example: <math>H_{4,3} = \frac {H_{1,2}}{1 \cdot 2} + \frac {H_{2,2}}{2 \cdot 3} + \frac {H_{3,2}}{3 \cdot 4} + \frac {H_{4,2}}{4} </math>

A [[generating function]] for the generalized harmonic numbers is
<math display="block">\sum_{n=1}^\infty z^n H_{n,m} = \frac {\operatorname{Li}_m(z)}{1-z},</math>
where <math>\operatorname{Li}_m(z)</math> is the [[polylogarithm]], and {{math|{{mabs|''z''}} < 1}}. The generating function given above for {{math|1=''m'' = 1}} is a special case of this formula.

A '''fractional argument for generalized harmonic numbers''' can be introduced as follows:

For every <math>p,q>0</math> integer, and <math>m>1</math> integer or not, we have from polygamma functions:
<math display="block">H_{q/p,m}=\zeta(m)-p^m\sum_{k=1}^\infty \frac{1}{(q+pk)^m}</math>
where <math>\zeta(m)</math> is the [[Riemann zeta function]]. The relevant recurrence relation is
<math display="block">H_{a,m}=H_{a-1,m}+\frac{1}{a^m}.</math>
Some special values are<math display="block">\begin{align}
H_{\frac{1}{4},2} &= 16-\tfrac{5}{6}\pi^2 -8G\\
H_{\frac{1}{2},2} &= 4-\frac{\pi^2}{3} \\
H_{\frac{3}{4},2} &= \frac{16}{9}-\frac{5}{6}\pi^2 + 8G \\
H_{\frac{1}{4},3} &= 64-\pi^3-27\zeta(3) \\
H_{\frac{1}{2},3} & =8-6\zeta(3) \\
H_{\frac{3}{4},3} &= \left(\frac{4}{3}\right)^3+\pi^3 -27\zeta(3)
\end{align}</math>where ''G'' is [[Catalan's constant]]. In the special case that <math>p = 1</math>, we get
<math display="block">H_{n,m}=\zeta(m, 1) - \zeta(m, n+1),</math>


where <math>\zeta(m, n)</math> 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
<math display="block">\begin{align}
H_{2x} & =\frac{1}{2}\left(H_x+H_{x-\frac{1}{2}}\right)+\ln 2 \\
H_{3x} &= \frac{1}{3}\left(H_x+H_{x-\frac{1}{3}}+H_{x-\frac{2}{3}}\right)+\ln 3,
\end{align}</math>
or, more generally,
<math display="block">H_{nx}=\frac{1}{n}\left(H_x+H_{x-\frac{1}{n}}+H_{x-\frac{2}{n}}+\cdots +H_{x-\frac{n-1}{n}} \right) + \ln n.</math>

For generalized harmonic numbers, we have
<math display="block">\begin{align}
H_{2x,2} &= \frac{1}{2}\left(\zeta(2)+\frac{1}{2}\left(H_{x,2}+H_{x-\frac{1}{2},2}\right)\right) \\
H_{3x,2} &= \frac{1}{9}\left(6\zeta(2)+H_{x,2}+H_{x-\frac{1}{3},2}+H_{x-\frac{2}{3},2}\right),
\end{align}</math>
where <math>\zeta(n)</math> is the [[Riemann zeta function]].

===Hyperharmonic numbers===

The next generalization was discussed by [[John Horton Conway|J. H. Conway]] and [[Richard K. Guy|R. K. Guy]] in their 1995 book ''[[The Book of Numbers (maths)|The Book of Numbers]]''.<ref name=ConwayGuy/>{{rp|258}} Let
<math display="block"> H_n^{(0)} = \frac1n. </math>
Then the nth [[hyperharmonic number]] of order ''r'' (''r>0'') is defined recursively as
<math display="block"> H_n^{(r)} = \sum_{k=1}^n H_k^{(r-1)}. </math>
In particular, <math>H_n^{(1)}</math> is the ordinary harmonic number <math>H_n</math>.

=== Roman Harmonic numbers ===
The [[Roman Harmonic numbers]],<ref>{{Cite journal |last=Sesma |first=J. |date=2017 |title=The Roman harmonic numbers revisited |url=http://dx.doi.org/10.1016/j.jnt.2017.05.009 |journal=Journal of Number Theory |volume=180 |pages=544–565 |doi=10.1016/j.jnt.2017.05.009 |issn=0022-314X|arxiv=1702.03718 }}</ref> named after [[Steven Roman]], were introduced by [[Daniel E. Loeb|Daniel Loeb]] and [[Gian-Carlo Rota]] in the context of a generalization of [[umbral calculus]] with logarithms.<ref>{{Cite journal |last1=Loeb |first1=Daniel E |last2=Rota |first2=Gian-Carlo |date=1989 |title=Formal power series of logarithmic type |journal=Advances in Mathematics |volume=75 |issue=1 |pages=1–118 |doi=10.1016/0001-8708(89)90079-0 |issn=0001-8708|doi-access=free }}</ref>  There are many possible definitions, but one of them, for  <math>n,k \geq 0</math>, is<math display="block"> c_n^{(0)} = 1, </math>and<math display="block"> c_n^{(k+1)} = \sum_{i=1}^n\frac{c_i^{(k)}}{i}. </math>Of course,<math display="block"> c_n^{(1)} = H_n. </math>

If <math>n \neq 0</math>, they satisfy<math display="block"> c_n^{(k+1)} - \frac{c_n^{(k)}}{n} = c_{n-1}^{(k+1)}. </math>Closed form formulas are<math display="block"> c_n^{(k)} = n! (-1)^k s(-n,k), </math>where <math>s(-n,k)</math> is [[Stirling numbers of the first kind]] generalized to negative first argument, and<math display="block"> c_n^{(k)} = \sum_{j=1}^n \binom{n}{j} \frac{(-1)^{j-1}}{j^k}, </math>which was found by [[Donald Knuth]].

In fact, these numbers were defined in a more general manner using Roman numbers and [[Roman factorials]], that include negative values for <math>n</math>. This generalization was useful in their study to define [[Harmonic logarithms]].

==Harmonic numbers for real and complex values==
{{unreferenced section|date=May 2019}}
The formulae given above,
<math display="block"> H_x = \int_0^1 \frac{1-t^x}{1-t} \, dt= \sum_{k=1}^\infty {x \choose k} \frac{(-1)^{k-1}}{k}</math>
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]]
<math display="block">H_x = \psi(x+1)+\gamma,</math>
where {{math|''ψ''(''x'')}} is the digamma function, and {{math|''γ''}} is the [[Euler–Mascheroni constant]]. The integration process may be repeated to obtain
<math display="block">H_{x,2}= \sum_{k=1}^\infty \frac {(-1)^{k-1}}{k} {x \choose k} H_k.</math>

The [[Taylor series]] for the harmonic numbers is
<math display="block">H_x=\sum_{k=2}^\infty (-1)^{k}\zeta (k)\;x^{k-1}\quad\text{ for } |x| < 1</math>
which comes from the Taylor series for the digamma function (<math>\zeta </math> is the [[Riemann zeta function]]).

=== Alternative, asymptotic formulation ===
There is an asymptotic formulation that gives the same result as the analytic continuation of the integral just described. When seeking to approximate&nbsp;{{math|''H''{{sub|''x''}}}} for a [[complex number]]&nbsp;{{math|''x''}}, it is effective to first compute&nbsp;{{math|''H''{{sub|''m''}}}} for some large integer&nbsp;{{math|''m''}}.  Use that as an approximation for the value of&nbsp;{{math|''H''{{sub|''m''+''x''}}}}. Then use the recursion relation {{math|1=''H''{{sub|''n''}} = ''H''{{sub|''n''−1}} + 1/''n''}} backwards&nbsp;{{math|''m''}} times, to unwind it to an approximation for&nbsp;{{math|''H''{{sub|''x''}}}}.  Furthermore, this approximation is exact in the limit as&nbsp;{{math|''m''}} goes to infinity.

Specifically, for a fixed integer&nbsp;{{math|''n''}}, it is the case that
<math display="block">\lim_{m \rightarrow \infty} \left[H_{m+n} - H_m\right] = 0.</math>

If&nbsp;{{math|''n''}} 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&nbsp;{{math|''n''}} is replaced by an arbitrary complex number&nbsp;{{math|''x''}},

<math display="block">\lim_{m \rightarrow \infty} \left[H_{m+x} - H_m\right] = 0\,.</math>
Swapping the order of the two sides of this equation and then subtracting them from&nbsp;{{math|''H''<sub>''x''</sub>}} gives
<math display="block">
\begin{align}H_x &= \lim_{m \rightarrow \infty} \left[H_m - (H_{m+x}-H_x)\right] \\[6pt]
&= \lim_{m \rightarrow \infty} \left[\left(\sum_{k=1}^m \frac{1}{k}\right) - \left(\sum_{k=1}^m \frac{1}{x+k}\right) \right] \\[6pt]
&= \lim_{m \rightarrow \infty} \sum_{k=1}^m \left(\frac{1}{k} - \frac{1}{x+k}\right) = x \sum_{k=1}^{\infty} \frac{1}{k(x+k)}\, .
\end{align}
</math>

This [[infinite series]] converges for all complex numbers&nbsp;{{math|''x''}} except the negative integers, which fail because trying to use the recursion relation {{math|1=''H''{{sub|''n''}} = ''H''{{sub|''n''−1}} + 1/''n''}} backwards through the value&nbsp;{{math|1=''n'' = 0}} 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) {{math|1=''H''{{sub|0}} = 0}}, (2) {{math|1=''H''{{sub|''x''}} = ''H''{{sub|''x''−1}} + 1/''x''}} for all complex numbers&nbsp;{{math|''x''}} except the non-positive integers, and (3) {{math|1=lim<sub>''m''→+∞</sub> (''H''<sub>''m''+''x''</sub> − ''H''<sub>''m''</sub>) = 0}} for all complex values&nbsp;{{math|''x''}}.

This last formula can be used to show that
<math display="block"> \int_0^1 H_x \, dx = \gamma, </math>
where&nbsp;{{math|''γ''}} is the [[Euler–Mascheroni constant]] or, more generally, for every&nbsp;{{math|''n''}} we have:
<math display="block"> \int_0^nH_{x}\,dx = n\gamma + \ln(n!) .</math>

===Special values for fractional arguments===
There are the following special analytic values for fractional arguments between 0 and 1, given by the integral
<math display="block">H_\alpha = \int_0^1\frac{1-x^\alpha}{1-x}\,dx\, .</math>

More values may be generated from the recurrence relation
<math display="block"> H_\alpha = H_{\alpha-1}+\frac{1}{\alpha}\,,</math>
or from the reflection relation
<math display="block"> H_{-\alpha}-H_{\alpha-1} = \pi\cot{(\pi\alpha)}.</math>

For example:
<math display="block"> \begin{align}
H_{\frac{1}{2}} &= 2 - 2\ln 2 \\
H_{\frac{1}{3}} &= 3 - \frac{\pi}{2\sqrt{3}} - \frac{3}{2}\ln 3 \\
H_{\frac{2}{3}} &= \frac{3}{2}+\frac{\pi}{2\sqrt{3}} - \frac{3}{2}\ln 3 \\
H_{\frac{1}{4}} &= 4 - \frac{\pi}{2} - 3\ln 2 \\
H_{\frac{1}{5}} &= 5 - \frac{\pi}{2} \sqrt{1+\frac{2}{\sqrt{5}}} - \frac{5}{4} \ln 5 - \frac{\sqrt{5}}{4} \ln\left(\frac{3+\sqrt{5}}{2}\right) \\
H_{\frac{3}{4}} &= \frac{4}{3} + \frac{\pi}{2} - 3\ln 2 \\
H_{\frac{1}{6}} &= 6 - \frac{\sqrt{3}}{2} \pi - 2\ln 2 - \frac{3}{2} \ln 3 \\
H_{\frac{1}{8}} &= 8 - \frac{1+\sqrt{2}}{2} \pi - 4\ln{2} - \frac{1}{\sqrt{2}} \left(\ln\left(2 + \sqrt{2}\right) - \ln\left(2 - \sqrt{2}\right)\right) \\
H_{\frac{1}{12}} &= 12 - \left(1+\frac{\sqrt{3}}{2}\right)\pi - 3\ln{2} - \frac{3}{2} \ln{3} + \sqrt{3} \ln\left(2-\sqrt{3}\right)
\end{align}</math>

Which are computed via [[Digamma function#Gauss's digamma theorem|Gauss's digamma theorem]], which essentially states that for positive integers ''p'' and ''q'' with ''p'' < ''q''
<math display="block"> H_{\frac{p}{q}} = \frac{q}{p} +2\sum_{k=1}^{\lfloor\frac{q-1}{2}\rfloor} \cos\left(\frac{2 \pi pk}{q}\right)\ln\left({\sin \left(\frac{\pi k}{q}\right)}\right)-\frac{\pi}{2}\cot\left(\frac{\pi p}{q}\right)-\ln\left(2q\right)</math>

===Relation to the Riemann zeta function===
Some derivatives of fractional harmonic numbers are given by
<math display="block">
\begin{align}
\frac{d^n H_x}{dx^n} & = (-1)^{n+1}n!\left[\zeta(n+1)-H_{x,n+1}\right] \\[6pt]
\frac{d^n H_{x,2}}{dx^n} & = (-1)^{n+1}(n+1)!\left[\zeta(n+2)-H_{x,n+2}\right] \\[6pt]
\frac{d^n H_{x,3}}{dx^n} & = (-1)^{n+1}\frac{1}{2}(n+2)!\left[\zeta(n+3)-H_{x,n+3}\right].
\end{align}
</math>

And using [[Taylor series|Maclaurin series]], we have for ''x'' < 1 that
<math display="block">
\begin{align}
H_x & = \sum_{n=1}^\infty (-1)^{n+1}x^n\zeta(n+1) \\[5pt]
H_{x,2} & = \sum_{n=1}^\infty (-1)^{n+1}(n+1)x^n\zeta(n+2) \\[5pt]
H_{x,3} & = \frac{1}{2}\sum_{n=1}^\infty (-1)^{n+1}(n+1)(n+2)x^n\zeta(n+3).
\end{align}
</math>

For fractional arguments between 0 and 1 and for ''a'' > 1,
<math display="block">
\begin{align}
H_{1/a} & = \frac{1}{a}\left(\zeta(2)-\frac{1}{a}\zeta(3)+\frac{1}{a^2}\zeta(4)-\frac{1}{a^3} \zeta(5) + \cdots\right) \\[6pt]
H_{1/a, \, 2} & = \frac{1}{a}\left(2\zeta(3)-\frac{3}{a}\zeta(4)+\frac{4}{a^2}\zeta(5)-\frac{5}{a^3} \zeta(6) + \cdots\right) \\[6pt]
H_{1/a, \, 3} & = \frac{1}{2a}\left(2\cdot3\zeta(4)-\frac{3\cdot4}{a}\zeta(5)+\frac{4\cdot5}{a^2}\zeta(6)-\frac{5\cdot6}{a^3}\zeta(7)+\cdots\right).
\end{align}
</math>

==See also==
* [[Watterson estimator]]
* [[Tajima's D]]
* [[Coupon collector's problem]]
* [[Jeep problem]]
* [[100 prisoners problem]]
* [[Riemann zeta function]]
* [[List of sums of reciprocals]]
* [[False discovery rate#Benjamini–Yekutieli procedure]]
* [[Block-stacking problem]]

==Notes==
{{Reflist|refs=
<ref name=ConwayGuy>
{{Cite book
| last1 = John H. | first1 = Conway
| last2 = Richard K. | first2 = Guy
| title = The book of numbers
| year = 1995
| publisher = Copernicus
}}</ref>
}}

==References==
* {{cite journal |author1=Arthur T. Benjamin |author2=Gregory O. Preston |author3=Jennifer J. Quinn |url=http://www.math.hmc.edu/~benjamin/papers/harmonic.pdf |title=A Stirling Encounter with Harmonic Numbers |year=2002 |journal=[[Mathematics Magazine]] |volume=75 |issue=2 |pages=95–103 |doi=10.2307/3219141 |jstor=3219141 |citeseerx=10.1.1.383.722 |access-date=2005-08-08 |archive-url=https://web.archive.org/web/20090617002133/http://www.math.hmc.edu/~benjamin/papers/harmonic.pdf |archive-date=2009-06-17 |url-status=dead }}
* {{cite book |author=Donald Knuth |author-link=Donald Knuth |title=The Art of Computer Programming |volume=1: ''Fundamental Algorithms'' |edition=Third |publisher=Addison-Wesley |year=1997 |isbn=978-0-201-89683-1 |chapter=Section 1.2.7: Harmonic Numbers |pages=75–79}}
* Ed Sandifer, ''[http://www.maa.org/editorial/euler/How%20Euler%20Did%20It%2002%20Estimating%20the%20Basel%20Problem.pdf How Euler Did It — Estimating the Basel problem] {{Webarchive|url=https://web.archive.org/web/20050513105944/http://www.maa.org/editorial/euler/How%20Euler%20Did%20It%2002%20Estimating%20the%20Basel%20Problem.pdf |date=2005-05-13 }}'' (2003)
* {{cite journal
 | last1 = Paule | first1 = Peter | author1-link = Peter Paule
 | last2 = Schneider | first2 = Carsten
 | doi = 10.1016/s0196-8858(03)00016-2
 | issue = 2
 | journal = Adv. Appl. Math.
 | pages = 359–378
 | title = Computer Proofs of a New Family of Harmonic Number Identities
 | url = http://www.risc.uni-linz.ac.at/publications/download/risc_200/HarmonicNumberIds.pdf
 | volume = 31
 | year = 2003}}
* {{cite journal |author=Wenchang Chu |url=http://www.combinatorics.org/Volume_11/PDF/v11i1n15.pdf |title=A Binomial Coefficient Identity Associated with Beukers' Conjecture on Apery Numbers |year=2004 |journal=The Electronic Journal of Combinatorics |volume=11 |pages=N15|doi=10.37236/1856 |doi-access=free }}

==External links==
* {{MathWorld|urlname=HarmonicNumber |title=Harmonic Number}}

{{PlanetMath attribution|id=3421|title=Harmonic number}}

{{DEFAULTSORT:Harmonic Number}}
[[Category:Number theory]]