Finding the Digital Root | Baeldung on Computer Science

1. Introduction

In this tutorial, we’ll show how to find the digital root of an integer number. We get it by repeatedly taking the sum of the integer’s digits until there’s only one.

We can use the digital root to check the correctness of addition, subtraction, and multiplication.

2. Digital Root

Let’s say our number is 1654. By summing its digits, we get:

$1 + 6 + 5 + 4 = 16$

Since the sum 16 has more than one digit, we add its digits together:

$1 + 6 = 7$

Now, we have a single-digit number, so 7 is the digital root of 1654.

We can define the digital root recursively:

(1) $\begin{equation*} dr(n) = \begin{cases} n,& n < 10 \\ \text{the sum of the digits of } dr(n),& n \geq 10 \end{cases} \end{equation*}$

3. Pseudocode

Here’s a straightforward way of computing digital roots:

algorithm digitalRoot(n):
    // INPUT
    //    n - the number to map to a single digit
    // OUTPUT
    //    the digital root of n

    if n < 10:
        return n
    else:
        sum <- 0
        while n > 0:
            digit <- n mod 10
            n <- n div 10
            sum <- sum + digit
        return digitalRoot(sum)

The base case is as in the definition: $n < 10$ . If $n \geq 10$ , we extract digits from the right to the left by successively dividing $n$ with 10 and taking the remainder. Afterward, we apply digital_root to their sum.

3.1. Complexity

Since $n$ has $\lceil \log_{10} n \rceil$ digits, the maximal sum of its digits is $9 \lceil \log_{10} n \rceil \in O(\log n)$ .

Therefore, in the second call to digital_root, we sum at most $\lceil \log_{10} \left( 9 \lceil\log_{10} n \rceil \right) \rceil \in O(\log \log n)$ digits. That’s the asymptotic worst case of the maximal number of divisions and mod operations in the second call.

Let $\log^k n = \underbrace{\log \log \ldots \log}_{k\text{ times}} n$ . Then, the complexity of the $\boldsymbol{k}$ -th call is $\boldsymbol{O \left( \log^k n \right)}$ .

Taking all the calls into account, we get the overall complexity of:

(2) $\begin{equation*} \sum_{k=1}^{\log^* n} O(\log^k n) = O \left( \sum_{k=1}^{\log^* n} \log^k n \right) \end{equation*}$

where $\log^*$ is the iterated logarithm.

Since $\log n \in O(n)$ , we have:

$\log^{k+1} n \in O \left( \log^k n \right) \quad \forall k \geq 1$

Consequently, $\log n$ dominates the sum (2). As a result, this method has a logarithmic time complexity.

4. The O(1) Solution

$O(\log n)$ is pretty fast, but we can do even better in terms of the number of divisions and mods.

There’s a neat formula we can use to compute $dr(n)$ directly:

$dr(n) = \begin{cases} 0,& n = 0 \\ 9, & n \bmod 9 = 0 \\ n \bmod 9,& otherwise \end{cases}$

For example, $dr(1654) = 1654 \bmod 9 = 7$ , which is what we get with our recursive algorithm.

Why does this work? Well, since $10 \equiv 1 \pmod 9$ , we have that for any number $a_{n}a_{n-1}\ldots a_1 a_0$ it holds that:

$\sum_{i=0}^{n} a_i \times 10^i \equiv \sum_{i=0}^{n} a_i \pmod 9$

Let $s(n)$ be the sum of the digits of $n$ . The above relation says that $n \bmod 9 = s(n) \bmod 9$ .

However, the same holds for the sum, so $s(n) \bmod 9 = s(s(n)) \bmod 9$ . Continuing the chain, we eventually reach the single-digit number $s(s(\ldots s(n) \ldots ))$ , i.e., the digital root $dr(n)$ . As a result, $\boldsymbol{dr(n)}$ is congruent with $\boldsymbol{n}$ modulo 9.