Liczby Uparte

Definicja

Liczby Uparte to takie liczby nieparzyste, których nie można wyrazić przy pomocy pewnej potęgi liczby 2 oraz liczby pierwszej. Oznacza to, że liczba Uparta jest postaci 2ⁱ + p, gdzie i ≥ 0.

Przykład

Najmniejszą liczbą upartą jest 1, ponieważ 2⁰ = 1, a wtedy p = 0, ale 0 nie jest liczbą pierwszą. Drugą liczbą upartą jest 127. Można to udowodnić sprawdzając wszystkie potencjalne rozkłady:

Jak wynika z tabelki niezależnie od wybranej pary warunek rozkładu nigdy nie został spełniony.

Ciąg liczb

Ustawiając liczby w ciąg otrzymujemy: 1, 127, 149, 251, 331, 337, 373, 509, 599, 701, ...

Implementacja

W celu zaimplementowania funkcji do sprawdzania czy dana liczba jest Uparta należy dodać funkcję do sprawdzania czy liczba jest pierwsza. W ten sposób możliwe jest sprawdzenie czy rozpatrywany rozkład jest prawidłowy. Więcej informacji o sprawdzaniu czy liczba jest pierwsza można znaleźć tutaj.

1. bool czyPierwsza(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. }

Teraz można przejść do pisania funkcji czyUparta(), która dla danego argumentu a zwróci wartość logiczną czy tak jest. Oto przykładowy kod funkcji:

1. bool czyUparta(int a) {
2.   if (a % 2 == 0)
3.     return false;
4.   int i = 1;
5.   while (i < a) {
6.     if (czyPierwsza(a - i))
7.       return false;
8.     i *= 2;
9.   }
10.   return true;
11. }

Sprawdzanie polega na wyliczaniu kolejnych potęg liczby dwa i sprawdzaniu czy różnica pomiędzy daną potęgą oraz sprawdzaną liczba jest liczbą pierwszą. Jeśli tak jest to należy zwrócić fałsz. Jeśli jednak pętla nie zostanie przerwana to liczba na pewno jest Upartai należy zwrócić prawdę.

Testowanie funkcji

Poniższy kod pozwala na wczytanie liczby od użytkownika, a następnie wypisanie czy przekazana liczba jest liczba Upartą.

1. int main () {
2.   int a;
3.   cout << "Podaj liczbe do sprawdzenia\n a = ";
4.   cin >> a;
5.   bool wynik = czyUparta(a);
6.   cout << "Liczba " << (wynik ? "" : "nie ") << "jest uparta";
7.   system("pause");
8.   return 0;
9. }

• Kod źródłowy Implementacja