Strona główna » Algorytmy » Teoria Liczb » Liczby Trimorficzne i wyższego rzędu
 

Liczby Trimorficzne i wyższego rzędu

https://mattomatti.com/a98

Definicje

Liczba Trimorficzna

Liczba Trimorficzna to taka liczba naturalna n, która podniesiona do sześcianu zawiera na końcu wartość n. Przykładowo taką liczbą jest 9, ponieważ 93 = 729. Innym przykładem jest liczba 25, ponieważ 253 = 15625.

Uogólnienie

Warto zauważyć, że liczby Trimorficzne należą do tej samej rodziny liczb co liczby Automorficzne. Sposób wykrywania jest identyczny, ale różnią się potęgą do której jest podnoszona liczba n. Na podstawie tych dwóch rodzajów liczb można utworzyć następujące uogólnienie:

Liczbą kmorifczną nazywamy liczbę naturalną n, która podniesiona do potęgi k zawiera na ostatnich cyfrach liczbę n.

Implementacja

Czy Trimorficzna?

Zdecydowanie najprostszą metodą na implementację sprawdzenia czy liczba jest automorficzna polega na obliczeniu potęgi 3 danej liczby a, a następnie sprawdzeniu p ostatnich pozycji sześcianu liczby czy wynoszą tyle co a, gdzie p to ilość cyfr liczby a.

Zadanie to realizuje poniższy kod:

  1. bool isTrimorphic(int a) {
  2.   int potega3 = pow(a, 3);
  3.   int potega_dl = pow(10, (int)(log10(a) + 1));
  4.   return (a == (potega3 % potega_dl));
  5. }

(2.) Wyliczenie potęgi. (3.) Wyliczenie liczby 10p, gdzie p to ilość cyfr. Najszybszą metodą wyliczenia długości cyfry jest wyliczenie jej logarytmu dziesiętnego, pobrania części całkowitej i zwiększenie wyniku o 1. (4.) Zwrócenie wyniku czy końcówka wyliczonego sześcianu jest równa liczbie a.

Drobna optymalizacja

Jak wiadomo sprzęt komputerowy potrafi przechowywać w zmiennych prostego typu tylko liczby z ograniczonego zakresu. W przypadku sześcianu wartości bardzo szybko rosną i już powyżej wartości 1290 może dojść do przekłamań w wyniku. (Dla zmiennych typu int). Jednym ze sposobów na zwiększenie tej wartości jest stworzenie własnej implementacji potęgowania. Należy tu skorzystać z faktu, że do ostatecznego warunku potrzebne jest jedynie p ostatnich cyfr wyliczanego sześcianu.

Z tego powodu po każdym mnożeniu będzie wyciągana reszta z dzielenia aktualnej wartości przez wartość 10p. Dzięki tej prostej operacji wartość graniczna dla której algorytm zwróci prawidłową wartość zwróci to 46340. (Wartość wyliczona dla typu int).

  1. bool isTrimorphic(int a) {
  2.   int potega_dl = pow(10, (int)(log10(a) + 1));
  3.   int potega3 = a;
  4.   for (int i = 1; i < 3; i++)
  5.     potega3 = (potega3 * a) % potega_dl;
  6.   return (a == (potega3 % potega_dl));
  7. }

Implementacja własnego potęgowania została dodana w linijkach (3. - 5.).

Czy kmorficzna?

Kod wyliczający zgodnie z definicją uogólnienia liczb morficznych jest bardzo podobny do napisanej wyżej implementacji:

  1. bool iskmorphic(int a, int k) {
  2.   int potega_dl = pow(10, (int)(log10(a) + 1));
  3.   int potegak = a;
  4.   for (int i = 0; i < k; i++)
  5.     potegak = (potegak * a) % potega_dl;
  6.   return (a == (potegak % potega_dl));
  7. }

Po pierwsze (1.) w definicji funkcji pojawia się obowiązek podania dodatkowego argumentu k. Ma to za zadanie określić rząd morficzności k. (2.) Wyliczenie liczby 10p nie zmienia się. W trakcie wyliczania potęgi (3. - 5.) należy pamiętać o (4.) poprawnej ilości pętli. (6.) Sprawdzanie czy liczba jest k morficzna pozostaje niezmienna.

Posiadając funkcję iskmorphic() można dopisać prostszą implementacją funkcji isTrimorphic():

  1. bool isTrimorphic(int a) {
  2.   return iskmorphic(a, 3);
  3. }

Testowanie funkcji

W celu wypisania wszystkich liczb kmorficznych z zakresu [1, 1000] wystarczy poniższa funkcja main():

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

Zadania

Zadanie 1

Napisz funkcję, która dla podanego zakresu [a, b] oraz zakresu [p, q] wypisze wszystkie ile jest w danym zakresie liczby pmorficznych, (p+1)morficznych, ..., qmroficznych. Pamiętaj o komunikatach dla użytkownika podczas wprowadzania danych.

Przykładowo dla zakresu [1, 100] i zakresu rzędów [2, 5] program powinien wypisać:

  1. 2-morficznych 7
  2. 3-morficznych 25
  3. 4-morficznych 7
  4. 5-morficznych 43