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

Liczby Giuga

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. static bool czyLiczbaGiuga(ulong n) {
  2.   ulong t = n, suma = 0, dzielnik = 1;
  3.   for (ulong i = 2; i <= Math.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. static void Main(string[] args) {
  2.   Console.Write("Z jakiego zakresu wypisać liczby Giuga?\n a = ");
  3.   ulong a = Convert.ToUInt64(Console.ReadLine());
  4.   Console.Write(" b = ");
  5.   ulong b = Convert.ToUInt64(Console.ReadLine());
  6.   Console.WriteLine("\nLiczby Giuga z zakresu [{0}, {1}]:", a, b);
  7.   for (; a <= b; a++)
  8.     if (czyLiczbaGiuga(a))
  9.       Console.WriteLine(a);
  10.   Console.ReadKey();
  11. }

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.