Strona główna » Algorytmy » Teoria Liczb » Permutacyjne liczby pierwsze
 

Permutacyjne liczby pierwsze

https://mattomatti.com/a80

Definicja

Permutacyjna liczba pierwsza to taka liczba naturalna, która jest liczbą pierwszą i każda permutacja jej cyfr tworzy również liczbą pierwszą. Takie liczby znane są również pod nazwą absolutne liczby pierwsze. Dla przypomnienia: liczba pierwsza to taka liczba naturalna, która jest podzielna tylko przez samą siebie oraz jeden. Liczbą pierwszą nie jest 1.

Przykład

Najmniejszą permutacyjną liczba pierwszą jest 2. Do tej grupy liczb należą wszystkie liczby pierwsze jednocyfrowe, ponieważ ich jedyna permutacja to ich oryginalna wartość. Przykładowej dwucyfrowej permutacyjnej liczby pierwszej jest 17, ponieważ zarówno 17 jak i 71 są liczbami pierwszymi. Jako przykład trzycyfrowej takiej liczby można podać 113, która wraz z permutacjami 131 i 311 jest permutacyjną liczbą pierwszą.

Pierwsze wyrazy

Pierwsze 10 wyrazów permutacyjnych liczb pierwszych to: 2, 3, 5, 7, 11, 13 ,17, 31, 37, 71, ...

Sprawdzanie warunku

Strategia

W przypadku sprawdzania specjalnych właściwości znalezionej liczby pierwszej należy pamiętać, że należy sprawdzić wszystkie jej permutacje czy też są liczbami pierwszymi. Kod realizujący takie sprawdzenie wygląda następująco:

  1. bool isPermutablePrime(int a) {
  2.   char* data = new char[10];
  3.   int i = 0;
  4.   do {
  5.     data[i++] = a % 10;
  6.   } while ((a /= 10) > 0);
  7.   data[i] = '\0';
  8.   bool b = permute(data, 0, i - 1);
  9.   delete[] data;
  10.   return b;
  11. }

(1.) Funkcja isPermutablePrime() przyjmuje jeden argument a, który określa liczbę do sprawdzenia, a wynikiem działania funkcji jest wartość logiczna sprawdzanego warunku. Nowe permutacje będzie łatwiej tworzyć jeśli liczba będzie zapisana jako lista cyfr, dlatego: (2.) alokacja pamięci pod cyfry i (3. - 6.) zapisanie na liście kolejnych cyfr (w kolejności odwrotnej). Następnie (7.) pobierany jest wynik sprawdzania wszystkich permutacji, (8.) dealokowana jest zarezerwowana pamięć i (9.) zwracany jest wynik.

Permutacje

Wszystkie kombinacje sprawdza funkcja permute(). Przyjmuje ona trzy argumenty: data - tablica z cyframi do permutowania, l - określa ile już wykonano zamian oraz r - ile zamian powinno zostać wykonanych.

  1. bool permute(char* data, int l, int r) {
  2.   if (l == r) {
  3.     int l = 0;
  4.     for (; r >= 0; r--) {
  5.       l *= 10;
  6.       l += data[r];
  7.     }
  8.     return isPrime(l);
  9.   } else {
  10.     for (int i = l; i <= r; i++) {
  11.       zamien(data + l, data + i);
  12.       if (!permute(data, l + 1, r))
  13.         return false;
  14.       zamien(data + l, data + i);
  15.     }
  16.   }
  17.   return true;
  18. }

(2.) Jeśli została uzyskana nowa permutacja to: (3. - 7.) zamień tablicę cyfr na liczbę i (8.) zwróć wynik testu pierwszości odczytanej liczby. (9.) Jednak jeśli permutacja nie jest ukończona to (10.) dla każdej cyfry na liście: (11.) przeprowadź zamiany dla i-tej cyfry z ostatnią. (12.) Sprawdź wynik dotychczasowych permutacji i jeśli któraś z permutacji liczb nie jest pierwsza to (13.) zwróć fałsz. Jeśli jednak (14.) znalezione dotychczas permutacje są pierwsze to wycofaj zmiany permutacji. Jeśli pętla for zakończy się i nie zostanie zwrócony fałsz to znaczy, że wszystkie permutacje są pierwsze i wtedy (17.) zwróć prawdę.

Funkcje pomocnicze

Powyższe funkcje korzystały z dwóch funkcji pomocniczej. Jedna z nich zamieniała dane na wybranych pozycjach:

  1. void zamien(char* a, char* b) {
  2.   char t = *a;
  3.   *a = *b;
  4.   *b = t;
  5. }

Druga isPrime() sprawdzała czy podana liczba jest liczbą pierwszą:

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

Testowanie funkcji

Przy pomocy poniższej funkcji można wypisać wszystkie permutacyjne liczby pierwsze z zakresu [2, 1000].

  1. int main () {
  2.   for (int i = 2; i < 1000; i++) {
  3.     if (isPermutablePrime(i)) {
  4.       cout << i << " ";
  5.     }
  6.   }
  7.   system("pause");
  8.   return 0;
  9. }

Tylko jedna permutacja

Zadanie

Pozostaje jednak pytanie ile jest unikalnych permutacji liczb pierwszych. Założenie polega na tym, że jeśli została już wcześniej wypisana permutacja jakieś liczby pierwszej to już dalsze permutacje tej liczby pierwszej nie będą wypisywane. Przykładowo jeśli zostanie już wypisane 113 to żadna z permutacji 131 i 113 nie zostanie wypisana.

Wtedy pierwsze 10 wyrazów permutacyjnych liczb pierwszych to: 2, 3, 5, 7, 11, 13 ,17, 37, 79, 113, ...

Jednym ze sposobów na rozwiązanie tego zadania byłoby zapisać wszystkie znalezione permutacyjne liczby pierwsze, a następnie przed wypisaniem kolejnej znalezionej sprawdzić czy nie jest permutacją którejś z poprzednich. Takie rozwiązanie jest prawidłowe, ale mało efektywne.

Zdecydowanie lepszym pomysłem jest zapamiętywanie minimalnej wartości wszystkich znalezionych permutacji, a następnie wypisanie liczby tylko pod warunkiem, że wypisywana liczba jest równa minimalnej znalezionej permutacji. Początkowo za minimalną wartość można przyjąć podaną liczbę. Powyższy kod wymaga drobnej poprawki, aby realizował nowe zadanie.

Zmiany w kodzie

Przede wszystkim funkcja permute() musi przyjmować dodatkowy argument min, który będzie sprawdzaną liczbą. Jeśli okaże się, że któraś z permutacji jest mniejsza od min to znaczy, że nie będzie to najmniejsza permutacyjna liczba pierwsza z danej grupy permutacji.

  1. bool permute(char* data, int l, int r, int min) {
  2.   if (l == r) {
  3.     int l = 0;
  4.     for (; r >= 0; r--) {
  5.       l *= 10;
  6.       l += data[r];
  7.     }
  8.     return l >= min && isPrime(l);
  9.   } else {
  10.     for (int i = l; i <= r; i++) {
  11.       zamien(data + l, data + i);
  12.       if (!permute(data, l + 1, r, min))
  13.         return false;
  14.       zamien(data + l, data + i);
  15.     }
  16.   }
  17.   return true;
  18. }

(1.) Funkcje permute() musi przyjmować dodatkowy argument min. (8.) Tym razem wyliczona permutacja musi nie tylko spełnić test pierwszości, ale również jej wartość musi być większa bądź równa podanemu argumentowi min. Oczywiście w trakcie (12.) rekurencyjnego wywołania funkcji należy pamiętać, że funkcja potrzebuje podania dodatkowego argumentu.

  1. bool isPermutablePrime(int a) {
  2.   char* data = new char[10];
  3.   int min = a;
  4.   int i = 0;
  5.   do {
  6.     data[i++] = a % 10;
  7.   } while ((a /= 10) > 0);
  8.   data[i] = '\0';
  9.   bool b = permute(data, 0, i - 1, min);
  10.   delete[] data;
  11.   return b;
  12. }

Funkcja isPermutablePrime() potrzebuje (3.) zapamiętać wartość a, która dalej jest modyfikowana oraz (9.) należy podać tę wartość funkcji permute() jako dodatkowy argument.

Testowanie funkcji

Funkcję można przetestować przy pomocy poprzednio podanej funkcji main().

Ćwiczenia

Zadanie 1

Napisz program, który będzie działał na zasadzie drugiego zadania, ale będzie wypisywał nie minimalną, ale maksymalną wartość permutacji znalezionej permutacyjnej liczby pierwszej.

Wynik działania funkcji powinien być następujący (w przypadku zakresu [2, 1000]):

  1. 2 3 5 7 31 71 73 97 311 733 991