Strona główna » Algorytmy » Artykuły » Liczby Samotne
 

Liczby Samotne

https://mattomatti.com/a0180

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.

C++C#
Python
  1. def czyPierwsza(a):
  2.   for i in range(2, int(math.sqrt(a)) + 1):
  3.     if (a % i == 0):
  4.       return False
  5.   return True

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

C++C#
Python
  1. def nastepnaPierwsza(a):
  2.   a += 1
  3.   while (not czyPierwsza(a)):
  4.     a += 1
  5.   return a

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

C++C#
Python
  1. def liczbySamotne(max):
  2.   wynik = [0]
  3.   roznica = 2
  4.   p1, p2, p3 = 2, 3, 5
  5.   for i in range(2, max):
  6.     if (i > p2):
  7.       p1, p2, p3 = p2, p3, nastepnaPierwsza(p3)
  8.     if (i < p2):
  9.       q = min(i - p1, p2 - i)
  10.     else:
  11.       q = min(p3 - p2, p2 - p1)
  12.     if (q > roznica):
  13.       wynik.append(i)
  14.       roznica = q
  15.   return wynik

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:

C++C#
Python
  1. max = int(input("Podaj zakres przeszukiwań:\n max = "))
  2. wynik = liczbySamotne(max)
  3. print("Znalezione liczby:")
  4. for x in wynik:
  5.   print(x, end=' ')