Digital root

O(log n) per pass

The digital root of a number is found by summing its digits over and over until only one digit is left. For example, 493 → 16 → 7. It turns out the result always equals n mod 9 (with 9 replacing 0 for multiples of 9), so the process is really a dramatic demonstration of that modular identity. The digital root has ancient roots in "casting out nines" — a mental arithmetic trick for spotting arithmetic errors. Each step in the visualizer replaces the current number with its digit sum, so you can watch it collapse down to a single digit.

Sequence
Press ▶ to run
Edit the input and press Play

How it works

  1. Write out n.
  2. Sum all of n's decimal digits to get a new number.
  3. Repeat if the result still has more than one digit.
  4. Stop — the final single-digit number is the digital root.

Pseudocode

1digitalRoot(n):                     # O(log n) per pass2  while n ≥ 10:3    n ← sum of decimal digits of n4    emit n5  # n is now the digital root