Strona główna » Algorytmy » Teoria Liczb » Liczby Hilberta
 

Liczby Hilberta

https://mattomatti.com/a91

Definicja

Liczby Hilberta są to takie liczby naturalne, które są postaci n = 4k + 1. (Innymi słowy liczbą Hilberta jest każda liczba naturalna, której reszta dzielenia przez 4 daje 1.) Dla liczb Hilberta wprowadza się pojęcie liczb pierwszych Hilberta analogiczne do definicji dla liczb naturalnych. Liczba może zostać nazwana liczbę Hilbertą wtedy i tylko wtedy, gdy nie jest podzielna przez żadna liczbę Hilberta mniejszą od niej samej, prócz 1. Wszystkie pozostałe liczby to liczby złożone Hilberta. Liczba 1 nie zalicza się do żadnej z wymienionych grup.

Przykład

Liczby HilbertaCiąg
Wszystkie1, 5, 9, 13, 17, ..
Pierwsze5, 9, 13, 17, 21, ..
Złożone25, 45, 65, 81, 85, ..

Właściwości

Liczby Hilberta charakteryzują się faktem, że ich rozkład na liczby pierwsze Hilberta nie zawsze jest jednoznaczny. Przykładem jest rozkład liczby 1089, która ma dwa różne rozkłady na liczby pierwsze Hilberta: 1089 = 121 * 9 = 33 * 33. Począwszy od najmniejszych liczb właściwość tę mają jeszcze następujące liczby: 441, 693, 1089, 1197, 1449, ...

Implementacja

Liczba Hilberta

Wyliczanie k-tej liczby Hilberta nie powinno stanowić problemu:

  1. int hilbert_n(int k) {
  2.   return 4 * k + 1;
  3. }

Jednak częściej zamiast wyliczać n-tą liczbę Hilberta wygodniej będzie sprawdzić czy dana liczba jest taką liczbą. Wtedy należy pamiętać, że przy dzieleniu przez cztery reszta musi wynieść 1:

  1. bool czyHilbert(int a) {
  2.   return (a % 4 == 1);
  3. }

Wypisywanie liczb Hilberta

Istnieją co najmniej trzy metody wypisywania kolejnych liczb Hilberta: pierwsza z nich wypisze n liczb Hilberta poprzez wypisanie ich funkcją hilbert_n(). W przypadku poszukiwania w liczb w określonym zakresie [a, b] lepiej sprawdzi się funkcja czyHilbert(), która sprawdzi każdą liczbę z zakresu i sprawdzi czy jest liczbą Hilberta. Jednak najlepszą metodą jest napisanie funkcji hilbert_wypiszn(), która wypisze pierwsze n liczb i nie będzie za każdym razem wyliczała wszystkiego od nowa i nie będzie sprawdzać każdej liczby z zakresu.

  1. void hilbert_wypiszn(int n) {
  2.   int i = 1;
  3.   do {
  4.     cout << i << " ";
  5.     i += 4;
  6.   } while (n--);
  7. }

Liczba pierwsza Hilberta

Kolejnym krokiem w implementacji jest sprawdzenie czy dana liczba jest liczbą Hilberta. Warto zwrócić uwagę, że użytkownik może podać dowolną liczbę, dlatego należy się upewnić, że podana liczba jest liczbą Hilberta. Zadanie realizuje poniższy kod:

  1. bool hilbert_czypierwsza(int a) {
  2.   if (a < 5 || !czyHilbert(a))
  3.     return false;
  4.   int a_pom = a - 4;
  5.   while (a_pom != 1) {
  6.     if (a % a_pom == 0)
  7.       return false;
  8.     a_pom -= 4;
  9.   }
  10.   return true;
  11. }

(1.) Dla podanej liczby a funkcja określi czy jest liczbą pierwszą Hilberta i zwróci to jako wartość logiczną. (2.) Upewnij się, że a to liczba Hilberta. Nie rozpatruj liczb mniejszych od najmniejszej liczby pierwszej. (3.) Zwróć fałsz jeśli liczba nie spełnia warunków wstępnej kwalifikacji. (4.) Rozpocznij poszukiwania dzielnika od liczby o 4 mniejszej. (5. - 9.) Szukaj dzielnika za każdym razem zmniejszając wartość dzielnika o 4. (7.) Jeśli w którejś iteracji dzielnik dzieli a to (8.) zwróć fałsz. (11.) Jednak jeśli nie znajdziesz dzielnika to zwróć prawdę.

Złożona liczba Hilberta

Jeśli liczba nie jest liczbą pierwszą to musi być liczbą złożoną. Należy jednak pamiętać, że wyjątkiem jest tutaj liczba 1, która nie należy do żadnej z wymienionych grup.

  1. bool hilbert_czyzlozona(int a) {
  2.   if (a <= 1)
  3.     return false;
  4.   return !hilbert_czypierwsza(a);
  5. }

Rozkład liczby Hilberta

Jednym z interesujących aspektów liczb Hilberta jest fakt, że ich rozkład nie zawsze jest jednoznaczny. Funkcja hilbert_wypiszrozklad() pozwoli to zbadać, ponieważ wypisze ona wszystkie rozkłady liczby a na czynniki pierwsze. Jednym z podstawowych problemów podczas szukania rozkładu jest zapamiętanie poprzednich dzielników. Z tego powodu zostanie zadeklarowana lista odpowiedniej długości. Można tu skorzystać z faktu, że liczba a może mieć maksymalnie czynników pierwszych. Do obliczenia tego wystarczy posłużyć się funkcją intlog(), która oblicza logarytm o odpowiedniej bazie base dla podanej liczby x:

  1. int intlog(double base, double x) {
  2.   return (int)(log(x) / log(base));
  3. }

Przechodzą do głównego algorytmu:

  1. void hilbert_wypiszrozklad(int a) {
  2.   cout << a << " ";
  3.   if (!czyHilbert(a)) {
  4.     cout << "nie jest liczba Hilberta";
  5.   } else {
  6.     if (hilbert_czypierwsza(a)) {
  7.       cout << "jest pierwsza";
  8.     } else {

(2.) Wypisz liczbę. (3.) Na początku sprawdź czy liczba jest liczbą Hilberta. Jeśli nie to (4.) wypisz odpowiedni komunikat. (5.) W przeciwnym razie jeśli jest to liczba Hilberta to sprawdź (6.) czy jest to liczba pierwsza. (7.) Jeśli tak to wypisz komunikat i zakończ funkcję. (8.) Jeśli jest to jednak złożona liczba Hilberta przejdź do szukania jej rozkładów.

  1.       int dl = intlog(5, a) + 1;
  2.       int* lista = new int[dl];
  3.       int a_pom = a - 4;
  4.       while (a_pom > 1) {
  5.         if (a % a_pom == 0 && hilbert_czypierwsza(a_pom)) {
  6.           int n = 0, d = a_pom, a_kopia = a;
  7.           while (a_kopia != 1 && d > 1) {
  8.             if (a_kopia % d == 0) {
  9.               lista[n++] = d;
  10.               a_kopia /= d;
  11.             }
  12.             else {
  13.               d -= 4;
  14.             }
  15.           }

(9.) Oblicz z ilu maksymalnie składników może składać się rozkład. (10.) Zaalokuj pamięć pod liczby z rozkładu i (11.) rozpocznij poszukiwania dzielnika. (12.) Dopóki dzielnik jest większy od 1 to (13.) sprawdź czy aktualna wartość dzielnika dzieli a i czy jest pierwsza. Jeśli oba warunki zostaną spełnione to (14.) zadeklaruj zmienną n - indeks aktualnie zapisywanej liczby, d - największy dzielnik oraz a_kopia - kopia liczb a. (15.) Dopóki liczba jest różna od 1, a istnieje jeszcze na znalezienie dzielnika to (16.) sprawdź czy d dzieli kopię liczby a. Wtedy (17. - 18.) dopisz dzielnik na listę i podziel a_kopia przez dzielnik d. Jeśli jednak d nie dzieli to (20.) zmniejsz wartość dzielnika o 4.

  1.           if (a_kopia == 1) {
  2.             n--;
  3.             cout << "= ";
  4.             for (int i = 0; i < n; i++) {
  5.               cout << lista[i] << " * ";
  6.             }
  7.             cout << lista[n] << " ";
  8.           }
  9.         }
  10.         a_pom -= 4;
  11.       }
  12.       delete[] lista;
  13.     }
  14.   }
  15.   cout << endl;
  16. }

Algorytm przyjmuje, że każdy kolejny dzielnik jest mniejszy lub równy poprzedniemu. W ten sposób ograniczana jest ilość rozkładów poprzez eliminację duplikatów np. 45 = 5 * 9 = 9 * 5, dlatego (23.) przed wypisaniem znalezionego rozkładu należy upewnić się, że kopia liczby a to 1. (25.) Wypisz znak równości i (26. - 29.) Wszystkie liczby z rozkładu.

Testowanie funkcji

W celu wypisania informacji o wszystkich liczbach z zakresu [1, 100] można skorzystać z poniższej funkcji main(). Dla każdej liczby z zakresu program wypisze czy jest liczbą Hilberta, a jeśli jest to czy jest pierwsza, albo jej rozkład na czynniki pierwsze.

  1. int main () {
  2.   for (int i = 1; i < 100; i += 4) {
  3.     hilbert_wypiszrozklad(i);
  4.   }
  5.   system("pause");
  6.   return 0;
  7. }

Zadania

Zadanie 1

Napisz funkcję hilbert_ilezrozkladems(), która dla podanego zakresu [a, b] wypisze na ekran wszystkie liczby Hilberta z zakresu, które mają dokładnie s różnych rozkładów.

Przykładowo dla zakresu [1, 10] i s = 1 zostaną zwrócone wszystkie liczby Hilberta z zakresu:

  1. 1 5 9

W przypadku zakresu [1, 1000] i s = 2 wynikiem będzie:

  1. 441 693