Pierwiastek cyfrowy (ang. digital root) – funkcja przypisująca liczbie naturalnej jednocyfrową wartość otrzymaną poprzez iteracyjne sumowanie jej cyfr. Wzór funkcji można przedstawić jako: .
Definicja Pierwiastek cyfrowy liczby naturalnej otrzymuje się, sumując wszystkie cyfry liczby, a następnie powtarzając tę operację dla uzyskanego wyniku aż do momentu otrzymania liczby jednocyfrowej.
Przykład:
Zatem pierwiastek cyfrowy liczby wynosi .
Uproszczenie Pierwiastek cyfrowy liczby jest równoważny jej reszcie z dzielenia przez (z wyjątkiem przypadku, gdy liczba jest podzielna przez – wtedy wynik wynosi zamiast ). Dodatkowo przyjmuje się, że . Można go obliczyć za pomocą wzoru dla . Dowód Niech liczba naturalna ma rozwinięcie dziesiętne , gdzie są jej cyframi.
Ponieważ , zachodzi także dla każdego . Stąd .
Oznacza to, że liczba i suma jej cyfr mają tę samą resztę z dzielenia przez . Powtarzając operację sumowania cyfr, nie zmieniamy tej reszty, aż do uzyskania liczby jednocyfrowej.
Każdej klasie reszt modulo odpowiada dokładnie jedna liczba jednocyfrowa z zakresu –, przy czym reszcie 0 odpowiada liczba . Zatem: jeśli , to , jeśli i , to .
W konsekwencji, dla : .
Inne systemy liczbowe Pojęcie pierwiastka cyfrowego można uogólnić na dowolny system liczbowy o podstawie . Dla liczby naturalnej zapisanej w systemie o podstawie : , gdzie , pierwiastek cyfrowy definiuje się jako wynik iteracyjnego sumowania cyfr aż do uzyskania jednej cyfry w tym systemie.
Zachodzi: , a więc dla każdego , skąd: .
W konsekwencji pierwiastek cyfrowy w systemie o podstawie odpowiada reszcie z dzielenia przez , z uwzględnieniem przypadków szczególnych: jeśli , to , jeśli i , to , jeśli , to .
Zwarty wzór dla . Własności Jeśli , dla pierwiastka cyfrowego zachodzą następujące własności: Idempotentność:
Operacje algebraiczne: Dodawanie:
Odejmowanie
Mnożenie
Potęgowanie
Sumowanie
Iloczyn iterowany
Okresowość: . Dowód Idempotentność: Niech: . Wówczas ze względu na to, że pierwiastek cyfrowy jest liczbą jednocyfrową w systemie o podstawie : . Rozważmy dwa przypadki: Jeżeli , to . Jeżeli , to z definicji: . Ponieważ: , otrzymujemy: . Zatem: . A więc: , q.e.d. Operacje algebraiczne: Dodawanie: Z definicji pierwiastka cyfrowego: . Z własności modularnej: . Po zastosowaniu funkcji do obu stron otrzymujemy: , q.e.d. Odejmowanie: Z definicji pierwiastka cyfrowego: . Z własności modularnej dla : . Po zastosowaniu funkcji do obu stron otrzymujemy: , q.e.d. Mnożenie: Z definicji pierwiastka cyfrowego: . Z własności modularnej: . Po zastosowaniu funkcji do obu stron otrzymujemy: , q.e.d. Potęgowanie: Z definicji pierwiastka cyfrowego: . Z własności modularnej: . Po zastosowaniu funkcji do obu stron otrzymujemy: , q.e.d. Sumowanie: Z definicji pierwiastka cyfrowego: . Z własności modularnej: . Po zastosowaniu funkcji do obu stron otrzymujemy: , q.e.d. Iloczyn iterowany: Z definicji pierwiastka cyfrowego: . Z własności modularnej: . Po zastosowaniu funkcji do obu stron otrzymujemy: , q.e.d. Okresowość: . Z definicji pierwiastka cyfrowego: . Z własności modularnej: . Po zastosowaniu funkcji do obu stron otrzymujemy: , q.e.d.
Informatyka W informatyce pierwiastek cyfrowy może być definiowany dla dowolnej podstawy systemu liczbowego . Najczęściej stosuje się podstawę dziesiętną (), jednak uogólnienie pozwala na implementację dla dowolnego systemu pozycyjnego.
Implementacja w C++ Istnieją dwa główne podejścia do obliczania tej funkcji: metoda iteracyjna oraz metoda oparta na wzorze modularnym. Implementacja iteracyjna #include <iostream> using namespace std;
int digital_root(long long number, int base = 10) { if (number == 0) return 0;
while (number >= base) { long long sum = 0;
while (number > 0) { sum += number % base; number /= base;
number = sum;
return static_cast<int>(number); }Metoda iteracyjna odwzorowuje definicję pierwiastka cyfrowego dla dowolnej podstawy systemu liczbowego. Polega na wielokrotnym sumowaniu cyfr liczby w systemie o podstawie base, aż do uzyskania wyniku jednocyfrowego. Złożoność obliczeniowa wynosi na każdą redukcję, gdzie to liczba cyfr.
Implementacja modularna #include <iostream> using namespace std;
int digital_root(long long number, int base = 10) { if (number == 0) return 0; return 1 + ((number - 1) % (base - 1)); }Metoda wzorowa wykorzystuje własność . Dzięki temu wynik można obliczyć bez iteracji. W tym przypadku złożoność obliczeniowa wynosi . Przypisy
Kategoria:Teoria liczb Kategoria:Działania na liczbach Kategoria:Arytmetyka modularna