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

Liczby Smitha

https://mattomatti.com/a67

Definicja

Liczby Smitha są podzbiorem liczb naturalnych. Suma cyfr liczby a Smitha wynosi tyle samo co suma cyfr liczb rozkładu na czynniki pierwsze liczby a. Do liczb Smitha nie należą liczby pierwsze chociaż spełniają poprzedni warunek.

Przykład

Najmniejszą liczbą Smitha jest 4. Suma cyfr tej liczby wynosi 4. Jej rozkład na czynniki pierwsze to {2, 2}, a ich suma daje 4. Cztery nie jest też liczbą pierwszą, ponieważ nie dzieli się tylko przez samą siebie - oba warunki zostały spełnione. Innym przykładem liczby Smitha jest 319. Suma cyfr liczby wynosi 13 = 3 + 1 + 9. Rozkład liczby na czynniki pierwsze to {11, 29}. Sumując cyfry wszystkich liczb z rozkładu otrzymuje sie 13 = (1 + 1) + (2 + 9).

Pierwsze 10 liczb Smitha to: 4, 22, 27, 58, 85, 94, 121, 166, 202, 265, ...

Implementacja

Sumowanie cyfr

Do sprawdzenia czy wprowadzona liczba jest liczbą Smitha będzie potrzebna funkcja sumOfDigit(), która będzie sumować cyfry zadanej liczby:

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

(1.) Liczba przyjmuje argument a - liczbę, której cyfry mają być zsumowane. Wynikiem będzie suma cyfr liczby a. (2.) Zmienna s będzie przechowywać wyliczoną sumę cyfr. (3.) Dopóki liczba ma jakąś niezerową cyfrę to: (4.) ostatnia cyfrę należy dodać do s i (5.) usunąć ostatnią cyfrę z liczby. (7.) Po zakończeniu pętli wynikiem jest wartość zmiennej s.

Czy liczba Smitha?

Napisanie funkcji sprawdzającej czy dana liczba jest liczbą Smitha jest proste dzięki poprzednio napisanej funkcji. Pozostaje jednak kwestia czy znaleziona liczba nie jest liczbą pierwszą. Można wyeliminować potrzebę sprawdzania tego nie dopuszczając do sprawdzenia czy liczbę a dzieli a. Oczywiście byłoby to zawsze spełnione, ale bez sprawdzenia tego suma rozkładu na czynniki pierwsze wyniesie 0. Suma cyfr liczby pierwszej będzie zawsze różna od 0.

  1. bool isSmithNumber(int a){
  2.   int s = 0, b = a;
  3.   for(int i = 2; i <= b/2; i++){
  4.     while (a % i == 0){
  5.       s += sumOfDigit(i);
  6.       a /= i;
  7.     }
  8.   }
  9.   return (s == sumOfDigit(b));
  10. }

(1.) Funkcja isSmithNumber() przyjmuje jeden argument a - liczbę do sprawdzenia czy jest liczbą Smitha. Wynikiem będzie wartość logiczna czy tak jest. (2.) Na początku funkcji deklarowane są dwie dodatkowe zmienne: s - suma cyfr dzielników a oraz b - kopia wartości a. (3.) Wszystkie możliwe dzielniki zawierają się w zakresie [2, n/2]. Sprawdzanie podzielności należy zacząć od 2, ponieważ każdy znaleziony dzielnik od razu usunie wszystkie wielokrotności dzielnika co za tym idzie liczba zostanie rozłożona tylko na liczby pierwsze. (4.) Dopóki w i-tej i dzieli a to należy (5.) s zwiększyć o sumę cyfr i i (6.) podzielić a przez i. (9.) Wynikiem działania funkcji jest porównanie sumy cyfr dzielników oraz sumy cyfr liczby a. Tu użyta została kopia zapisana w zmiennej b.

Testowanie funkcji

W celu wypisania liczb Smitha z zakresu [1, 1000] można posłużyć się poniższym kodem:

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

Bratnie liczby Smitha

W przypadku, gdy liczby Smitha są kolejnymi liczbami naturalnymi to mówimy o bratnich liczbach Smitha. Pierwszą taką parą jest para liczb 728 i 729. Liczby Smitha mogą też występować trójkami: 73615, 73616, 73617. Niewiadomo ile jest dokładnie takich przykładów w zbiorze liczb Smitha.

Zadania

Zadanie 1

Napisz program, który znajdzie liczby, które można określić mianem braci Smitha. Każda grupa braci powinna być wypisana w oddzielnej linijce. Zakres sprawdzania [a, b] ma być wprowadzony przez użytkownika.

Zadanie 2

Napisz program, który wczyta liczbę od użytkownika i stwierdzi czy liczba ma Smithowskich braci.