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

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

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

We can define the digital root recursively:

(1)

## 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: . If , we extract digits from the right to the left by successively dividing with 10 and taking the remainder. Afterward, we apply *digital_root* to their sum.

### 3.1. Complexity

Since has digits, the maximal sum of its digits is .

Therefore, in the second call to digital_root, we sum at most digits. That’s the asymptotic worst case of the maximal number of divisions and mod operations in the second call.

Let . Then, **the complexity of the -th call is .**

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

(2)

where is the iterated logarithm.

Since , we have:

Consequently, dominates the sum (2). As a result, **this method has a logarithmic time complexity.**

## 4. The *O(1)* Solution

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 directly:

For example, , which is what we get with our recursive algorithm.

Why does this work? Well, since , we have that for any number it holds that:

Let be the sum of the digits of . The above relation says that .

However, the same holds for the sum, so . Continuing the chain, we eventually reach the single-digit number , i.e., the digital root . As a result, ** is congruent with modulo 9.**

## 5. Conclusion

In this article, we showed two ways to calculate the digital root of an integer.