Strona główna » Algorytmy » Teoria Liczb » Liczby Giuga
 

Liczby Giuga

https://mattomatti.com/a0074

Definicja

Liczba Giuga to taka liczba, której suma odwrotności dzielników pierwszych pomniejszona o iloczyn odwrotności dzielników wynosi 1. Przedstawiony opis można przedstawić w postaci wzoru:

Liczby Giuga została nazwane po matematyku Giuseppe Giuga i mają one związek z jego przypuszczeniami dotyczącymi pierwszości liczb.

Przykład

Najmniejszą liczbą Giuga jest 30. Jej dzielnikami pierwszymi są 2, 3, 5. Wtedy ze wzoru otrzymujemy:

Ciąg

Pierwsze dziesięć wyrazów Giuga to: 30, 858, 1722, 66198, 2214408306, 24423128562, 432749205173838, 14737133470010574, 550843391309130318, 244197000982499715087866346, ..

Implementacja

Znajdowanie liczb na podstawie wzoru

Zauważmy, że każdy sumowany ułamek możemy zamienić na ułamek podwójny, gdzie mianownik to liczba n, a licznik to drugi ułamek liczba n podzielona dzielnik p. Wtedy możliwe jest zsumowanie liczników. Jeśli obie strony zostaną pomnożone przez p to otrzymujemy, że iloczyn dzielników p musi się równać sumie tych dzielników pomniejszone o 1. Dodatkowo należy pamiętać, że wtedy iloczyn dzielników musi wynosić tyle co sama liczba, ponieważ inaczej nie można byłoby odjąć 1, a pewien ułamek, który jest mniejszy o jeden. Warunki te muszą zostać sprawdzone oddzielnie!

Funkcja czyLiczbaGiuga() sprawdza czy przekazana liczba n na należy do zbioru liczb Giuga. Oto kod:

C++
C#
  1. bool czyLiczbaGiuga(unsigned long n) {
  2.   unsigned long t = n, suma = 0, dzielnik = 1;
  3.   for (unsigned long i = 2; i <= sqrt(n); i++) {
  4.     if (t % i == 0) {
  5.       suma += n / i;
  6.       dzielnik *= i;
  7.       while (t % i == 0) {
  8.         t /= i;
  9.       }
  10.     }
  11.   }
  12.   return suma - 1 == dzielnik && dzielnik == n;
  13. }

(2.) Deklaracja trzech zmiennych: t - kopia zmiennej n, suma - zmienna potrzebna do sumowania kolejnych dzielników oraz dzielnik - iloczyn dzielników. Następnie (3.) dla każdego możliwego dzielnika: (4.) jeśli aktualna wartość jest dzielnikiem to: (5.) dodaj do sumy i (6.) pomnóż przez aktualny iloczyn dzielników. Potem (7. - 9.) dziel przez i tak długo jak to możliwe, aby kolejne i też była liczbą pierwszą. Na koniec (13.) zwróć wynik porównania obu warunków.

Testowanie funkcji

Poniższy kod pozwala przetestować działanie napisanej funkcji. Od użytkownika wczytywany jest pewien zakres [a, b], a następnie wypisywane są wszystkie liczby Giuga w zakresie.

C++
C#
  1. int main () {
  2.   unsigned long a, b;
  3.   cout << "Z jakiego zakresu wypisac liczby Giuga?\n a = ";
  4.   cin >> a;
  5.   cout << " b = ";
  6.   cin >> b;
  7.   cout << "\nLiczby Giuga z zakresu";
  8.   cout << "[" << a << ", " << b << "]:" << endl;
  9.   for (; a <= b; a++)
  10.     if (czyLiczbaGiuga(a))
  11.       cout << a << endl;
  12.   system("pause");
  13.   return 0;
  14. }

Zadania

Teoria do Zadanie 1

Istnieje jeszcze drugi sposób sprawdzenia czy liczba należy do liczb Giuga. Dla każdego dzielnika pierwszego, który dzieli sprawdzaną liczbą należy sprawdzić warunek:

Ponadto należy upewnić się, że liczba ma jakikolwiek dzielnik!

Przykład

Weźmy jeszcze raz jako przykład liczbę 30. Wtedy kolejno otrzymujemy, że 2 jest dzielnikiem 14, 3 jest dzielnikiem 9, a 5 jest dzielnikiem 5. Z tego wynika, że liczba 31 jest liczbą Giuga.

Zadanie 1

Używajac wzoru podanego w teorii powyżej napisz program, który będzie sprawdzał czy liczba n jest liczbą Giuga. Przetestuj działanie programu.