Strona główna » Algorytmy » Teoria Liczb » Ciąg Aliquot
σ
 

Ciąg Aliquot

https://mattomatti.com/a0042

Ciąg

Ciag Aliqout to nietypowy ciąg, który chociaż nieskończony zeruje się już nawet po kilku wyrazach, a dla innego wyrazu początkowego ma cały czas tę samą wartość. Niektóre właściwości ciagu można wywnioskować na podstawie różnych liczb specjalnych.

Definicja

Dla ciągu Aliqout należy ustalić jego pierwszy wyraz a1. Następnie każdy kolejny wyraz to suma dzielników właściwych wyrazu poprzedniego an = σ(an - 1) dla n > 1.

Przykład

Przyjmijmy a1 = 9. Wtedy następny wyraz to a2 = σ(9) = 1 + 3 = 4, a3 = σ(4) = 1 + 2 = 3, a4 = σ(3) = 1 oraz a5 = σ(1) = 0. Suma dzielników właściwych z 0 i 1 to zawsze jest 0, więc jest to ciąg, który zaczyna się od 9, 4, 3, 1, 0, .. i dalej ma same zera. Jeśli przyuważyć się ciąg kończy się wyrazami o wartości 1 i 0 jeśli przed nimi będzie jakaś liczba Pierwsza.

Jednak problem pojawia się w przypadku, gdy mamy doczynienia z liczbami Doskonałymi. Wtedy każdy wyraz ciągu jest równy początkowemu. Jest to spowodowane faktem, że liczba Doskonała jest sumą swoich dzielników właściwych. Przykładowo dla a1 = 6, a2 = σ(9) = 1 + 2 + 3 = 6, a3 = 1 + 2 + 3 = 6 itd.

Podobne zachowanie można odkryć w przypadku natrafienia na liczby Zaprzyjaźnione. Wtedy ciąg zaczyna powtarzać w kółko dwie te same liczby w nieskończoność. Tutaj jako przykład można podać najmniejszą parę liczb Zaprzyjaźnionych 220 i 284. Przykładowo dla a1 = 220, a2 = σ(220) = 284, a3 = σ(284) = 220 itd. Oczywiście są też ciągi, których powtarzająca się w nieskończoność końcówka jest znacznie dłuższa.

Implementacja

Wypisywanie ciągu

Podczas implementowania należy pamiętać, że wypisywany ciąg może się okazać nieskończony i nie należy polegać na fakcie, że czasem od pewnego miejsca wyrazy się zerują. Chociaż nie jest to zbyt ekonomiczne dla komputera to trzeba zapamiętać wszystkie poprzednie wyrazy tak, aby można było sprawdzić czy ciąg nie zaczyna się powtarzać.

Poniżej została przedstawiona przykładowo implementacja. W celu uproszczenia zapamiętywania wyrazów ciągu wykorzystana została klasa vector. Funkcja ciagAliqout() przyjmuje tylko jeden argument n - pierwszy wyraz ciągu.

  1. void ciagAliquota(int n) {
  2.   int s = n;
  3.   vector<int> v;
  4.   do {
  5.     v.push_back(s);
  6.     cout << s << ", ";
  7.     s = sumaDzielnikow(s);
  8.   } while (find(v.begin(), v.end(), s) == v.end());
  9.   if (s == 0)
  10.     cout << "0, .., 0, ..";
  11.   if (s == n)
  12.     cout << ".., " << n;
  13. }

(2.) Przyjmij pierwszy wyraz za równy argumentowi n oraz (3.) zadeklaruj vector v. (4.) W pętli (5.) dopisz wartość s na koniec v, (6.) wypisz element i (7.) wylicz następny element. (8.) Warunkiem kontynuuowania pętli jest nie znalezienie nowej wartości s w wektorze v. Dodatkowo na koniec zostały dopisane warunki, które dopisują odpowiednie rzeczy, aby zapis wyglądał bardziej matematycznie.

Sumowanie dzielników

Do sumowania dzielników dowolnej liczby n służy funkcja sumaDzielnikow():

  1. int sumaDzielnikow(int n) {
  2.   int s = 0;
  3.   for (int i = 1; i <= n / 2; i++) {
  4.     if (n % i == 0) {
  5.       s += i;
  6.     }
  7.   }
  8.   return s;
  9. }

Podczas wyliczania sumy dzielników właściwych należy pamiętać, że σ(0) = σ(1) = 0, ponieważ 1 nie ma żadnych dzielników właściwych. (Dzielnik właściwy liczby n jest mniejszy od niej samej).

Testowanie funkcji

W celu przetestowania programu może skorzystać z poniższego fragmentu kodu:

  1. int main () {
  2.   int n;
  3.   cout << "Podaj pierwszy wyraz: ";
  4.   cin >> n;
  5.   ciagAliquota(n);
  6.   cout << endl;
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Zadanie 1

Największym problemem dotyczącym ciągu Aliqout jest wyszukiwanie czy dana wartość już nie pojawiła się, aby przerwać wypisywanie. Napisz wersję kodu, która będzie implementowała wyszukiwanie binarne, aby jak najszybciej wyliczyć ciąg.