# Digital root

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 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 ${\displaystyle n}$ be a natural number. For base ${\displaystyle b>1}$, we define the digit sum ${\displaystyle F_{b}:\mathbb {N} \rightarrow \mathbb {N} }$ to be the following:

${\displaystyle F_{b}(n)=\sum _{i=0}^{k-1}d_{i}}$

where ${\displaystyle k=\lfloor \log _{b}{n}\rfloor +1}$ is the number of digits in the number in base ${\displaystyle b}$, and

${\displaystyle 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 ${\displaystyle n}$ is a digital root if it is a fixed point for ${\displaystyle F_{b}}$, which occurs if ${\displaystyle F_{b}(n)=n}$.

All natural numbers ${\displaystyle n}$ are preperiodic points for ${\displaystyle F_{b}}$, regardless of the base. This is because if ${\displaystyle n\geq b}$, then

${\displaystyle n=\sum _{i=0}^{k-1}d_{i}b^{i}}$

and therefore

${\displaystyle F_{b}(n)=\sum _{i=0}^{k-1}d_{i}<\sum _{i=0}^{k-1}d_{i}b^{i}=n}$

because ${\displaystyle b>1}$. If ${\displaystyle n, then trivially

${\displaystyle F_{b}(n)=n}$

Therefore, the only possible digital roots are the natural numbers ${\displaystyle 0\leq n, and there are no cycles other than the fixed points of ${\displaystyle 0\leq n.

### Example

In base 12, 8 is the additive digital root of the base 10 number 3110, as for ${\displaystyle n=3110}$

${\displaystyle d_{0}={\frac {3110{\bmod {12^{0+1}}}-3110{\bmod {1}}2^{0}}{12^{0}}}={\frac {3110{\bmod {12}}-3110{\bmod {1}}}{1}}={\frac {2-0}{1}}={\frac {2}{1}}=2}$
${\displaystyle d_{1}={\frac {3110{\bmod {12^{1+1}}}-3110{\bmod {1}}2^{1}}{12^{1}}}={\frac {3110{\bmod {144}}-3110{\bmod {1}}2}{12}}={\frac {86-2}{12}}={\frac {84}{12}}=7}$
${\displaystyle d_{2}={\frac {3110{\bmod {12^{2+1}}}-3110{\bmod {1}}2^{2}}{12^{2}}}={\frac {3110{\bmod {1728}}-3110{\bmod {1}}44}{144}}={\frac {1382-86}{144}}={\frac {1296}{144}}=9}$
${\displaystyle d_{3}={\frac {3110{\bmod {12^{3+1}}}-3110{\bmod {1}}2^{3}}{12^{3}}}={\frac {3110{\bmod {20736}}-3110{\bmod {1}}728}{1728}}={\frac {3110-1382}{1728}}={\frac {1728}{1728}}=1}$
${\displaystyle 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 ${\displaystyle F_{12}(3110)=19}$

${\displaystyle d_{0}={\frac {19{\bmod {12^{0+1}}}-19{\bmod {1}}2^{0}}{12^{0}}}={\frac {19{\bmod {12}}-19{\bmod {1}}}{1}}={\frac {7-0}{1}}={\frac {7}{1}}=7}$
${\displaystyle d_{1}={\frac {19{\bmod {12^{1+1}}}-19{\bmod {1}}2^{1}}{12^{1}}}={\frac {19{\bmod {144}}-19{\bmod {1}}2}{12}}={\frac {19-7}{12}}={\frac {12}{12}}=1}$
${\displaystyle 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,

${\displaystyle F_{12}(8)=8}$.

## Direct formulas

We can define the digit root directly for base ${\displaystyle b>1}$ ${\displaystyle \operatorname {dr} _{b}:\mathbb {N} \rightarrow \mathbb {N} }$ in the following ways:

### Congruence formula

The formula in base ${\displaystyle b}$ is:

${\displaystyle \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,

${\displaystyle \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 (sequence A010888 in the OEIS).

The digital root is the value modulo ${\displaystyle (b-1)}$ because ${\displaystyle b\equiv 1{\pmod {(b-1)}},}$ and thus ${\displaystyle b^{i}\equiv 1^{i}\equiv 1{\pmod {(b-1)}}.}$ So regardless of the position ${\displaystyle i}$ of digit ${\displaystyle d_{i}}$, ${\displaystyle d_{i}b^{i}\equiv d_{i}{\pmod {(b-1)}}}$, which explains why digits can be meaningfully added. Concretely, for a three-digit number ${\displaystyle n=d_{2}b^{2}+d_{1}b^{1}+d_{0}b^{0}}$,

${\displaystyle \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 ${\displaystyle m}$, one can take weighted sums, where the weight on the ${\displaystyle i}$-th digit corresponds to the value of ${\displaystyle b^{i}{\bmod {m}}}$. In base 10, this is simplest for ${\displaystyle 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 ${\displaystyle m=b+1}$. Since ${\displaystyle b\equiv -1{\pmod {(b+1)}},}$ and thus ${\displaystyle b^{2}\equiv (-1)^{2}\equiv 1{\pmod {(b+1)}},}$ taking the alternating sum of digits yields the value modulo ${\displaystyle (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 ${\displaystyle 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 ${\displaystyle 6-1=5}$. Likewise, in base 10 the digital root of 2035 is 1, which means that ${\displaystyle 2035-1=2034|9}$. If a number produces a digital root of exactly ${\displaystyle b-1}$, then the number is a multiple of ${\displaystyle b-1}$.

With this in mind the digital root of a positive integer ${\displaystyle n}$ may be defined by using floor function ${\displaystyle \lfloor x\rfloor }$, as

${\displaystyle \operatorname {dr} _{b}(n)=n-(b-1)\left\lfloor {\frac {n-1}{b-1}}\right\rfloor .}$

## Properties

• The digital root of ${\displaystyle a_{1}+a_{2}}$ in base ${\displaystyle b}$ is the digital root of the sum of the digital root of ${\displaystyle a_{1}}$ and the digital root of ${\displaystyle a_{2}}$:
${\displaystyle \operatorname {dr} _{b}(a_{1}+a_{2})=\operatorname {dr} _{b}(\operatorname {dr} _{b}(a_{1})+\operatorname {dr} _{b}(a_{2})).}$
This property can be used as a sort of checksum, to check that a sum has been performed correctly.
• The digital root of ${\displaystyle a_{1}-a_{2}}$ in base ${\displaystyle b}$ is congruent to the difference of the digital root of ${\displaystyle a_{1}}$ and the digital root of ${\displaystyle a_{2}}$ modulo ${\displaystyle (b-1)}$:
${\displaystyle \operatorname {dr} _{b}(a_{1}-a_{2})\equiv (\operatorname {dr} _{b}(a_{1})-\operatorname {dr} _{b}(a_{2})){\pmod {(b-1)}}.}$
• The digital root of ${\displaystyle -n}$ in base ${\displaystyle b}$ is
${\displaystyle \operatorname {dr} _{b}(-n)\equiv -\operatorname {dr} _{b}(n){\bmod {b-1}}.}$
• The digital root of the product of nonzero single digit numbers ${\displaystyle a_{1}\cdot a_{2}}$ in base ${\displaystyle b}$ is given by the Vedic Square in base ${\displaystyle b}$.
• The digital root of ${\displaystyle a_{1}\cdot a_{2}}$ in base ${\displaystyle b}$ is the digital root of the product of the digital root of ${\displaystyle a_{1}}$ and the digital root of ${\displaystyle a_{2}}$:
${\displaystyle \operatorname {dr} _{b}(a_{1}a_{2})=\operatorname {dr} _{b}(\operatorname {dr} _{b}(a_{1})\cdot \operatorname {dr} _{b}(a_{2})).}$

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 ${\displaystyle b}$. Proof: For a given number ${\displaystyle n}$, the persistence of the number consisting of ${\displaystyle n}$ repetitions of the digit 1 is 1 higher than that of ${\displaystyle 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, ... (sequence A006050 in the OEIS)

The next number in the sequence (the smallest number of additive persistence 5) is 2 × 102×(1022 − 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.[1]

## Programming example

The example below implements the digit sum described in the definition above to search for digital roots and additive persistences in Python.

def digit_sum(x: int, b: int) -> int:
total = 0
while x > 0:
total = total + (x % b)
x = x // b

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

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


## 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.