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:

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:

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.

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. }

• Kod źródłowy Implementacja z listą
• Kod źródłowy Implementacja oszczędna

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).

• Kod źródłowy Zadanie 1