Liczyba nadwyrazna

Liczby nadwyrazne (zwane także liczbami obfitymi) to podklasa liczb naturalnych, w których suma wszystkich dzielników (włącznie z liczbą samą w sobie) jest większa niż dwukrotność tej liczby. Formalnie, liczba naturalna n jest nadwyrazna, jeżeli

σ(n) > 2 · n,

gdzie σ(n) oznacza funkcję sumy dzielników.

Definicja i przykłady

W przeciwieństwie do liczb doskonałych, które spełniają równość σ(n) = 2 · n, oraz liczb deficytowych, dla których σ(n) < 2 · n, liczby nadwyrazne „przekraczają” tę granicę.

Najmniejsze liczby nadwyrazne to:

12 – σ(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28 > 24
18 – σ(18) = 1 + 2 + 3 + 6 + 9 + 18 = 39 > 36
20 – σ(20) = 1 + 2 + 4 + 5 + 10 + 20 = 42 > 40
24 – σ(24) = 60 > 48
30 – σ(30) = 72 > 60

Historia

Pierwsze wzmianki o liczbach nadwyraznych pojawiły się w starożytnej greckiej literaturze matematycznej; w „Elementach” Euklidesa nie ma ich oddzielnej klasy, ale już wtedy rozważano sumy dzielników. Systematyczne badania nad liczbami nadwyraznymi rozpoczęły się w XIX wieku, gdy Leonhard Euler wprowadził funkcję sigma σ(n). W latach 20. XX wiecznia przyczynili się do rozwoju tematu Srinivasa Ramanujan i Godfrey Hardy, analizując ich gęstość oraz relacje z liczbami pierwszymi.

Właściwości

Wzajemna zależność z liczbami doskonałymi i deficytowymi. Każda liczba naturalna należy dokładnie do jednej z trzech klas: doskonałe, nadwyrazne lub deficytowe.
Dziedziczenie przez wielokrotności. Jeżeli n jest liczbą nadwyrazną, to każdy jej wielokrotność k·n (gdzie k ≥ 2) również jest nadwyrazny.
Liczby pierwsze nie są nadwyrazne. Dla każdej liczby pierwszej p zachodzi σ(p) = 1 + p = p + 1 < 2 · p.
Gęstość. Zbiór liczb nadwyraznych ma naturalną gęstość równą 1; czyli „prawie wszystkie” liczby naturalne są nadwyrazne.
Przeciętna nadwyżka. Dla liczby n nadwyżka definiowana jest jako Δ(n) = σ(n) − 2 · n. Dla liczb nadwyraznych Δ(n) > 0.

Klasyfikacje wewnątrz zbioru liczb nadwyraznych

Liczby nadwyrazne prymarne. Są to takie liczby n, które nie mają żadnego dzielnika nadwyraznego mniejszego od n. Przykładem jest 12.
Liczby dziwne (ang. weird numbers). Są to liczby nadwyrazne, dla których nie istnieje podzbiór dzielników właściwych sumujący się dokładnie do n. Najmniejsza liczba dziwna to 70.
Liczby superabundant. Dla tych liczb stosunek σ(n) / n jest większy niż dla wszystkich mniejszych liczb.

Algorytmy i testowanie

Sprawdzanie, czy liczba jest nadwyrazna, wymaga obliczenia sumy jej dzielników. Najprostszy algorytm działa w czasie O(√n):

int sigma(int n) {
    int suma = 1 + n;               // 1 i n zawsze są dzielnikami
    for (int d = 2; d * d <= n; ++d) {
        if (n % d == 0) {
            suma += d;
            if (d != n / d) suma += n / d;
        }
    }
    return suma;
}
bool jest_nadwyrazna(int n) {
    return sigma(n) > 2 * n;
}

Dla bardzo dużych liczb korzysta się z faktoryzacji przy pomocy metod takich jak sito Eratostenesa oraz algorytmów faktoryzacji (np. Pollarda rho).

Zastosowania

Badania w teorii liczb – liczby nadwyrazne odgrywają rolę w problemach dotyczących rozkładu dzielników oraz w analizie funkcji arytmetycznych.
Algorytmy kryptograficzne – chociaż samych liczb nadwyraznych nie używa się bezpośrednio, ich własności wpływają na szacowanie gęstości liczb pierwszych w pewnych testach.
Problemy kombinatoryczne – pojęcie nadwyżki wykorzystywane jest przy analizie sum podzbiorów dzielników w zagadnieniach typu „partition problem”.

Powiązane pojęcia

Na temat liczb nadwyraznych przeczytasz także w artykułach:

W matematyce liczby nadwyrazne stanowią fascynujący przedmiot badań, łącząc elementy teorii liczb, kombinatoryki oraz analizy algorytmicznej.