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.