Teoria Sumy Kwadratów

Wstęp

Teoria Sumy Kwadratów pozwala stwierdzić kiedy liczbę całkowitą większą od 1 można zapisać jako sumę kwadratów dwóch liczb. Wykorzystuje ona do tego rozkład liczby na czynniki pierwsze. Poniższy artykuł przedstawio sposób implementacji algorytmu rozwiązującego zagadnienie.

Teorie

Teoria Fermata

Nieparzysta liczba pierwsza p może zostać wyrażona jako suma dwóch kwadratów wtedy i tylko wtedy, gdy p mod 4 = 1.

Uzupełnienie

Dowolna liczba całkowita większa od 1 może zostać zapisana jaok suma dwóch kwadratów wtedy i tylko wtedy, gdy w jej rozkładzie na czynniki pierwsze nie ma czynnika pierwszego p, który jest podniesiony do nie parzystej potęgi, a on sam spełnia warunek p mod 4 == 3.

Analiza

Teoria Fermata ogranicza się jedynie do liczb pierwszych, ale biorąc pod uwagę też uzupełnienie jesteśmy w stanie odpowiedzieć dla dowolnej liczby całkowitej n czy uda się ją zapisać w postaci n = a² + b². Przykładowo liczba 13 jest pierwsza i spełnia warunek 13 mod 4 == 1. Można ją zapisać jako: 13 = 3² + 2². Weźmy przykładowo liczbę 1234. Nie jest to liczba pierwsza, więc musimy odwołać się do uzupełnienia teorii. Pierwszy krok polega na rozkładzie na czynniki pierwsze czyli 1234 = 2·617. Obydwie liczby są pierwsze i 2 mod 4 = 2, a 617 mod 4 = 1, więc istnieje rozkład: 1234 = 3² + 35².

Implementacja

Szukanie rozkładu

W celu znalezienia rozkładu pewnej liczby sprawdzamy kolejne potęgi. Na ich podstawie obliczamy obydwa składniki i sprawdzamy czy suma ich kwadratów daje liczbę wejsciową. Oto przykładowa funkcja SzukajRozkladu():

1. pair<int, int> SzukajRozkladu(int n) {
2.   for (int i = 1; 2*i*i < n; i++) {
3.     int a = i * i;
4.     int b = n - a;
5.     int sqrt_b = round(sqrt(b));
6.     if (pow(sqrt_b, 2) == b) {
7.       return make_pair(i, sqrt_b);
8.     }
9.   }
10.   return make_pair(0, 0);
11. }

Poszukiwania ograniczamy do wartości, których kwadrat jest nie większy od liczby wejściowej. Do sprawdzenia czy drugi obliczony składnik ma pierwiastek należy wpierw go obliczyć, zaokrąglić do liczby całkowitej, a następnie podnieść ponownie do kwadratu. Należy tutaj pamiętać, że dużą rolę odgrywa przybliżona postać wyniku operacji pierwiastka.

Implementacja Toerii

Do sprawdzenia warunków teorii jak również jej uzupełniania potrzebna jest metoda do sprawdzenia czy dana liczba jest pierwsza. Następnie można napisać poniższą funkcję, która zwraca informację czy według teorii rozkład istnieje:

1. bool CzyIstniejeRozklad(int n) {
2.   if (CzyPierwsza(n) && n % 4 == 1) {
3.     return true;
4.   }
5.   int dzielnik = n + 1;
6.   int licznik = 0;
7.   while (dzielnik > 2) {
8.     dzielnik--;
9.     if (!CzyPierwsza(dzielnik)) {
10.       continue;
11.     }
12.     licznik = 0;
13.     while (n % dzielnik == 0) {
14.       n /= dzielnik;
15.       licznik++;
16.     }
17.     if (licznik % 2 == 1 && dzielnik % 4 == 3) {
18.       return false;
19.     }
20.   }
21.   return true;
22. }

Powyższa implementacja wpierw sprawdza warunek dla liczb pierwszych, a następnie dotyczący rozkładu na czynniki pierwsze. Nie jest ona optymalna, ponieważ wpierw należałoby wyznaczyć tablicę liczb pierwszych, a nie przechodzić po kolejnych wartościach i sprawdzać czy są one pierwsze. Powyższy kod ma jedynie zastosowanie demonstracyjne.

Testowanie funkcji

Do przetestowania kodu można uruchomić poniższy fragment kodu. Wypisze on dla wpisanej liczby jaki ma rozkład lub, że nie ma oraz co orzeka toeria dla danej liczby.

1. int main() {
2.   int n;
3.   cout << "Podaj liczbe\n n = ";
4.   cin >> n;
5.   pair<int, int> wynik = SzukajRozkladu(n);
6.   bool teoria = CzyIstniejeRozklad(n);
7.   if (wynik.first == 0) {
8.     cout << "Rozklad nie istnieje";
9.   } else {
10.     cout << n << " = " << wynik.first;
11.     cout << "^2 + " << wynik.second << "^2";
12.   }
13.   cout << "\nTeoria: " << (teoria ? "jest rozklad" : "nie ma");
14.   system("pause");
15.   return 0;
16. }

• Kod źródłowy Implementacja