Pierwiastek cyfrowy

Pierwiastek cyfrowy (ang. digital root) – funkcja przypisująca liczbie naturalnej jednocyfrową wartość otrzymaną poprzez iteracyjne sumowanie jej cyfr^[1]. Wzór funkcji $\mathrm {dr} _{b}:\mathbb {N} \rightarrow \mathop {\bigcup } _{k=0}^{b-1}\{k\},\quad b\in \mathbb {N} _{\geqslant 2}$ można przedstawić jako:

\mathrm {dr} _{b}(n):={\begin{cases}0&n=0\\1+((n-1){\bmod {(}}b-1))&n>0\end{cases}}

.

Definicja

Pierwiastek cyfrowy liczby naturalnej $n$ otrzymuje się, sumując wszystkie cyfry liczby, a następnie powtarzając tę operację dla uzyskanego wyniku aż do momentu otrzymania liczby jednocyfrowej^[2].

Przykład:

6741\rightarrow 6+7+4+1=18\rightarrow 1+8=9

\mathrm {dr} (6741)=\mathrm {dr} (18)=9

Zatem pierwiastek cyfrowy liczby $6741$ wynosi $9$ .

Uproszczenie

Pierwiastek cyfrowy liczby jest równoważny jej reszcie z dzielenia przez $9$ (z wyjątkiem przypadku, gdy liczba jest podzielna przez $9$ – wtedy wynik wynosi $9$ zamiast $0$ ). Dodatkowo przyjmuje się, że $\mathrm {dr} (0)=0$ . Można go obliczyć za pomocą wzoru $\mathrm {dr} (n)=1+((n-1){\bmod {9}})$ dla $n>0$ .

Dowód

Niech liczba naturalna $n$ ma rozwinięcie dziesiętne $n=\sum _{i=0}^{k}a_{i}\cdot 10^{i}$ , gdzie $a_{i}\in \{0,1,\dots ,9\}$ są jej cyframi.

Ponieważ $10\equiv 1{\pmod {9}}$ , zachodzi także $10^{i}\equiv 1{\pmod {9}}$ dla każdego $i\geqslant 0$ . Stąd $n\equiv \sum _{i=0}^{k}a_{i}{\pmod {9}}$ .

Oznacza to, że liczba $n$ i suma jej cyfr mają tę samą resztę z dzielenia przez $9$ . Powtarzając operację sumowania cyfr, nie zmieniamy tej reszty, aż do uzyskania liczby jednocyfrowej.

Każdej klasie reszt modulo $9$ odpowiada dokładnie jedna liczba jednocyfrowa z zakresu $1$ – $9$ , przy czym reszcie 0 odpowiada liczba $9$ . Zatem:

jeśli $n\not \equiv 0{\pmod {9}}$ , to $\mathrm {dr} (n)=n{\bmod {9}}$ ,
jeśli $n\equiv 0{\pmod {9}}$ i $n>0$ , to $\mathrm {dr} (n)=9$ .

W konsekwencji, dla $n>0$ :

\mathrm {dr} (n)=1+((n-1){\bmod {9}})

^[3].

Inne systemy liczbowe

Pojęcie pierwiastka cyfrowego można uogólnić na dowolny system liczbowy o podstawie $b\geqslant 2$ . Dla liczby naturalnej zapisanej w systemie o podstawie $b$ :

n=\sum _{i=0}^{k}a_{i}b^{i}

,

gdzie $a_{i}\in \{0,1,\dots ,b-1\}$ , pierwiastek cyfrowy definiuje się jako wynik iteracyjnego sumowania cyfr aż do uzyskania jednej cyfry w tym systemie.

Zachodzi:

b\equiv 1{\pmod {(b-1)}}

, a więc

b^{m}\equiv 1{\pmod {(b-1)}}

dla każdego

m\geqslant 0

, skąd:

n\equiv \sum _{i=0}^{k}a_{i}{\pmod {(b-1)}}

.

W konsekwencji pierwiastek cyfrowy w systemie o podstawie $b$ odpowiada reszcie z dzielenia przez $b-1$ , z uwzględnieniem przypadków szczególnych:

jeśli $n\not \equiv 0{\pmod {(b-1)}}$ , to $\mathrm {dr} _{b}(n)=n{\bmod {(}}b-1)$ ,
jeśli $n\equiv 0{\pmod {(b-1)}}$ i $n>0$ , to $\mathrm {dr} _{b}(n)=b-1$ ,
jeśli $n=0$ , to $\mathrm {dr} _{b}(n)=0$ .

Zwarty wzór $\mathrm {dr} _{b}(n)=1+((n-1){\bmod {(}}b-1))$ dla $n>0$ ^[4].

Własności

Jeśli $b,k,l,n\in \mathbb {N} ;b\geqslant 2$ , dla pierwiastka cyfrowego zachodzą następujące własności:

Idempotentność:
$\mathrm {dr} _{b}(\mathrm {dr} _{b}(k))=\mathrm {dr} _{b}(k)$
Operacje algebraiczne:
- Dodawanie:
  $\mathrm {dr} _{b}(k+l)=\mathrm {dr} _{b}\!{\bigl (}\mathrm {dr} _{b}(k)+\mathrm {dr} _{b}(l){\bigr )}$
- Odejmowanie
  $\mathrm {dr} _{b}(k-l)=\mathrm {dr} _{b}\!{\bigl (}\mathrm {dr} _{b}(k)-\mathrm {dr} _{b}(l){\bigr )};\quad k\geqslant l;\quad {dr}_{b}(k)\geqslant {dr}_{b}(l)$
- Mnożenie
  $\mathrm {dr} _{b}(k\cdot l)=\mathrm {dr} _{b}(\mathrm {dr} _{b}(k)\cdot \mathrm {dr} _{b}(l))$
- Potęgowanie
  $\mathrm {dr} _{b}(k^{l})=\mathrm {dr} _{b}(\mathrm {dr} _{b}(k)^{l})$
- Sumowanie
  $\mathrm {dr} _{b}\!\left(\sum _{i=1}^{n}k_{i}\right)=\mathrm {dr} _{b}\!\left(\sum _{i=1}^{n}\mathrm {dr} _{b}(k_{i})\right)$
- Iloczyn iterowany
  $\mathrm {dr} _{b}\!\left(\prod _{i=1}^{n}k_{i}\right)=\mathrm {dr} _{b}\!\left(\prod _{i=1}^{n}\mathrm {dr} _{b}(k_{i})\right)$
Okresowość:
$\mathrm {dr} _{b}(k)=\mathrm {dr} _{b}(k+l(b-1))$ .

Dowód

Idempotentność:
Niech:
$x=\mathrm {dr} _{b}(k)$ .

Wówczas ze względu na to, że pierwiastek cyfrowy jest liczbą jednocyfrową w systemie o podstawie $b$ :
$0\leqslant x<b$ .
Rozważmy dwa przypadki:
- Jeżeli $x=0$ , to
  $\mathrm {dr} _{b}(x)=\mathrm {dr} _{b}(0)=0=x$ .
- Jeżeli $1\leqslant x<b$ , to z definicji:
  $\mathrm {dr} _{b}(x)=1+((x-1){\bmod {(}}b-1))$ .
Ponieważ:
$0\leqslant x-1<b-1$ ,

otrzymujemy:
$(x-1){\bmod {(}}b-1)=x-1$ .

Zatem:
$\mathrm {dr} _{b}(x)=1+(x-1)=x$ .

A więc:
$\mathrm {dr} _{b}(\mathrm {dr} _{b}(k))=\mathrm {dr} _{b}(k)$ , q.e.d.
Operacje algebraiczne:
- Dodawanie:
  Z definicji pierwiastka cyfrowego:
  $k\equiv \mathrm {dr} _{b}(k),\quad l\equiv \mathrm {dr} _{b}(l){\pmod {b-1}}$ .
  
  Z własności modularnej:
  $k+l\equiv \mathrm {dr} _{b}(k)+\mathrm {dr} _{b}(l){\pmod {b-1}}$ .
  
  Po zastosowaniu funkcji $\mathrm {dr} _{b}$ do obu stron otrzymujemy:
  $\mathrm {dr} _{b}(k+l)=\mathrm {dr} _{b}(\mathrm {dr} _{b}(k)+\mathrm {dr} _{b}(l))$ , q.e.d.
- Odejmowanie:
  Z definicji pierwiastka cyfrowego:
  $k\equiv \mathrm {dr} _{b}(k),\quad l\equiv \mathrm {dr} _{b}(l){\pmod {b-1}}$ .
  
  Z własności modularnej dla $k\geqslant l;\quad {dr}_{b}(k)\geqslant {dr}_{b}(l)$ :
  $k-l\equiv \mathrm {dr} _{b}(k)-\mathrm {dr} _{b}(l){\pmod {b-1}}$ .
  
  Po zastosowaniu funkcji $\mathrm {dr} _{b}$ do obu stron otrzymujemy:
  $\mathrm {dr} _{b}(k-l)=\mathrm {dr} _{b}(\mathrm {dr} _{b}(k)-\mathrm {dr} _{b}(l))$ , q.e.d.
- Mnożenie:
  Z definicji pierwiastka cyfrowego:
  $k\equiv \mathrm {dr} _{b}(k),\quad l\equiv \mathrm {dr} _{b}(l){\pmod {b-1}}$ .
  
  Z własności modularnej:
  $kl\equiv \mathrm {dr} _{b}(k)\cdot \mathrm {dr} _{b}(l){\pmod {b-1}}$ .
  
  Po zastosowaniu funkcji $\mathrm {dr} _{b}$ do obu stron otrzymujemy:
  $\mathrm {dr} _{b}(kl)=\mathrm {dr} _{b}(\mathrm {dr} _{b}(k)\cdot \mathrm {dr} _{b}(l))$ , q.e.d.
- Potęgowanie:
  Z definicji pierwiastka cyfrowego:
  $k\equiv (\mathrm {dr} _{b}(k)){\pmod {b-1}}$ .
  
  Z własności modularnej:
  $k^{l}\equiv (\mathrm {dr} _{b}(k))^{l}{\pmod {b-1}}$ .
  
  Po zastosowaniu funkcji $\mathrm {dr} _{b}$ do obu stron otrzymujemy:
  $\mathrm {dr} _{b}(k^{l})=\mathrm {dr} _{b}(\mathrm {dr} _{b}(k)^{l})$ , q.e.d.
- Sumowanie:
  Z definicji pierwiastka cyfrowego:
  $k_{i}\equiv \mathrm {dr} _{b}(k_{i}){\pmod {b-1}}$ .
  
  Z własności modularnej:
  $\sum _{i=1}^{n}k_{i}\equiv \sum _{i=1}^{n}\mathrm {dr} _{b}(k_{i}){\pmod {b-1}}$ .
  
  Po zastosowaniu funkcji $\mathrm {dr} _{b}$ do obu stron otrzymujemy:
  $\mathrm {dr} _{b}\!\left(\sum _{i=1}^{n}k_{i}\right)=\mathrm {dr} _{b}\!\left(\sum _{i=1}^{n}\mathrm {dr} _{b}(k_{i})\right)$ , q.e.d.
- Iloczyn iterowany:
  Z definicji pierwiastka cyfrowego:
  $k_{i}\equiv \mathrm {dr} _{b}(k_{i}){\pmod {b-1}}$ .
  
  Z własności modularnej:
  $\prod _{i=1}^{n}k_{i}\equiv \prod _{i=1}^{n}\mathrm {dr} _{b}(k_{i}){\pmod {b-1}}$ .
  
  Po zastosowaniu funkcji $\mathrm {dr} _{b}$ do obu stron otrzymujemy:
  $\mathrm {dr} _{b}\!\left(\prod _{i=1}^{n}k_{i}\right)=\mathrm {dr} _{b}\!\left(\prod _{i=1}^{n}\mathrm {dr} _{b}(k_{i})\right)$ , q.e.d.
Okresowość:
$\mathrm {dr} _{b}(k)=\mathrm {dr} _{b}(k+l(b-1))$ .

Z definicji pierwiastka cyfrowego:
$k+l(b-1)\equiv k{\pmod {b-1}}$ .

Z własności modularnej:
$k\equiv \mathrm {dr} _{b}(k){\pmod {b-1}}$ .

Po zastosowaniu funkcji $\mathrm {dr} _{b}$ do obu stron otrzymujemy:
$\mathrm {dr} _{b}(k)=\mathrm {dr} _{b}(k+l(b-1))$ , q.e.d.

Informatyka

W informatyce pierwiastek cyfrowy może być definiowany dla dowolnej podstawy systemu liczbowego $b$ . Najczęściej stosuje się podstawę dziesiętną ( $b=10$ ), 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 $O(k)$ na każdą redukcję, gdzie $k$ to liczba cyfr^[5].

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ść $\mathrm {dr} _{b}(n)=1+((n-1){\bmod {(}}b-1))$ . Dzięki temu wynik można obliczyć bez iteracji. W tym przypadku złożoność obliczeniowa wynosi $O(1)$ ^[5].

Przypisy

↑ Kalkulator Pierwiastka Cyfrowego [online], miniwebtool.com .
↑ Pierwiastek cyfrowy [online], DEV Community, 18 marca 2022 .
↑ Eric W.E.W. Weisstein Eric W.E.W., Digital Root [online], mathworld.wolfram.com (ang.).
↑ F.M.F.M. Hall F.M.F.M., An Introduction to Abstract Algebra, CUP Archive, 6 kwietnia 1972, ISBN 978-0-521-08484-0 (ang.).
1 2 MateuszM. Dański MateuszM., Trwałość liczb [online], mattomatti.com .

[1] Kalkulator Pierwiastka Cyfrowego [online], miniwebtool.com .

[2] Pierwiastek cyfrowy [online], DEV Community, 18 marca 2022 .

[3] Eric W.E.W. Weisstein Eric W.E.W., Digital Root [online], mathworld.wolfram.com (ang.).

[4] F.M.F.M. Hall F.M.F.M., An Introduction to Abstract Algebra, CUP Archive, 6 kwietnia 1972, ISBN 978-0-521-08484-0 (ang.).

[:0-5] 1 2 MateuszM. Dański MateuszM., Trwałość liczb [online], mattomatti.com .

[1]

[2]

[3]

[4]

[5]