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:

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.

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. }

• Kod źródłowy Implementacja

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.

• Kod źródłowy Zadanie 1