Strona główna » Algorytmy » Artykuły » Słaba hipoteza Goldbacha
 

Słaba hipoteza Goldbacha

https://mattomatti.com/a88

Przypuszczenie

Słaba hipoteza Goldbacha to przypuszczenie w teorii liczb, które mówi, że każda liczba naturalna nieparzysta i większa od 7 jest sumą trzech nieparzystych liczb pierwszych (niekoniecznie różnych).

Przykład

Przykładowo liczbę 9 można zapisać jako sumę 5, 3 oraz 1. Innym przykładem jest liczba 23, którą można zapisać jako sumę 11 + 7 + 5.

Zadanie

Zadanie polega na napisaniu programu, który dla wszystkich liczb nieparzystych z podanego przedziału [a, b]. Po znalezieniu odpowiedniej trójki liczb pierwszych program powinien wypisać sumę na ekran. Przykładowo dla przedziału [9, 13] program powinien wypisać:

  1. 9 = 5 + 3 + 1
  2. 11 = 7 +3 + 1
  3. 13 = 7 + 5 + 1

Spostrzeżenia

W celu ograniczenia wykonywanych obliczeń warto przyjąć, że każda kolejna znaleziona liczba pierwsza jest większa lub równa poprzedniej znalezionej.

Czy liczba pierwsza

Poniższy kod pozwala sprawdzić czy przekazana liczba a jest liczbą pierwszą. Jego wyjaśnienie można znaleźć w tym artykule.

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

Wypisywanie rozkładu

Poniższy kod dla podanej liczby a szuka trzech liczb pierwszych, które w sumie dają a. W przypadku nie znalezienia lub w przypadku niespełnienia warunków przypuszczenia funkcja zwróci fałsz. W przeciwnym wypadku prawdę.

  1. bool goldbachRozklad(int a) {
  2.   if (a <= 7 || a % 2 == 0)
  3.     return false;
  4.   for (int j = 2; j + 4 < a; j++) {
  5.     if (czyPierwsza(j)) {
  6.       for (int i = j; i <= a - j - i; i++) {
  7.         if (czyPierwsza(i) && czyPierwsza(a - j - i)) {
  8.           cout << a << " = " << j << " + " << i;
  9.           cout << " + " << (a - j - i) << endl;
  10.           return true;
  11.         }
  12.       }
  13.     }
  14.   }
  15.   return false;
  16. }

(2.) Jeśli nie są spełnione warunki dotyczące liczby a to (3.) wykonywanie funkcji zostanie przerwane. W przeciwnym wypadku (4.) można przejść do szukania trójki liczb pierwszych. Pierwsza liczba w sumie jest sprawdzana dla każdej liczby z przedziału [2, a - 4), ponieważ 4 to najmniejsza suma pozostałych dwóch liczb pierwszych. (5.) Pod warunkiem, że przyjęta pierwsza liczba j to (6.) należy poszukiwania drugiej liczby pierwsze z przedziału [j, a - j - i], ponieważ każda następna liczba ma być większa lub równa.

(7.) Trójka zostanie znaleziona jeśli liczbą pierwszą jest wyznaczona liczba i oraz liczba a - j - i. Wtedy można (8. - 9.) wypisać rozkład i (10.) zwrócić, że rozkład został znaleziony.

Rozkłady z przedziału

Do wypisywania rozkładu liczb nieparzystych z przedziału [zakrL, zakrP] można wykorzystać funkcję czySlabyGoldbachRozklady().

  1. void czySlabyGoldbachRozklady(int zakrL, int zakrP) {
  2.   if (zakrL % 2 == 0)
  3.     zakrL++;
  4.   for (; zakrL <= zakrP; zakrL += 2)
  5.     goldbachRozklad(zakrL);
  6. }

Testowanie funkcji

Przykładowe wywołanie funkcji, aby wypisać rozkłady z przedziału [9, 13] wygląda następująco:

  1. int main() {
  2.   czySlabyGoldbachRozklady(9, 13);
  3.   system("pause");
  4.   return 0;
  5. }

Zadania

Zadanie 1

Napis program do wyszukiwania rozkładu liczby Goldbacha, który wypisze wszystkie możliwe rozkłady danej liczby nieparzystej. Każda wypisana trójka powinna być unikalna, a nie permutacją jednej z wcześniej wymienionych.

Przykładowo dla liczby 13 program powinien wypisać

  1. 13 = 3 + 3 + 7 = 3 + 5 + 5