Strona główna » Algorytmy » Teoria Liczb » Liczby Zachwycające
 

Liczby Zachwycające

Definicja

Liczbę naturalną n można nazwać liczbą zachwycającą kiedy istnieje taki dzielnik d liczby n, że n = σ(n) - 2d, gdzie σ to funkcja sumująca wszystkie dzielniki właściwe liczby.

Oficjalną definicje można nieco uprościć: liczba zachwycająca to taka liczba n, której suma dzielników właściwych, gdzie jeden jest ujemny wynosi tyle co dwukrotność liczby n.

Kolejne liczby zachwycające to: 12, 20, 24, 30, 40, 42, 54, 56, 66, 70, ...

Przykład

Najmniejszą liczbą zachwycającą jest 12, ponieważ jej dzielniki właściwe to {1, 2, 3, 4, 6}. Z tych liczb 12 można uzyskać następująco: 12 = 1 + 2 + 3 - 4 + 6.

Implementacja z listą

Metoda

Generalnie w celu sprawdzenia czy liczba jest zachwycająca można przykładowo zapamiętać wszystkie dzielniki. W trakcie lub po znalezieniu wszystkich zsumować je, a następnie próbować z każdym dzielnikiem sprawdzić czy spełni wspomnianą w definicji zależność. W trakcie implementowania tego rozwiązania należy pamiętać, że liczba n może mieć, aż n/2 dzielników.

Tego typu wymaga bardzo dużo pamięci. Złożoność jest liniowa i wynosi Θ(n). Tę samą złożoność posiada czas wykonywania programu.

Czy zachwycająca?

Poniższy kod jest implementacją pomysłu powyżej:

C++
C#
  1. bool czyZachwycająca(int n) {
  2.   int* dzielniki = new int[n / 2];
  3.   int suma = 0, ile = 0;
  4.   for (int i = 1; i <= n / 2; i++) {
  5.     if (n % i == 0) {
  6.       suma += i;
  7.       dzielniki[ile++] = i;
  8.     }
  9.   }
  10.   for (int i = 0; i < ile; i++) {
  11.     if (n == suma - 2 * dzielniki[i]) {
  12.       delete dzielniki;
  13.       return true;
  14.     }
  15.   }
  16.   delete dzielniki;
  17.   return false;
  18. }

(1.) Funkcja przyjmuje jeden argument: n - liczbę do sprawdzenia. (2.) Przygotowanie listy pod zapisanie dzielników oraz (3.) inicjalizacja zmiennych suma - sumuje dzielniki oraz ile - przechowuje ile dzielników zostało znalezionych. Dalej (4. - 9.) wyszukiwane są dzielniki i jeśli takowy zostanie znaleziony to (7.) jest on dopisywany do listy na kolejne wolne miejsce. (10. - 15.) Kolejny etap polega na sprawdzeniu czy którykolwiek z dzielników spełnia założenia. Jeśli tak to (12.) należy zwolnić pamięć i (13.) zwrócić prawdę. (17.) Jednak jeśli żaden z dzielników nie okaże się właściwy to należy zwrócić fałsz.

Implementacja Oszczędna

Metoda

Zadanie to można rozwiązać bez zapisywania wszystkich dzielników. Na początku wystarczy znaleźć dzielniki w pętli, aby wyznaczyć ich sumę, a potem powtórzyć szukanie dzielników, ale tym razem sprawdzać warunek z definicji.

Zaletą takiego rozwiązania jest fakt, że złożoność pamięciowa jest niezależna i wynosi Θ(1). Warto jednak zwrócić uwagę, że zastosowany sposób zwiększa ilość wykonywanych sprawdzeń czy liczba jest dzielnikiem dwa razy, ale i tak złożoność czasowa pozostanie liniowa Θ(n).

Kod

Nagłówek funkcji pozostaje niezmieniony:

C++
C#
  1. bool czyZachwycająca(int n) {
  2.   int suma = 0;
  3.   for (int i = 1; i <= n / 2; i++) {
  4.     if (n % i == 0) {
  5.       suma += i;
  6.     }
  7.   }
  8.   for (int i = 1; i <= n / 2; i++) {
  9.     if (n % i == 0 && n == suma - 2 * i) {
  10.       return true;
  11.     }
  12.   }
  13.   return false;
  14. }

(2.) Początkowo przyjmij sumę równą 0. (3. - 8.) Zsumuj wszystkie dzielniki właściwe liczby, a następnie (9. - 13.) jeszcze raz przechodząc po wszystkich dzielnikach sprawdź czy którykolwiek z nich wstawiony do wzoru pasuje. Jeśli tak to (11.) zwróć prawdę. Jeśli jednak dzielnik nie zostanie znaleziony to (14.) zwróć fałsz.

Testowanie funkcji

Poniższa funkcja testująca wypisuje wszystkie liczby zachwycające z przedziału [1, 100]. Pasuje do obu implementacji.

C++
C#
  1. int main() {
  2.   for (int i = 1; i <= 100; i++) {
  3.     if (czyZachwycająca(i)) {
  4.       cout << i << endl;
  5.     }
  6.   }
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Zadanie 1

Napisz funkcję void szukajParZachwycających(long long lewy, long long prawy), która w danym zakresie będzie wyszukiwać pary liczb zachwycających, które występują obok siebie (czyli ich różnica wynosi 1).

Ostrzeżenie! Ponizej 1012 istnieją takie dwie 11 cyfrowe pary. Są to: (29691198404, 29691198405) oraz (478012798575, 478012798576). Z tego względu zaleca się sprawdzenie jak najmniejszego zakresu. Obliczenia mogą trwać bardzo długo, dlatego należy pamiętać o jak najlepszej optymalizacji.