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. The formula for the function ${\displaystyle \mathrm {dr} _{b}:\mathbb {N} \rightarrow \mathop {\bigcup } _{k=0}^{b-1}\{k\},\quad b\in \mathbb {N} _{\geqslant 2}}$ is expressed as:

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

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<b}$, then trivially

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

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

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}$.

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:

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)}$.

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 .}$

Let ${\displaystyle b\geq 2}$ and let ${\displaystyle \operatorname {dr} _{b}(n)}$ denote the digital root of ${\displaystyle n}$ in base ${\displaystyle b}$. Then:

• Idempotence

${\displaystyle \operatorname {dr} _{b}(\operatorname {dr} _{b}(n))=\operatorname {dr} _{b}(n).}$

Since the digital root is a single digit (i.e. ${\displaystyle 0\leq \operatorname {dr} _{b}(n)<b}$), applying the digit-sum process again leaves it unchanged.

• Compatibility with addition

${\displaystyle \operatorname {dr} _{b}(a+c)=\operatorname {dr} _{b}(\operatorname {dr} _{b}(a)+\operatorname {dr} _{b}(c)).}$

This follows from the congruence

${\displaystyle a\equiv \operatorname {dr} _{b}(a),\quad c\equiv \operatorname {dr} _{b}(c){\pmod {b-1}}.}$

• Compatibility with subtraction

${\displaystyle \operatorname {dr} _{b}(a-c)\equiv \operatorname {dr} _{b}(a)-\operatorname {dr} _{b}(c){\pmod {b-1}}.}$

In particular, after applying ${\displaystyle \operatorname {dr} _{b}}$ to the result, subtraction is preserved up to reduction modulo ${\displaystyle b-1}$.

• Compatibility with multiplication

${\displaystyle \operatorname {dr} _{b}(ac)=\operatorname {dr} _{b}(\operatorname {dr} _{b}(a)\cdot \operatorname {dr} _{b}(c)).}$

This is a consequence of multiplicative compatibility modulo ${\displaystyle b-1}$.

• Compatibility with exponentiation

${\displaystyle \operatorname {dr} _{b}(a^{k})=\operatorname {dr} _{b}(\operatorname {dr} _{b}(a)^{k}).}$

This follows from

${\displaystyle a\equiv \operatorname {dr} _{b}(a){\pmod {b-1}}}$,

so

${\displaystyle a^{k}\equiv \operatorname {dr} _{b}(a)^{k}{\pmod {b-1}}.}$

These properties show that the digital root behaves like reduction modulo ${\displaystyle b-1}$, followed by mapping the residue ${\displaystyle 0}$ to ${\displaystyle b-1}$.

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 × 10^{2×(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.¹

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<Integer> 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<Integer> 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));
    }
}

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.