View source for Digital root

{{Short description|Repeated sum of a number's digits}}
{{no footnotes|date=January 2016}}
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 [[digit sum|'''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 again 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]].

== Formal definition ==
Let <math>n</math> be a natural number. For base <math>b > 1</math>, we define the '''[[digit sum]]''' <math>F_{b} : \mathbb{N} \rightarrow \mathbb{N}</math> to be the following:
:<math>F_{b}(n) = \sum_{i=0}^{k - 1} d_i</math>
where <math>k = \lfloor \log_{b}{n} \rfloor + 1</math> is the number of digits in the number in base <math>b</math>, and
:<math>d_i = \frac{n \bmod{b^{i+1}} - n \bmod b^i}{b^i}</math> 
is the value of each digit of the number. A natural number <math>n</math> is a '''digital root''' if it is a [[Fixed point (mathematics)|fixed point]] for <math>F_{b}</math>, which occurs if <math>F_{b}(n) = n</math>. 

All natural numbers <math>n</math> are [[periodic point#iterated function|preperiodic points]] for <math>F_{b}</math>, regardless of the base. This is because if <math>n \geq b</math>, then
:<math>n = \sum_{i=0}^{k - 1} d_i b^i</math>
and therefore
:<math>F_{b}(n) = \sum_{i=0}^{k - 1} d_i < \sum_{i=0}^{k - 1} d_i b^i = n</math>
because <math>b > 1</math>.
If <math>n < b</math>, then trivially 
:<math>F_{b}(n) = n</math>
Therefore, the only possible digital roots are the natural numbers <math>0 \leq n < b</math>, and there are no cycles other than the fixed points of <math>0 \leq n < b</math>.

===Example===
In [[base 12]], 8 is the additive digital root of the [[base 10]] number 3110, as for <math>n = 3110</math>
: <math>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</math>
: <math>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</math>
: <math>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</math>
: <math>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</math>
: <math>F_{12}(3110) = \sum_{i=0}^{4 - 1} d_i = 2 + 7 + 9 + 1 = 19</math>
This process shows that 3110 is 1972 in [[base 12]]. Now for <math>F_{12}(3110) = 19</math>
: <math>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</math>
: <math>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</math>
: <math>F_{12}(19) = \sum_{i=0}^{2 - 1} d_i = 1 + 7 = 8</math>
shows that 19 is 17 in [[base 12]]. And as 8 is a 1-digit number in [[base 12]],
: <math>F_{12}(8) = 8</math>.

==Direct formulas==
We can define the '''digit root''' directly for base <math>b > 1</math> <math>\operatorname{dr}_{b} : \mathbb{N} \rightarrow \mathbb{N}</math> in the following ways:
===Congruence formula===
The formula in base <math>b</math> is:
:<math> \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}
</math>
or,
:<math> \operatorname{dr}_{b}(n) = 
\begin{cases}
0 & \mbox{if}\ n = 0, \\ 
1\ +\ ((n-1) \bmod{(b - 1)}) & \mbox{if}\ n \neq 0.
\end{cases}
</math>

In [[base 10]], the corresponding sequence is {{OEIS|id=A010888}}.

The digital root is the value modulo <math>(b - 1)</math> because <math>b \equiv 1 \pmod{(b - 1)},</math> and thus <math>b^i \equiv 1^i \equiv 1 \pmod{(b - 1)}.</math> So regardless of the position <math>i</math> of digit <math>d_i</math>, <math>d_i b^i\equiv d_i \pmod{(b-1)}</math>, which explains why digits can be meaningfully added. Concretely, for a three-digit number <math>n = d_2 b^2 + d_1 b^1 + d_0 b^0</math>,
:<math>\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)}.</math>

To obtain the modular value with respect to other numbers <math>m</math>, one can take [[weighted sum]]s, where the weight on the <math>i</math>-th digit corresponds to the value of <math>b^i \bmod{m}</math>. In [[base 10]], this is simplest for <math>m=2, 5,\text{ and }10</math>, 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 <math>m = b + 1</math>. Since <math>b \equiv -1 \pmod{(b + 1)},</math> and thus <math>b^2 \equiv (-1)^2 \equiv 1 \pmod{(b + 1)},</math> taking the ''alternating'' sum of digits yields the value modulo <math>(b + 1)</math>.

===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 <math>b - 1</math> 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 <math>6 - 1 = 5</math>. Likewise, in base 10 the digital root of 2035 is 1, which means that <math>2035 - 1 = 2034|9</math>. If a number produces a digital root of exactly <math>b - 1</math>, then the number is a multiple of <math>b - 1</math>.

With this in mind the digital root of a positive integer <math>n</math> may be defined by using [[floor function]] <math>\lfloor x\rfloor </math>, as
:<math>\operatorname{dr}_{b}(n)=n-(b - 1)\left\lfloor\frac{n-1}{b - 1}\right\rfloor.</math>

==Properties==
* The digital root of <math>a_1 + a_2</math> in base <math>b</math> is the digital root of the sum of the digital root of <math>a_1</math> and the digital root of <math>a_2</math>: <math display="block">\operatorname{dr}_{b}(a_1 + a_2) = \operatorname{dr}_{b}(\operatorname{dr}_{b}(a_1)+\operatorname{dr}_{b}(a_2)).</math> This property can be used as a sort of [[checksum]], to check that a sum has been performed correctly. 

* The digital root of <math>a_1 - a_2</math> in base <math>b</math> is congruent to the difference of the digital root of <math>a_1</math> and the digital root of <math>a_2</math> modulo <math>(b - 1)</math>: <math display="block">\operatorname{dr}_{b}(a_1 - a_2) \equiv (\operatorname{dr}_{b}(a_1)-\operatorname{dr}_{b}(a_2)) \pmod{(b - 1)}.</math>

* The digital root of <math>-n</math> in base <math>b</math> is <math display="block">\operatorname{dr}_{b}(-n) \equiv -\operatorname{dr}_{b}(n) \bmod{b - 1}.</math>

* The digital root of the product of nonzero single digit numbers <math>a_1 \cdot a_2</math> in base <math>b</math> is given by the [[Vedic Square]] in base <math>b</math>. 

* The digital root of <math>a_1 \cdot a_2</math> in base <math>b</math> is the digital root of the product of the digital root of <math>a_1</math> and the digital root of <math>a_2</math>: <math display="block">\operatorname{dr}_{b}(a_1 a_2) = \operatorname{dr}_{b}(\operatorname{dr}_{b}(a_1)\cdot\operatorname{dr}_{b}(a_2) ).</math>

==Additive persistence==
The '''additive [[Persistence of a number|persistence]]''' counts how many times we must [[digit sum|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&nbsp;+&nbsp;7&nbsp;+&nbsp;1&nbsp;+&nbsp;8&nbsp;=&nbsp;18, then that&nbsp;1&nbsp;+&nbsp;8&nbsp;=&nbsp;9. 

There is no limit to the additive persistence of a number in a number base <math>b</math>. Proof: For a given number <math>n</math>, the persistence of the number consisting of <math>n</math> repetitions of the digit 1 is 1 higher than that of <math>n</math>. The smallest numbers of additive persistence 0, 1, ... in base 10 are:
:0, 10, 19, 199, 19&thinsp;999&thinsp;999&thinsp;999&thinsp;999&thinsp;999&thinsp;999&thinsp;999, ... {{OEIS|A006050}}
The next number in the sequence (the smallest number of additive persistence 5) is 2&nbsp;×&nbsp;10<sup>2×(10<sup>22</sup>&nbsp;−&nbsp;1)/9</sup>&nbsp;−&nbsp;1 (that is, 1 followed by 2&thinsp;222&thinsp;222&thinsp;222&thinsp;222&thinsp;222&thinsp;222&thinsp;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]].<ref name="Meimaris">{{citation |last=Meimaris | first=Antonios | title=On the additive persistence of a number in base p| publisher=Preprint | year=2015| url=https://www.academia.edu/11654065}}</ref>

==Programming example==
The example below implements the digit sum described in the definition above to search for digital roots and additive persistences in [[Python (programming language)|Python]].
<syntaxhighlight lang="python">
def digit_sum(x: int, b: int) -> int:
    total = 0
    while x > 0:
        total = total + (x % b)
        x = x // b
    return total

def digital_root(x: int, b: int) -> int:
    seen = set()
    while x not in seen:
        seen.add(x)
        x = digit_sum(x, b)
    return x

def additive_persistence(x: int, b: int) -> int:
    seen = set()
    while x not in seen:
        seen.add(x)
        x = digit_sum(x, b)
    return len(seen) - 1
</syntaxhighlight>

== In popular culture ==
Digital roots are used in Western [[numerology]], but certain numbers deemed to have occult significance (such as 11 and 22) are not always completely reduced to a single digit.

Digital roots form an important mechanic in the visual novel adventure game ''[[Nine Hours, Nine Persons, Nine Doors]]''.

== See also ==
{{Div col}}
* [[Arithmetic dynamics#Other areas in which number theory and dynamics interact|Arithmetic dynamics]]
* [[Base 9]]
* [[Casting out nines]]
* [[Digit sum]]
* [[Divisibility rule]]
* [[Hamming weight]]
* [[Multiplicative digital root]]
{{Div col end}}

==References==
{{reflist}}
*{{Citation|last1=Averbach|first1=Bonnie|author1-link=Bonnie Averbach|last2=Chein|first2=Orin|author2-link=Orin Chein|date=27 May 1999|title=Problem Solving Through Recreational Mathematics|title-link=Problem Solving Through Recreational Mathematics|publisher=Courier Dover Publications|location=Mineola, NY|edition=reprinted|series=Dover Books on Mathematics|isbn=0-486-40917-1|pages=[https://archive.org/details/isbn_9780486409177/page/125 125–127]}} ({{Google books|qtMoAwAAQBAJ|online copy|page=125}})
*{{Citation|last=Ghannam|first=Talal|author-link=Talal Ghannam|date=4 January 2011|title=The Mystery of Numbers: Revealed Through Their Digital Root|publisher=CreateSpace Publications|isbn=978-1-4776-7841-1|url=https://www.createspace.com/3529186|pages=68–73|access-date=11 February 2016|archive-url=https://web.archive.org/web/20160329004316/https://www.createspace.com/3529186|archive-date=29 March 2016|url-status=dead}} ({{Google books|PN4dzi8eoZQC|online copy|page=68}})
*{{Citation|last=Hall|first=F. M.|author-link=Frederick Michael Hall|year=1980|title=An Introduction into Abstract Algebra|publisher=CUP Archive|location=Cambridge, U.K.|edition=2nd|volume=1|isbn=978-0-521-29861-2|page=101}} ({{Google books|qqs8AAAAIAAJ|online copy|page=101}})
*{{Citation|last=O'Beirne|first=T. H.|author-link=T. H. O'Beirne|date=13 March 1961|title=Puzzles and Paradoxes|journal=New Scientist|publisher=Reed Business Information|volume=10|issue=230|issn=0262-4079|pages=53–54}} ({{Google books|j4VdAP43V7cC|online copy|page=53}})
*{{Citation|last1=Rouse Ball|first1=W. W.|author1-link=Walter William Rouse Ball|last2=Coxeter|first2=H. S. M.|author2-link=Harold Scott Macdonald Coxeter|date=6 May 2010|title=Mathematical Recreations and Essays|publisher=Dover Publications|location=NY|edition=13th|series=Dover Recreational Mathematics|isbn=978-0-486-25357-2}} ({{Google books|9lJqNJhYc9oC|online copy}})

== External links ==
* [http://people.revoledu.com/kardi/tutorial/DigitSum/index.html Patterns of digital roots using MS Excel]
*{{MathWorld|title=Digital Root|id=DigitalRoot}}

{{Classes of natural numbers}}

[[Category:Algebra]]
[[Category:Arithmetic dynamics]]
[[Category:Base-dependent integer sequences]]
[[Category:Number theory]]

[[de:Quersumme#Einstellige (oder iterierte) Quersumme]]