Liczby Samotne

Definicja

Liczby Samotne to takie liczby naturalne, których minimalna odległość do liczby pierwszej ustanawia nowy rekord. Oznacza to, że żadna poprzednia liczba nie miała tak wysokiego rekordu jak wybrana.

Przykład

Najmniejszą liczbą samotną jest 0. Jej odległość od najbliższej liczby pierwszej 2 wynosi 2.Kolejną liczbą jest 23, która znajduje się pomiędzy 19, a 29. Tutaj warto zwrócić uwagę na to, że 23 sama jest liczbą pierwszą, ale nie ma to znaczenia podczas liczenia odległości do najbliższych liczb pierwszych.

Ciąg Liczb

Liczby Samotne można ustawić w następujący ciąg: 0, 23, 53, 120, 211, 1340, 1341, 1342, 1343, 1344, 2179...

Implementacja

Liczby Pierwsze

Podczas wyszukiwania liczb Samotnych dużą rolę odgrywa skuteczność wykrywana liczb Pierwszych. Do rozpoznania czy liczba jest Pierwsza wystarczy standardowa funkcja, które opis jest w tym artykule.

1. bool czyPierwsza(int a) {
2.   for (int i = 2; i <= sqrt(a); i++)
3.     if (a % i == 0)
4.       return false;
5.   return true;
6. }

Dodatkowo przydatna okaże się funkcja nastepnaPierwsza(), która będzie wyszukiwać najbliższą liczbę Pierwszą większą od przekazanej jako argument.

1. int nastepnaPierwsza(int a) {
2.   while (!czyPierwsza(++a));
3.   return a;
4. }

Wyszukiwanie liczb Samotnych

Implementacja funkcji liczbySamotne() przyjmuje jako argument górny zakres obszaru przeszukiwań max, a jako wynik otrzymuje się listę liczb Samotnych z zakresu [0, max].

1. vector<int> liczbySamotne(unsigned int max) {
2.   vector<int> wynik;
3.   wynik.push_back(0);
4.   int roznica = 2;
5.   int p1 = 2, p2 = 3, p3 = 5;
6.   for(int i = 2; i < max; i++) {
7.     if (i > p2) {
8.       p1 = p2;
9.       p2 = p3;
10.       p3 = nastepnaPierwsza(p3);
11.     }
12.     int q;
13.     if (i < p2) {
14.       q = min(i - p1, p2 - i);
15.     } else {
16.       q = min(p3 - p2, p2 - p1);
17.     }
18.     if (q > roznica) {
19.       wynik.push_back(i);
20.       roznica = q;
21.     }
22.   }
23.   return wynik;
24. }

Funkcja na początku tworzy nową listę na które od razu dopisywane jest 0, a następnie deklaruje ostatnią różnicę o wartości 2 oraz kolejne liczby pierwsze. Następnie w pętli dla każdej liczby będzie sprawdzana jej odległość do dwóćh sąsiednich liczb Pierwszych. W zamyśle liczba i musi znajdować się w przedziale [p1, p2]. Jeśli wykroczy poza ten zakres to generowana jest kolejna trójka liczba pierwszych. Następnie trzeba stwierdzić czy rozpatrujemy liczbę pomiędzy Pierwszymi czy Pierwszą. W pierszym przypadku wybieramy mniejszą odległość pomiędzy |i - p1| oraz |i - p2|. Jednak jeśli i to liczba Pierwsza to wynosi p2 i wtedy należy wybrać mniejszą odległość pomiędzy |p1 - p2| oraz |p2 - p3|. Ostatni warunek sprawdza czy nwoa różnica q jest większa od aktualnej. Jeśli tak to został ustanowiony nowy rekord. Aktualizujemy więc różnicę, a wartość i dopisujemy na listę.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu programu:

1. int main () {
2.   unsigned int max;
3.   cout << "Podaj zakres przeszukiwan:\n max = ";
4.   cin >> max;
5.   vector<int> wynik = liczbySamotne(max);
6.   cout << "Znalezione liczby:" << endl;
7.   for (int i = 0; i < wynik.size(); i++) {
8.     cout << wynik[i] << " ";
9.   }
10.   system("pause");
11.   return 0;
12. }

• Kod źródłowy Implementacja