Strona główna » Algorytmy » Teoria Liczb » Para Ruth-Aaron
 

Para Ruth-Aaron

https://mattomatti.com/a0051

Definicja

Para Ruth-Aaron jest to para dwóch kolejnych liczb naturalnych (n, n + 1), który suma liczb rozkładu na czynniki pierwsze jest równy. Wyróżnia się dwie kategorie takich liczb. Według pierwszej w sumie rozkładu na czynniki pierwsze należy zsumować wszystkie czynniki, a według drugiej kategorii identyczne czynniki powinny być liczone jako jeden.

Przykład

Weźmy przykładowo liczbę 125 = 5·5·5. Jest ona w parze z liczbą 126 = 2·3·3·7, ale tylko w myśl kategorii pierwszej, ponieważ 5 + 5 + 5 = 2 + 3 + 3 + 7. W drugiej kategorii z liczby 125 liczyłby się z rozkładu tylko jeden czynnik 5, a z liczby 126 tylko 2, 3 i 7. Wtedy równość 5 ≠ 2 + 3 + 7.

Istnieją jednak przypadki, że para należy do pierwszej i drugiej kategorii. Są to wszystkie pary, które w swoim rozkładzie mają tylko pojedyncze czynniki pierwsze. Jednym z przykładów jest liczba 77 = 7·11 oraz 78 = 2·3·13. Jak można zauważyć w tym przypadku usunięcie powtarzających się czynników z rozkładu nie zmienia ich sumy, a warunek jest spełniony 7 + 11 = 2 + 3 + 13.

Ciągi

Ciąg liczb pierwszej kategorii (wszystkie czynniki): 5, 24, 49, 77, 104, 153, 369, 492, 714, 1682, ..
Ciąg liczb drugiej kategorii (tylko unikalne czynniki): 5, 8, 15, 77, 125, 714, 948, ..

Implementacja

Suma rozkładu

Podczas szukania par Ruth-Aarona kluczowym elementem jest znalezienie sumy rozkładu liczby na czynniki pierwsze. Warto w takim razie napisać funkcję sumujRozkladWszystkie(), która dla przekazanej wartości a zwróci sumę jej dzielników. W tym przypadku zajmujemy się kategorią pierwszą, więc sumujemy wszystkie.

C++
C#
  1. static int sumujRozkladWszystkie(int a) {
  2.   int dzielnik = 2, suma = 0;
  3.   while (a > 1) {
  4.     while (a % dzielnik == 0) {
  5.       suma += dzielnik;
  6.       a /= dzielnik;
  7.     }
  8.     dzielnik++;
  9.   }
  10.   return suma;
  11. }

Zastosowana została tutaj sztuczka, która polega na tym, że zaczynamy dzielić przez najmniejszą liczbę pierwszą. Usuwając wszystkie jej wystąpienia automatycznie usuwamy jej wielokrotności nie będące liczbami pierwszymi w rozkładzie. Proces jest kontynuowany, aż do uzyskania wartości 1. Dla wartości jeden suma jej rozkładu na czynniki pierwsze wynosi 0, więc nie powoduje to niekonieczności korekcji wyniku.

Czy para?

Sprawdzenie teraz czy dana para jest parą Ruth-Aarona staje się proste. Funkcja sprawdzająca będzie przyjmować tylko jeden argument n, a sprawdzi parę (n, n + 1). Można tak zrobić, ponieważ zgodnie z definicją parę tworzą dwie kolejne liczby naturalne. Funkcja, aby zwrócić wynik musi porównać sumy rozkładu liczby n oraz n + 1. Będzie to para tylko wtedy, gdy sumy będą równe.

C++
C#
  1. static bool czyParaRuthAaronWszystkie(int n) {
  2.   int suma1 = sumujRozkladWszystkie(n);
  3.   int suma2 = sumujRozkladWszystkie(n + 1);
  4.   return (suma1 == suma2);
  5. }

Testowanie funkcji

Zazwyczaj w celu wyszukania pierwszych liczb danego typu wystarczy pętla i funkcja, która powie czy daną liczbę należy wypisać. Tutaj taka pętla może zostać zoptymalizowana, ponieważ przechodząc po kolejnych parach .., (i, i + 1), (i + 1, i + 2), (i + 2, i + 3), .. rozkład każdej liczby jest liczony dwa razy. Z tego powodu warto napisać własną funkcję wypisującą kolejne pary z określonego zakresu tak, aby wykonane zostało jak najmniej obliczeń.

C++
C#
  1. static void wypiszPary(int n) {
  2.   int suma1 = sumujRozkladWszystkie(0);
  3.   for (int i = 1; i <= n; i++) {
  4.     int suma2 = sumujRozkladWszystkie(i);
  5.     if (suma1 == suma2)
  6.       Console.Write("{0} ", i);
  7.     suma1 = suma2;
  8.   }
  9. }

Funkcja wypiszPary() przyjmuje tylko jeden argument n, który określa zakres [1, n] z którego mają zostać wypisane pary Ruth-Aarona. Przykładowo, aby wypisać pary z zakresu [1, 100000] można utworzyć taką funkcję główną:

C++
C#
  1. static void Main(string[] args) {
  2.   wypiszPary(100000);
  3.   Console.ReadKey();
  4. }

Zadania

Zadanie 1

Napisz podobny zestaw funkcji przedstawiony powyżej dla par Ruth-Aarona drugiej kategorii. Funkcja sumujRozkladUnikalne() ma przyjmować tylko jeden argument a, która zsumuje tylko unikalne czynniki z rozkładu liczby. Następna funkcja czyParaTuthAaronUnikalne() ma przyjmować argument n i sprawdzić czy para (n, n + 1) spełnia warunki z definicji. Ostatnią funkcją powinno być wypiszPary(), która dala przekazanej wartości n zwróci pary Ruth-Aarona drugiej kategorii z zakresu [1, n]. Przetestuj działanie programu.

Zadanie 2

Napisz funkcję wypiszPary2(), która wypisze z zakresu [1, n] wszystkie pary, które należą zarówno do pierwszej jak i do drugiej kategorii.