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

Liczby Niedotykalne

Definicja

Liczba Niedotykalna to taka liczba naturalna n, która nie jest sumą wszystkich dzielników właściwych jakiejkolwiek liczby naturalnej (włączając ją samą).

Przykład

Najmniejszą liczbą Niedotykalną jest liczba 2. Nie ma żadnej liczby naturalnej, której suma właściwa wynosi 2. Jedyną taką możliwością byłoby np. 2, ale jeśli liczba jest podzielna 2 to i przez 1, więc suma dzielników właściwych wyniesie wtedy dokładnie 3. Z kolei każdy dzielnik dodajemy do sumy maksymalnie raz, więc 1 i 1 jest niemożliwe.

Z kolei liczba 3 już nie może być liczbą Niedotykalną, ponieważ dzielniki liczby 4 to 2 i 1 co w sumie daje 3. Wspomniana liczba 4 też nie jest liczbą pierwszą, ponieważ jest sumą dzielników właściwych liczby 9: 4 = 1 + 3.

Ciąg liczb

Liczby można ustawić w następujący ciąg: 2, 5, 52, 88, 96, 120, 124, 146, 162, 188, ..

Liczb Niedotykalnych jest nieskończenie wiele. Przypuszcza się, że istnieje tylko jedna nieparzysta liczba Niedotykalna, która ma wartość 5.

Implementacja

Zadanie

Napisz program, który znajdzie wszystkie liczby Niedotykalne w zakresie [1, n]. Program powinien wypisać wszystkie znalezione liczby na konsole.

Strategia

Szukając liczb Niedotykalnych warto zadeklarować tablicę możliwych kandydatów tj. początkowo wszystkie liczby z zakresu [1, n] są potencjalnymi kandydatami. Dopiero później w trakcie obliczeń kolejne liczby zostaną wykreślone z listy. Wykreślanie będzie przebiegać następująco: dla kolejnych liczb wyliczamy sumę dzielników właściwych i jeśli taka wartość na liście nie została wykreślona to to robimy.

Istnieje jednak problem z ustaleniem zakresu liczb dla których zostanie wykonane wykreślanie. Podany wcześniej przykład z liczbą 4 wskazuje, że należy wziąć liczbę spoza zakresu [1, n]. Przypuszczalnie po wyliczeniu wszystkich liczb z zakresu [1, n2] na liście nie zostaną wykreślone jedynie liczby Niedotykalne.

Dowód Założenia

Nieformalny dowód tego stwierdzenia polega na tym, że nie bierzemy w nim pod uwagę liczb pierwszych dla których suma dzielników właściwych wynosi 1. Wtedy najmniejszą sumę dzielników właściwych będzie mieć n2 jako, że dzielnikami są wtedy co najmniej 1 i n, więc jest to liczba, której nie da się już wykreślić na liście. Dla każdej poprzedniej i-tej liczbie na liście i2 < n2.

Program

Sumowanie dzielników

Przed przystąpieniem do wykreślania warto napisać funkcję pomocniczą do sumowania dzielników właściwych sumaDzielnikow(), która przyjmuje jeden argmument a.

C++
C#
  1. int sumaDzielnikow(int a) {
  2.   int suma = 0;
  3.   for (int i = 1; i <= a / 2; i++)
  4.     if (a % i == 0)
  5.       suma += i;
  6.   return suma;
  7. }

(2.) Inicjalizacja sumy. Potem wyszukiwanie (3.) kolejnych dzielników od 1 do n/2 włącznie, ponieważ najmniejszy dzielnik większy od 1 to 2, więc nie ma potrzeby sprawdzać zakresu (n/2 n] w celu znalezienia dzielników. (4.) Każdy znaleziony dzielnik należy (5.) dodać do sumy. Na koniec (6.) zwraca jest wartość wyznaczonej sumy.

Szukanie liczb Niedotykalnych

Na początku wyszukiwania liczb Niedotykalnych należy zadeklarować tablicę z której będzie można wykreślać liczby, które nie mogą należeć do szukanego zbioru. Początkowo wszystkie liczby powinny zostać uznane za należące.

C++
C#
  1. void szukajNiedotykalnych(int n) {
  2.   bool* lista = new bool[n + 1];
  3.   for (int i = 0; i <= n; i++)
  4.     lista[i] = true;
  5.   for (int i = 1; i <= n*n + 1; i++) {
  6.     int s = sumaDzielnikow(i);
  7.     if (s <= n)
  8.       lista[s] = false;
  9.   }
  10.   for (int i = 1; i <= n; i++)
  11.     if(lista[i])
  12.       cout << i << " ";
  13. }

(2. - 5.) Deklaracja tablicy i oznaczenie wszystkich jako należące. Następnie (6.) dla każdej liczby z zakresu [1, n2 + 1] (7.) wyliczamy sumę jej dzielników i (8.) jeśli to możliwe to (9.) wykreślamy tę wartość z listy. Dopiero po wykreśleniu wszystkich możliwych sum można przejść do (11. - 13.) wypisania znalezionych liczb Niedotykalnych.

Testowanie funkcji

Poniższy kod wczytuje od użytkownika górne ograniczenie zakresu poszukiwań, a następnie wypisuje na konsolę wszystkie znalezione liczby Niedotykalne.

C++
C#
  1. int main() {
  2.   int n;
  3.   cout << "W jakim zakresie [1, n] szukac liczb Niedotykalnych?\n";
  4.   cin >> n;
  5.   cout << "\nW zakresie [1, " << n << "] sa:\n";
  6.   szukajNiedotykalnych(n);
  7.   system("pause");
  8.   return 0;
  9. }
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1