harmonic number

harmonic number (tsz. harmonic numbers)

1. (informatika) harmonikus szám

A harmonikus számok a matematika és számítástudomány egy gyakran előforduló számsora, amely az egymást követő reciprokok összegeként van definiálva.

Az első ${\textstyle n}$ darab harmonikus szám összege:

$${\displaystyle H_{n}=\sum _{k=1}^{n}{\frac {1}{k}}=1+{\frac {1}{2}}+{\frac {1}{3}}+\dots +{\frac {1}{n}}}$$

Ez az ${\textstyle n}$-edik harmonikus szám.

• ${\textstyle H_{1}=1}$
• ${\textstyle H_{2}=1+{\frac {1}{2}}=1.5}$
• ${\textstyle H_{3}=1+{\frac {1}{2}}+{\frac {1}{3}}\approx 1.833}$
• ${\textstyle H_{4}=1+{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}=2.083\ldots }$

A harmonikus számok lassan növekednek. A ${\textstyle H_{n}}$ értéke közelíthető:

$${\displaystyle H_{n}\approx \ln(n)+\gamma +{\frac {1}{2n}}-{\frac {1}{12n^{2}}}+\cdots }$$

ahol ${\textstyle \gamma \approx 0.5772}$ az Euler–Mascheroni állandó.

• Algoritmuselmélet – pl. az átlagos összehasonlítások száma a quickselect vagy quicksort algoritmusban.
• Valószínűségszámítás – például várható értékek számításánál.
• Kombinatorika – pl. részhalmazok átlagos tulajdonságainál.
• Analitikus számelmélet – prímszámok, zéta-függvény közelítései.

#include <iostream>

double harmonic(int n) {
    double H = 0.0;
    for (int k = 1; k <= n; ++k)
        H += 1.0 / k;
    return H;
}

int main() {
    int n = 10;
    std::cout << "H(" << n << ") = " << harmonic(n) << std::endl;
}

• A harmonikus sor nem konvergens: ${\textstyle \lim _{n\to \infty }H_{n}=\infty }$
• Ugyanakkor nagyon lassan divergál (logaritmikusan).

• harmonic number - Szótár.net (en-hu)
• harmonic number - Sztaki (en-hu)
• harmonic number - Merriam–Webster
• harmonic number - Cambridge
• harmonic number - WordNet
• harmonic number - Яндекс (en-ru)
• harmonic number - Google (en-hu)
• harmonic number - Wikidata
• harmonic number - Wikipédia (angol)