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

Liczby Automorficzne

https://mattomatti.com/a52

Wstęp

Liczba automorficzna to taka liczba naturalna, która podniesiona do kwadratu zawiera w końcówce samą siebie. Najprostszym przykładem jest liczba 1, ponieważ 12. Zdecydowanie lepszym przykładem jest liczba 5: 52 = 25. W liczbie 25 na końcu występuje 5. Bardziej skomplikowanym przykładem jest liczba 376: 3762 = 141376. Jak widać liczba 141376 zawiera na końcu 376.

Przykłady

Liczby automorficzne, pomijając 0 oraz 1 mają na końcu liczbę 5 i 6. Jako dowód możemy zastanowić się, które cyfry podniesione do kwadratu zawierają siebie w jedności. Otóż spełniają to tylko 0, 1, 5 oraz 6. Jednak z tej grupy tylko 5 i 6 są prawidłowe dla nieskończonej liczby przypadków.

Ciąg liczb automorficznych wygląda następująco: 0, 1, 5, 6, 25, 76, 376, 625, 9376, 90625, 109376, 890625, ..

Implementacja

Czy automorficzna?

Czy dana liczba a jest automorficzna możemy sprawdzić na kilka sposobów.

Metoda 1

Najprostszą metodą sprawdzenia czy liczba jest automorficzna jest skorzystanie ze wzoru a = a2 mod mk, gdzie a - dana liczba, m - podstawa liczby a oraz k - długość liczby a. Jest to (nieczysto) matematyczny zapis warunku podanego w definicji.

  1. bool czyAutomorficzna(long a){
  2.   int dl = 10;
  3.   long temp = a;
  4.   while (temp > 9){
  5.     dl *= 10;
  6.     temp /= 10;
  7.   }
  8.   return ((a * a) % dl == a);
  9. }

(1.) Funkcja czyAutomorficzna() przyjmuje argument a - liczba do sprawdzenia i zwraca wartość logiczną, która określa czy liczba jest automorficzna. (2.) Przyjmujemy, że podstawą liczby a jest 10. (3.) Tworzymy kopię liczby a. (4. - 7.) Wyliczamy 10k. (8.) Jako wynik zwracamy wartość warunku podanego w definicji.

Metoda 2

Tym razem pominiemy wyliczanie długości danej liczby a. Tym razem podniesiemy ja do kwadratu i porównamy ostatnie cyfry a2 oraz a.

  1. bool czyAutomorficzna(long a){
  2.   long a2 = a * a;
  3.   while(a > 0){
  4.     if(a % 10 != a2 % 10)
  5.       return false;
  6.     a /= 10;
  7.     a2 /= 10;
  8.   }
  9.   return true;
  10. }

(2.) Wyliczamy kwadrat liczby a. (3.) Dopóki nie sprawdzimy wszystkich cyfr a: (4.) sprawdzamy czy ostatnie cyfry są różne - jeśli tak to (5.) zwracamy, że liczba nie jest automorficzna. (6., 7.) Usuwamy ostatnią cyfrę z a i a2. Jeśli nie zwrócimy, ani razu fałszu, a wyjdziemy z pętli while oznacza to, że (9.) zwracamy prawdę.

Zdecydowaną zaletą drugiego rodzaju funkcji jest brak potrzeby wyliczania długości liczby. Jednak z punktu widzenia złożoności oba algorytmy działają w czasie Θ(k), ale pierwsza implementacja wykonuje mniej operacji arytmetycznych.

Testowanie programu

Funkcję można przetestować przy pomocy poniższej funkcji main():

  1. int main () {
  2.   long a;
  3.   cin >> a;
  4.   cout << (czyAutomorficzna(a) ? "TAK" : "NIE") << endl;
  5.   system("pause");
  6.   return 0;
  7. }

Zadania

Zadanie 1

Napisz funkcję, która na początku określi czy liczba ma szansę być liczbą automorficzną. Wskazówka: cechy ostatnich cyfr liczby automorficznej