Strona główna » Algorytmy » Teoria Liczb » Liczby Wesołe
 

Liczby Wesołe

https://mattomatti.com/a72

Definicja

Do omówienia liczb Wesołych należy zdefiniować funkcję f(a), która dla zadanej liczby naturalnej a złożonej z n cyfr zwróci liczbę, która jest sumą kwadratów cyfr liczby a. Liczbą Wesołą nazywamy liczbę, która po wywołaniu funkcji f k razy będzie równa 1. Liczba nie jest Wesoła kiedy nie można uzyskać 1 w k krokach.

Przykłady

Najprostszym przykładem jest liczba 1, która f(1) = 12 = 1.

Kolejną liczbą Wesołą jest 7, ponieważ funkcję f możemy wywołać k razy. Wtedy f(7) = 72 = 49, a f(49) = 42 + 92 = 16 + 81 = 97. Kontynuując f(97) = 92 + 72 = 130, f(130) = 12 + 32 + 02 = 10. W ostatniej piątej iteracji f(10) = 12 + 02 = 1.

Analiza

Warto zauważyć, że wszystkie liczby wyznaczone pomiędzy przejściem od liczby a do 1 też są liczbami wesołymi. Korzystając z przemienności dodawania można stwierdzić, że dowolna permutacja cyfr liczby a po dołączeniu dowolnej ilości zer dalej będzie liczbą wesołą.

Liczbę 1 można otrzymać wtedy i tylko wtedy, gdy suma kwadratów cyfr wynosi 1 co pokrywa się z faktem, że liczba składa się z tylko jednej niezerowej cyfry 1. W każdym systemie liczbowym zmieniają się liczby, które można oznaczyć jako wesołe. Interesującym przypadkiem jest fakt, że w systemie dwójkowym wszystkie liczby naturalne są wesołe.

Jeśli liczba nie osiągnie 1 po k wywołaniach f na a oznacza to, że liczba jest nieszczęśliwa. Liczbę nieszczęśliwą można rozpoznać po fakcie, że po l krokach funkcja f zwróci wartość, która już wcześniej wystąpiła w trakcie przekształceń. Uwaga: w cyklu wyników f może, ale nie musi wystąpić początkowa liczba a.

Implementacja

Funkcja f

Pierwszą rzeczą do zaimplementowania w programie jest funkcja f, która w kodzie źródłowym może wystąpić pod taką samą nazwą:

  1. void f(int &a) {
  2.   int s = 0;
  3.   while(a > 0){
  4.     s += (a % 10) * (a % 10);
  5.     a /= 10;
  6.   }
  7.   a = s;
  8. }

(1.) Funkcja f przyjmuje jeden argument z bezpośrednim dostępem w pamięci, więc nie istnieje potrzeba, aby zwracać jakąkolwiek wartość. (2.) Deklaracja sumy kwadratów s. (3.) Dopóki istnieją niezerowe cyfry w liczbie a to: (4.) zwiększ s o kwadrat ostatniej cyfry aktualnej wartości a i (5.) usuń ostatnią cyfrę liczby a. (7.) Na koniec zapisz s na miejscu liczby a.

Czy wesoła?

(1.) Funkcja czyWesola() zwróci wartość logiczną czy podana liczba a jest liczbą wesołą:

  1. bool czyWesola(int a) {
  2.   vector <int> v;
  3.   while(a != 1){
  4.     v.push_back(a);
  5.     f(a);
  6.     for(int i = 0; i < v.size(); i++)
  7.       if(v[i] == a)
  8.         return false;
  9.   }
  10.   return true;
  11. }

(2.) Istnieje potrzeba zapisywania dotychczasowych wartości. Trudno oszacować dokładną ilość, dlatego najwygodniej skorzystać z zmiennej vector. (3.) Przekształcenie będą dokonywane dopóki a jest różne od 1: (4.) dopisanie wartości do wektora v, (5.) wywołania funkcji f z argumentem a i (6. - 7.) sprawdzanie czy nowa wartość nie występuje już na liście dotychczasowych wartości. (7.) Jeśli się znajduje to (8.) znaczy, że liczba nie jest wesoła. Jednak jeśli pętla zostanie przerwana, ponieważ a wyniesie 1 to (10.) należy zwrócić prawdę.

Testowanie funkcji

Poniższy program wypisuje wszystkie liczby wesołe z zakresu [1, 1000]:

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

Zadania

Zadanie 1

Wesołe liczby pierwsze to takie liczby naturalne, które są jednocześnie liczbami wesołymi i pierwszymi. Napisz program, który dla wprowadzonego przez użytkownika zakresu [a, b] wypisze wszystkie wesołe liczby pierwsze.