Digital root
≈ 11 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The digital root (also repeated digital sum) of a natural number in a given radix is the (single digit) value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached. For example, in base 10, the digital root of the number 12345 is 6 because the sum of the digits in the number is 1 + 2 + 3 + 4 + 5 = 15, then the addition process is repeated for the resulting number 15, so that the sum of 1 + 5 equals 6, which is the digital root of that number. In base 10, this is equivalent to taking the remainder upon division by 9 (except when the digital root is 9, where the remainder upon division by 9 will be 0), which allows it to be used as a divisibility rule. The formula for the function \mathrm{dr}_b:\mathbb{N}\rightarrow\mathop{\bigcup}_{k=0}^{b-1}\{k\},\quad b\in\mathbb{N}_{\geqslant2} is expressed as: : \mathrm{dr}_b(n) := \begin{cases} 0 & n=0 \\ 1 + ((n - 1) \bmod (b - 1)) & n > 0\end{cases} .
The digital root (also repeated digital sum) of a natural number in a given radix is the (single digit) value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached. For example, in base 10, the digital root of the number 12345 is 6 because the sum of the digits in the number is 1 + 2 + 3 + 4 + 5 = 15, then the addition process is repeated for the resulting number 15, so that the sum of 1 + 5 equals 6, which is the digital root of that number. In base 10, this is equivalent to taking the remainder upon division by 9 (except when the digital root is 9, where the remainder upon division by 9 will be 0), which allows it to be used as a divisibility rule. The formula for the function \mathrm{dr}_b:\mathbb{N}\rightarrow\mathop{\bigcup}_{k=0}^{b-1}\{k\},\quad b\in\mathbb{N}_{\geqslant2} is expressed as: \mathrm{dr}_b(n) := \begin{cases} 0 & n=0 \\ 1 + ((n - 1) \bmod (b - 1)) & n > 0\end{cases} . F_{b}(n) = \sum_{i=0}^{k - 1} d_i where k = \lfloor \log_{b}{n} \rfloor + 1 is the number of digits in the number in base b , and d_i = \frac{n \bmod{b^{i+1}} - n \bmod b^i}{b^i} is the value of each digit of the number. A natural number n is a digital root if it is a fixed point for F_{b} , which occurs if F_{b}(n) = n . All natural numbers n are preperiodic points for F_{b} , regardless of the base. This is because if n \geq b , then n = \sum_{i=0}^{k - 1} d_i b^i and therefore F_{b}(n) = \sum_{i=0}^{k - 1} d_i because b > 1 . If n , then trivially F_{b}(n) = n Therefore, the only possible digital roots are the natural numbers 0 \leq n , and there are no cycles other than the fixed points of 0 \leq n . ===Example=== In base 12, 8 is the additive digital root of the base 10 number 3110, as for n = 3110 d_0 = \frac{3110 \bmod{12^{0+1}} - 3110 \bmod 12^0}{12^0} = \frac{3110 \bmod{12} - 3110 \bmod 1}{1} = \frac{2 - 0}{1} = \frac{2}{1} = 2 d_1 = \frac{3110 \bmod{12^{1+1}} - 3110 \bmod 12^1}{12^1} = \frac{3110 \bmod{144} - 3110 \bmod 12}{12} = \frac{86 - 2}{12} = \frac{84}{12} = 7 d_2 = \frac{3110 \bmod{12^{2+1}} - 3110 \bmod 12^2}{12^2} = \frac{3110 \bmod{1728} - 3110 \bmod 144}{144} = \frac{1382 - 86}{144} = \frac{1296}{144} = 9 d_3 = \frac{3110 \bmod{12^{3+1}} - 3110 \bmod 12^3}{12^3} = \frac{3110 \bmod{20736} - 3110 \bmod 1728}{1728} = \frac{3110 - 1382}{1728} = \frac{1728}{1728} = 1 F_{12}(3110) = \sum_{i=0}^{4 - 1} d_i = 2 + 7 + 9 + 1 = 19 This process shows that 3110 is 1972 in base 12. Now for F_{12}(3110) = 19 d_0 = \frac{19 \bmod{12^{0+1}} - 19 \bmod 12^0}{12^0} = \frac{19 \bmod{12} - 19 \bmod 1}{1} = \frac{7 - 0}{1} = \frac{7}{1} = 7 d_1 = \frac{19 \bmod{12^{1+1}} - 19 \bmod 12^1}{12^1} = \frac{19 \bmod{144} - 19 \bmod 12}{12} = \frac{19 - 7}{12} = \frac{12}{12} = 1 F_{12}(19) = \sum_{i=0}^{2 - 1} d_i = 1 + 7 = 8 shows that 19 is 17 in base 12. And as 8 is a 1-digit number in base 12, F_{12}(8) = 8 . ==Direct formulas== We can define the digit root directly for base b > 1 \operatorname{dr}_{b} : \mathbb{N} \rightarrow \mathbb{N} in the following ways: ===Congruence formula=== The formula in base b is: \operatorname{dr}_{b}(n) = \begin{cases} 0 & \mbox{if}\ n = 0, \\ b - 1 & \mbox{if}\ n \neq 0,\ n\ \equiv 0 \pmod{(b - 1)},\\ n \bmod{(b - 1)} & \mbox{if}\ n \not\equiv 0 \pmod{(b - 1)} \end{cases} or, \operatorname{dr}_{b}(n) = \begin{cases} 0 & \mbox{if}\ n = 0, \\ 1\ +\ ((n-1) \bmod{(b - 1)}) & \mbox{if}\ n \neq 0. \end{cases} In base 10, the corresponding sequence is . The digital root is the value modulo (b - 1) because b \equiv 1 \pmod{(b - 1)}, and thus b^i \equiv 1^i \equiv 1 \pmod{(b - 1)}. So regardless of the position i of digit d_i , d_i b^i\equiv d_i \pmod{(b-1)} , which explains why digits can be meaningfully added. Concretely, for a three-digit number n = d_2 b^2 + d_1 b^1 + d_0 b^0 , \operatorname{dr}_{b}(n) \equiv d_2 b^2 + d_1 b^1 + d_0 b^0 \equiv d_2 (1) + d_1 (1) + d_0 (1) \equiv d_2 + d_1 + d_0 \pmod{(b - 1)}. To obtain the modular value with respect to other numbers m , one can take weighted sums, where the weight on the i -th digit corresponds to the value of b^i \bmod{m} . In base 10, this is simplest for m=2, 5,\text{ and }10 , where higher digits except for the unit digit vanish (since 2 and 5 divide powers of 10), which corresponds to the familiar fact that the divisibility of a decimal number with respect to 2, 5, and 10 can be checked by the last digit. Also of note is the modulus m = b + 1 . Since b \equiv -1 \pmod{(b + 1)}, and thus b^2 \equiv (-1)^2 \equiv 1 \pmod{(b + 1)}, taking the alternating sum of digits yields the value modulo (b + 1) . ===Using the floor function=== It helps to see the digital root of a positive integer as the position it holds with respect to the largest multiple of b - 1 less than the number itself. For example, in base 6 the digital root of 11 is 2, which means that 11 is the second number after 6 - 1 = 5 . Likewise, in base 10 the digital root of 2035 is 1, which means that 2035 - 1 = 2034|9 . If a number produces a digital root of exactly b - 1 , then the number is a multiple of b - 1 . With this in mind the digital root of a positive integer n may be defined by using floor function \lfloor x\rfloor , as \operatorname{dr}_{b}(n)=n-(b - 1)\left\lfloor\frac{n-1}{b - 1}\right\rfloor. \operatorname{dr}_b(\operatorname{dr}_b(n)) = \operatorname{dr}_b(n). Since the digital root is a single digit (i.e. 0 \le \operatorname{dr}_b(n) ), applying the digit-sum process again leaves it unchanged. Compatibility with addition \operatorname{dr}_b(a + c) = \operatorname{dr}_b(\operatorname{dr}_b(a) + \operatorname{dr}_b(c)). This follows from the congruence a \equiv \operatorname{dr}_b(a), \quad c \equiv \operatorname{dr}_b(c) \pmod{b-1}. Compatibility with subtraction \operatorname{dr}_b(a - c) \equiv \operatorname{dr}_b(a) - \operatorname{dr}_b(c) \pmod{b-1}. In particular, after applying \operatorname{dr}_b to the result, subtraction is preserved up to reduction modulo b-1 . Compatibility with multiplication \operatorname{dr}_b(ac) = \operatorname{dr}_b(\operatorname{dr}_b(a)\cdot \operatorname{dr}_b(c)). This is a consequence of multiplicative compatibility modulo b-1 . Compatibility with exponentiation \operatorname{dr}_b(a^k) = \operatorname{dr}_b(\operatorname{dr}_b(a)^k). This follows from a \equiv \operatorname{dr}_b(a) \pmod{b-1} , so a^k \equiv \operatorname{dr}_b(a)^k \pmod{b-1}. These properties show that the digital root behaves like reduction modulo b-1 , followed by mapping the residue 0 to b-1 . ==Additive persistence== The additive persistence counts how many times we must sum its digits to arrive at its digital root. For example, the additive persistence of 2718 in base 10 is 2: first we find that 2 + 7 + 1 + 8 = 18, then that 1 + 8 = 9. There is no limit to the additive persistence of a number in a number base b . Proof: For a given number n , the persistence of the number consisting of n repetitions of the digit 1 is 1 higher than that of n . The smallest numbers of additive persistence 0, 1, ... in base 10 are: 0, 10, 19, 199, 19 999 999 999 999 999 999 999, ... The next number in the sequence (the smallest number of additive persistence 5) is 2 × 10 2×(10 22 − 1)/9 − 1 (that is, 1 followed by 2 222 222 222 222 222 222 222 nines). For any fixed base, the sum of the digits of a number is proportional to its logarithm; therefore, the additive persistence is proportional to the iterated logarithm. ==Programming example== The example below implements the digit sum described in the definition above to search for digital roots and additive persistences in Java. import java.util.HashSet; public class DigitFunctions { // Sum of digits in base b static int digitSum(int x, int b) { int total = 0; while (x > 0) { total += x % b; x /= b; } return total; } // Digital root in base b static int digitalRoot(int x, int b) { HashSet seen = new HashSet<>(); while (!seen.contains(x)) { seen.add(x); x = digitSum(x, b); } return x; } // Additive persistence in base b static int additivePersistence(int x, int b) { HashSet seen = new HashSet<>(); while (!seen.contains(x)) { seen.add(x); x = digitSum(x, b); } return seen.size() - 1; } // Example usage public static void main(String[] args) { int x = 9876; int b = 10; System.out.println("Digit Sum: " + digitSum(x, b)); System.out.println("Digital Root: " + digitalRoot(x, b)); System.out.println("Additive Persistence: " + additivePersistence(x, b)); } } ==References== ( ) ( ) ( ) ( ) ( )
Text derived from https://en.wikipedia.org/w/index.php?oldid=1368983554 under CC BY-SA 4.0; modifications have been made.