Liczby doskonałe
Wprowadzenie
Liczba doskonała to liczba naturalna równa sumie swoich właściwych dzielników (wszystkich dzielników z wyjątkiem samej liczby).
Matematycznie: liczba n jest doskonała ⟺ σ(n) = 2n, gdzie σ(n) to suma wszystkich dzielników n.
Przykłady liczb doskonałych:
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
8128 = 1 + 2 + 4 + 8 + ... + 4064
Liczby doskonałe są fascynujące ze względu na:
- Rzadkość (znamy tylko 51 liczb doskonałych!)
- Związek z liczbami pierwszymi Mersenne'a
- Własności matematyczne (wszystkie znane są parzyste)
- Historię (znane od czasów starożytnej Grecji)
- Nierozwiązane problemy (czy istnieją nieparzyste liczby doskonałe?)
- Piękno matematyczne (elegancja wzorów i własności)
Definicja i podstawy
Funkcja sumy dzielników σ(n)
σ(n) = suma wszystkich dzielników liczby n (włącznie z 1 i n)
Wyjście:
=== Funkcja sumy dzielników σ(n) ===
n Dzielniki σ(n) 2n Doskonała?
---------------------------------------------------------------------------
6 [1, 2, 3, 6] 12 12 ✓ TAK
12 [1, 2, 3, 4, 6, 12] 28 24 ✗ NIE
28 [1, 2, 4, 7, 14, 28] 56 56 ✓ TAK
30 [1, 2, 3, 5, 6, 10, 15, 30] 72 60 ✗ NIE
100 [1, 2, 4, 5, 10]...[50, 100] 217 200 ✗ NIE
Sprawdzanie liczb doskonałych
Metoda podstawowa
Wyjście:
=== Sprawdzanie liczb doskonałych ===
Liczby doskonałe w zakresie [1, 100]:
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
Twierdzenie Eulera-Mersenne'a
Liczby Mersenne'a
Liczba Mersenne'a: Mp = 2^p - 1 gdzie p jest liczbą pierwszą
Pierwsza Mersenne'a: Mp jest pierwsza
Wyjście:
=== Liczby Mersenne'a ===
p Mp = 2^p - 1 Mp pierwsza? Bin(Mp)
----------------------------------------------------------------------
2 3 ✓ TAK 0b11
3 7 ✓ TAK 0b111
5 31 ✓ TAK 0b11111
7 127 ✓ TAK 0b1111111
11 2047 ✗ NIE 0b11111111111
13 8191 ✓ TAK 0b1111111111111
17 131071 ✓ TAK 0b111111111111111...
19 524287 ✓ TAK 0b111111111111111...
23 8388607 ✗ NIE 0b111111111111111...
29 536870911 ✗ NIE 0b111111111111111...
31 2147483647 ✓ TAK 0b111111111111111...
Twierdzenie Eulera-Mersenne'a
Twierdzenie: Jeśli 2^p - 1 jest pierwsza, to 2^(p-1) × (2^p - 1) jest doskonała.
Wszystkie parzyste liczby doskonałe mają tę postać!
Wyjście:
=== Twierdzenie Eulera-Mersenne'a ===
p Mp = 2^p - 1 Liczba doskonała = 2^(p-1) × Mp Sprawdzenie
--------------------------------------------------------------------------------
2 3 6 ✓
3 7 28 ✓
5 31 496 ✓
7 127 8128 ✓
13 8191 33550336 (za duża)
Znajdowanie liczb doskonałych
Metoda 1: Brute force
Wyjście:
=== Liczby doskonałe - brute force ===
Zakres: [1, 10,000]
Znaleziono: 3 liczb doskonałych
Czas: 0.3421 s
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064
Metoda 2: Przez liczby Mersenne'a (szybsza!)
Wyjście:
=== Liczby doskonałe - metoda Mersenne'a ===
Wykładniki p: [2, 20]
Znaleziono: 6 liczb doskonałych
Czas: 0.0012 s
p Mp (pierwsza Mersenne'a) Liczba doskonała
----------------------------------------------------------------------
2 3 6
3 7 28
5 31 496
7 127 8128
13 8191 33550336
17 131071 2^16 × 131071 ≈ 8.59e+09
19 524287 2^18 × 524287 ≈ 1.37e+11
Klasyfikacja liczb według sumy dzielników
Liczby obfite i niedoborne
Wyjście:
=== Klasyfikacja liczb ===
n σ(n) 2n Typ Nadmiar/Niedobór
------------------------------------------------------------
6 12 12 DOSKONAŁA 0
12 28 24 Obfita +4
18 39 36 Obfita +3
20 42 40 Obfita +2
24 60 48 Obfita +12
28 56 56 DOSKONAŁA 0
30 72 60 Obfita +12
36 91 72 Obfita +19
40 90 80 Obfita +10
Gęstość liczb obfitych
Wyjście:
=== Gęstość typów liczb ===
Zakres Doskonałe Obfite Niedoborne
------------------------------------------------------------
[1, 100] 2 ( 2.00%) 21 (21.00%) 77 (77.00%)
[1, 1000] 3 ( 0.30%) 247 (24.70%) 750 (75.00%)
[1, 10000] 3 ( 0.03%) 2486 (24.86%) 7511 (75.11%)
Własności liczb doskonałych
Własność 1: Wszystkie znane są parzyste
Wyjście:
=== Własności liczb doskonałych ===
Liczba doskonała: 6
Parzysta: TAK
Postać Eulera-Mersenne'a: 2^1 × (2^2 - 1)
Mp = 3 (pierwsza Mersenne'a)
Suma cyfr: 6
Ostatnia cyfra: 6
Liczba doskonała: 28
Parzysta: TAK
Postać Eulera-Mersenne'a: 2^2 × (2^3 - 1)
Mp = 7 (pierwsza Mersenne'a)
Suma cyfr: 10
Ostatnia cyfra: 8
Liczba doskonała: 8128
Parzysta: TAK
Postać Eulera-Mersenne'a: 2^6 × (2^7 - 1)
Mp = 127 (pierwsza Mersenne'a)
Suma cyfr: 19
Ostatnia cyfra: 8
Własność 2: Suma odwrotności dzielników
Wyjście:
=== Suma odwrotności dzielników ===
n Typ ∑(1/d) Własność
-------------------------------------------------------
6 DOSKONAŁA 2.000000 = 2
12 Obfita 2.333333 ≠ 2
28 DOSKONAŁA 2.000000 = 2
30 Obfita 2.400000 ≠ 2
496 DOSKONAŁA 2.000000 = 2
Nierozwiązane problemy
Czy istnieją nieparzyste liczby doskonałe?
Wyjście:
=== Poszukiwanie nieparzystych liczb doskonałych ===
Brak nieparzystych liczb doskonałych w zakresie [1, 100000]
Fakt: Dotychczas nie znaleziono ŻADNEJ nieparzystej liczby doskonałej!
Wiemy jednak, że jeśli istnieje, to:
- Ma > 10^1500 cyfr
- Ma co najmniej 101 czynników pierwszych
- Nie jest podzielna przez 105
Złożoność obliczeniowa
Porównanie metod
| Metoda | Złożoność | Zakres praktyczny |
|---|---|---|
| Brute force | O(n√n) | Do ~10⁶ |
| Przez Mersenne'a | O(k × √Mp) | Nielimitowana (znamy 51) |
gdzie: - n = górna granica przeszukiwania - k = liczba pierwszych p do sprawdzenia - Mp = 2^p - 1
Podsumowanie
Kluczowe fakty o liczbach doskonałych
✅ Definicja: σ(n) = 2n (suma dzielników = 2n) ✅ Rzadkość: Znamy tylko 51 liczb doskonałych ✅ Twierdzenie Eulera-Mersenne'a: n = 2^(p-1) × (2^p - 1) gdzie Mp pierwsza ✅ Wszystkie znane są parzyste: Nieznana nieparzysta ✅ Suma odwrotności dzielników: ∑(1/d) = 2
Znane liczby doskonałe (pierwsze 8)
1. 6 = 2¹ × (2² - 1)
2. 28 = 2² × (2³ - 1)
3. 496 = 2⁴ × (2⁵ - 1)
4. 8128 = 2⁶ × (2⁷ - 1)
5. 33550336 = 2¹² × (2¹³ - 1)
6. 8589869056 = 2¹⁶ × (2¹⁷ - 1)
7. 137438691328 = 2¹⁸ × (2¹⁹ - 1)
8. 2305843008139952128 = 2³⁰ × (2³¹ - 1)
Nierozwiązane problemy
❓ Czy istnieją nieparzyste liczby doskonałe? ❓ Czy istnieje nieskończenie wiele liczb doskonałych? ❓ Czy wszystkie liczby doskonałe kończą się na 6 lub 28?
Co dalej?
Po opanowaniu liczb doskonałych, następne kroki to:
- Lekcja 71: Pierwiastkowanie - metoda Newtona
- Algorytm aproksymacji pierwiastków
- Pierwiastki wyższych stopni
-
Zastosowania numeryczne
-
Lekcja 72: Szybkie potęgowanie
- Algorytm binarny
- Potęgowanie modularne
-
Zastosowania w kryptografii
-
Dalsze tematy: Liczby zaprzyjaźnione, liczby Fermata, liczby Catalana
Zadania praktyczne
Zadanie 1: Znajdź piątą liczbę doskonałą
Użyj metody Mersenne'a do znalezienia 5. liczby doskonałej.
Zadanie 2: Liczby zaprzyjaźnione
Znajdź pary liczb zaprzyjaźnionych: σ(a) - a = b i σ(b) - b = a.
Zadanie 3: Wariancja obfitości
Dla liczb od 1 do 1000, oblicz średnią i odchylenie standardowe wartości (σ(n) - 2n).
Zadanie 4: Wizualizacja
Stwórz wykres pokazujący stosunek σ(n)/2n dla liczb od 1 do 1000.
Zadanie 5: Test tw. Eulera-Mersenne'a
Sprawdź, czy wszystkie liczby doskonałe ≤ 10⁹ mają postać 2^(p-1) × (2^p - 1).
Następna lekcja: Pierwiastkowanie - metoda Newtona