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

Liczby Egipskie

https://mattomatti.com/a90

Definicja

Liczby Egipskie to takie liczby naturalne, którą można rozłożyć na sumę n liczb. Ponadto suma odwrotności każdej liczby z sumy muszą dać 1. Podczas rozkładu na sumę nie wolno używać liczby 1.

Przykład

Prostym przykładem jest liczba 4, którą można zapisać jako sumę 2 + 2 = 4. Drugi krok polega na sprawdzeniu, że . Liczba 16 też jest liczbą Egipską, ponieważ można ją rozłożyć na sumą 4 + 4 + 4 + 4 = 16, a na podstawie można zapisać, że . Przykładem liczby będącej Egipską, ale nie potęgą 2 to 17: 17 = 6 + 4 + 4 + 3, a to z kolei .

Ciąg

Liczby Egipskie można ustawić w ciąg, którego początkowe wyrazy to: 4, 9, 10, 11, 16, 17, 18, 20, 22, ...

Implementacja

Spostrzeżenia

Szukanie rozkładu niektórych liczb można porównać do szukania igły w stogu siana. Możliwych rozkładów może być bardzo dużo, ponieważ są różnej długości. Długość możliwego rozkładu można ograniczyć przez fakt, że nie można wykorzystać w rozkładzie 1. Innymi słowy najmniejszy rozkład o długości n będzie składał się z samych 2 czyli najdłuższy rozkład będzie miał długość połowy sprawdzanej liczby. Idąc tym tokiem rozumowania można wykluczyć ze sprawdzania rozkłady o długości 1, ponieważ spełniłoby tylko a = 1. Ponadto warto ograniczyć sprawdzanie wszystkich możliwych rozkładów, ponieważ bardzo często ten sam rozkład na dwie liczby [a, b] można też znaleźć jako [b, a]. Uruchomienie programu bez takiej optymalizacji może skutkować 15 razy dłuższym wykonywaniem dla zaledwie pierwszy 100 liczb naturalnych.

Kolejnym bardzo ważnym krokiem jest napisanie algorytmu tak, aby sumę odwrotności składników sumy liczył jako ułamki, a nie jak byłoby wygodniej jako liczby rzeczywiste. Wynik musi być tutaj bardzo precyzyjny i jakikolwiek błąd obliczeń mógłby spowodować niewłaściwe zaklasyfikowanie liczby. Oczywiście są takie ułamki jak , które wywołają się bez najmniejszych problemów, ale problematyczne może okazać się dodanie ułamka .

Wyszukiwanie długości rozkładu

Do wyszukiwania długości posłuży funkcja czyEgipska():

  1. bool czyEgipska(int a) {
  2.   for (int i = 0; i < a / 2; i++) {
  3.     if (szukajRozkladu_n(a, i + 2))
  4.       return true;
  5.   }
  6.   return false;
  7. }

(1.) Dla podanej liczby a zwróć wartość logiczną czy liczba a jest liczbą Egipską. (2.) Rozpocznij szukanie długości rozkładu ograniczając z góry przez połowę liczby a. (3.) Dla każdej długości rozkładu wywołaj funkcję szukajRozkladu_n(), która będzie szukać rozkładu liczby a. Do funkcji tej należy podać faktyczną długość rozkładu tj. dodać 2. (4.) Tylko pod warunkiem, że zwrócona zostanie prawda to zwróć prawdę. Jeśli (6.) jednak pomimo przeszukania wszystkich długości rozkładów żaden nie spełnia wymagań to zwróć fałsz.

Szukanie rozkładu

W celu ograniczenie sprawdzanych przypadków zakładamy, że każda kolejna liczba w rozkładzie jest mniejsza lub równa poprzedniej.

  1. bool szukajRozkladu_n(int a, int n = 2) {
  2.   int* data = new int[n];
  3.   bool wynik = szukajRozkladu_pom(a, a - 2 * (n - 1), data, 0, n);
  4.   delete[] data;
  5.   return wynik;
  6. }

(1.) Funkcja szukajRozkladu_n() przyjmuje dwa argumenty a - liczba, której rozkład jest poszukiwany oraz n - jakiej długości ma być rozkład. (2.) Zaalokuj pamięć pod tablicę, aby można było zapisać rozkład. (3.) Wywołaj funkcję szukajRozkladu_pom(), która wyszuka rozkładu. Ograniczeniem dla pierwszej liczby w rozkładzie jest wartość a pomniejszona przez n - 1 wartości 2, ponieważ w rozkładzie każdy składnik przyjmuje najmniej właśnie wartość 2. (5.) Przed zwróceniem wartości wynik (4.) usuń z pamięci utworzoną listę data.

Funkcja szukajRozkladu_pom() przyjmuje następujące argumenty: a - pozostała wartość pierwotnej liczby a do dystrybucji, ogr - górne ograniczenie podczas poszukiwania kolejnego składnika sumy tj. [2, ogr], data - tablica gdzie zapisywany jest rozkład liczby, k - która liczba w rozkładzie jest aktualnie szukana oraz n - jak długi ma być rozkład.

  1. bool szukajRozkladu_pom(int a, int ogr, int* data, int k, int n) {
  2.   if (a < 2)
  3.     return false;
  4.   if (k + 1 == n) {
  5.     data[k] = a;
  6.     long long licznik = 1, mianownik = data[0], temp = 0;
  7.     for (int i = 1; i < n; i++) {
  8.       temp = licznik * data[i] + mianownik;
  9.       mianownik *= data[i];
  10.       licznik = temp;
  11.       temp = nwd(licznik, mianownik);
  12.       licznik /= temp;
  13.       mianownik /= temp;
  14.     }
  15.     return (licznik == mianownik);
  16.   } else {
  17.     for (int i = 2; i <= ogr; i++) {
  18.       data[k] = i;
  19.       if (szukajRozkladu_pom(a - data[k], data[k], data, k + 1, n))
  20.         return true;
  21.     }
  22.   }
  23.   return false;
  24. }

(2. - 3.) Na początek warto sprawdzić czy a < 2. Jeśli tak jest to nie ma jak dokonać dalszego rozkładu, więc można zwrócić od razu fałsz. (4.) Jeśli rozkład jest kompletny tj. zostało już zapisanych n - 1 składników to (5.) liczba a jest n-tym składnikiem. Następnie (6. - 15.) zsumuj wszystkie ułamki i (16.) zwróć porównanie licznika z mianownikiem.

Jednak jeśli lista ma mniej niż n - 1 składników to (18. - 22.) należy wyszukać kolejny składnik z zakresu [2, ogr]. W trakcie rekurencyjnego wywoływania należy pamiętać, że (20.) wartość a należy zmniejszyć o aktualnie dopisany składnik, ograniczeniem ogr będzie dopisany w tej iteracji składnik. Zwiększona musi być jeszcze zmienna k, ponieważ k-ty składnik właśnie został dopisany.

Testowanie funkcji

W celu wypisania liczb Egipskich z zakresu [2, 100] wystarczy poniższa funkcja main():

  1. int main () {
  2.   for (int i = 2; i < 100; i++) {
  3.     if (czyEgipska(i))
  4.       cout << i << ", ";
  5.   }
  6.   system("pause");
  7.   return 0;
  8. }

Liczby ściśle Egipskie

Liczby ściśle Egipskie to takie liczby w których poprawnym rozkładzie na sumę według definicji liczb Egipskich nie występują dwie takie same liczby.

Przykład

Liczbą ściśle Egipską nie jest liczba 4, ponieważ suma to 2 + 2 = 4. Przykładem liczby ściśle Egipskiej jest 11, ponieważ 11 = 6 + 3 + 2, a rozkład ten spełnia warunek .

Zadania

Zadanie 1

Napisz program, który będzie szukał liczb ściśle Egipskich w zakresie [a, b] podanym przez użytkownika.

Przykładowo dla danych 10 i 20 program wypisze na ekran:

  1. 11, 24, 30