Digital root

Let $n$ be a natural number. For base $b\; >\; 1$, we define the digit sum $F\_\{b\}\; :\; \backslash mathbb\{N\}\; \backslash rightarrow\; \backslash mathbb\{N\}$ to be the following:

:$F\_\{b\}(n)\; =\; \backslash sum\_\{i=0\}^\{k\; -\; 1\}\; d\_i$

where $k\; =\; \backslash lfloor\; \backslash log\_\{b\}\{n\}\; \backslash rfloor\; +\; 1$ is the number of digits in the number in base $b$, and

:$d\_i\; =\; \backslash frac\{n\; \backslash bmod\{b^\{i+1\}\}\; -\; n\; \backslash bmod\; b^i\}\{b^i\}$

is the value of each digit of the number. A natural number $n$ is a digital root if it is a fixed point for $F\_\{b\}$, which occurs if $F\_\{b\}(n)\; =\; n$.

All natural numbers $n$ are preperiodic points for $F\_\{b\}$, regardless of the base. This is because if $n\; \backslash geq\; b$, then

:$n\; =\; \backslash sum\_\{i=0\}^\{k\; -\; 1\}\; d\_i\; b^i$

and therefore

:

because $b\; >\; 1$.

If , then trivially

:$F\_\{b\}(n)\; =\; n$

Therefore, the only possible digital roots are the natural numbers , and there are no cycles other than the fixed points of .

In base 12, 8 is the additive digital root of the base 10 number 3110, as for $n\; =\; 3110$

: $d\_0\; =\; \backslash frac\{3110\; \backslash bmod\{12^\{0+1\}\}\; -\; 3110\; \backslash bmod\; 12^0\}\{12^0\}\; =\; \backslash frac\{3110\; \backslash bmod\{12\}\; -\; 3110\; \backslash bmod\; 1\}\{1\}\; =\; \backslash frac\{2\; -\; 0\}\{1\}\; =\; \backslash frac\{2\}\{1\}\; =\; 2$

: $d\_1\; =\; \backslash frac\{3110\; \backslash bmod\{12^\{1+1\}\}\; -\; 3110\; \backslash bmod\; 12^1\}\{12^1\}\; =\; \backslash frac\{3110\; \backslash bmod\{144\}\; -\; 3110\; \backslash bmod\; 12\}\{12\}\; =\; \backslash frac\{86\; -\; 2\}\{12\}\; =\; \backslash frac\{84\}\{12\}\; =\; 7$

: $d\_2\; =\; \backslash frac\{3110\; \backslash bmod\{12^\{2+1\}\}\; -\; 3110\; \backslash bmod\; 12^2\}\{12^2\}\; =\; \backslash frac\{3110\; \backslash bmod\{1728\}\; -\; 3110\; \backslash bmod\; 144\}\{144\}\; =\; \backslash frac\{1382\; -\; 86\}\{144\}\; =\; \backslash frac\{1296\}\{144\}\; =\; 9$

: $d\_3\; =\; \backslash frac\{3110\; \backslash bmod\{12^\{3+1\}\}\; -\; 3110\; \backslash bmod\; 12^3\}\{12^3\}\; =\; \backslash frac\{3110\; \backslash bmod\{20736\}\; -\; 3110\; \backslash bmod\; 1728\}\{1728\}\; =\; \backslash frac\{3110\; -\; 1382\}\{1728\}\; =\; \backslash frac\{1728\}\{1728\}\; =\; 1$

: $F\_\{12\}(3110)\; =\; \backslash sum\_\{i=0\}^\{4\; -\; 1\}\; d\_i\; =\; 2\; +\; 7\; +\; 9\; +\; 1\; =\; 19$

This process shows that 3110 is 1972 in base 12. Now for $F\_\{12\}(3110)\; =\; 19$

: $d\_0\; =\; \backslash frac\{19\; \backslash bmod\{12^\{0+1\}\}\; -\; 19\; \backslash bmod\; 12^0\}\{12^0\}\; =\; \backslash frac\{19\; \backslash bmod\{12\}\; -\; 19\; \backslash bmod\; 1\}\{1\}\; =\; \backslash frac\{7\; -\; 0\}\{1\}\; =\; \backslash frac\{7\}\{1\}\; =\; 7$

: $d\_1\; =\; \backslash frac\{19\; \backslash bmod\{12^\{1+1\}\}\; -\; 19\; \backslash bmod\; 12^1\}\{12^1\}\; =\; \backslash frac\{19\; \backslash bmod\{144\}\; -\; 19\; \backslash bmod\; 12\}\{12\}\; =\; \backslash frac\{19\; -\; 7\}\{12\}\; =\; \backslash frac\{12\}\{12\}\; =\; 1$

: $F\_\{12\}(19)\; =\; \backslash 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,

: $F\_\{12\}(8)\; =\; 8$.

We can define the digit root directly for base $b\; >\; 1$ $\backslash operatorname\{dr\}\_\{b\}\; :\; \backslash mathbb\{N\}\; \backslash rightarrow\; \backslash mathbb\{N\}$ in the following ways:

The formula in base $b$ is:

:$\backslash 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,

:$\backslash 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 {{OEIS|id=A010888}}.

The digital root is the value modulo $(b\; -\; 1)$ because $b\; \backslash equiv\; 1\; \backslash pmod\{(b\; -\; 1)\},$ and thus $b^i\; \backslash equiv\; 1^i\; \backslash equiv\; 1\; \backslash pmod\{(b\; -\; 1)\}.$ So regardless of the position $i$ of digit $d\_i$, $d\_i\; b^i\backslash equiv\; d\_i\; \backslash pmod\{(b-1)\}$, which explains why digits can be meaningfully added. Concretely, for a three-digit number $n\; =\; d\_2\; b^2\; +\; d\_1\; b^1\; +\; d\_0\; b^0$,

:$\backslash operatorname\{dr\}\_\{b\}(n)\; \backslash equiv\; d\_2\; b^2\; +\; d\_1\; b^1\; +\; d\_0\; b^0\; \backslash equiv\; d\_2\; (1)\; +\; d\_1\; (1)\; +\; d\_0\; (1)\; \backslash equiv\; d\_2\; +\; d\_1\; +\; d\_0\; \backslash pmod\{(b\; -\; 1)\}.$

To obtain the modular value with respect to other numbers $m$, one can take weighted sums, where the weight on the $i$-th digit corresponds to the value of $b^i\; \backslash bmod\{m\}$. In base 10, this is simplest for $m=2,\; 5,\backslash 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 $m\; =\; b\; +\; 1$. Since $b\; \backslash equiv\; -1\; \backslash pmod\{(b\; +\; 1)\},$ and thus $b^2\; \backslash equiv\; (-1)^2\; \backslash equiv\; 1\; \backslash pmod\{(b\; +\; 1)\},$ taking the alternating sum of digits yields the value modulo $(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 $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 $6\; -\; 1\; =\; 5$. Likewise, in base 10 the digital root of 2035 is 1, which means that $2035\; -\; 1\; =\; 2034|9$. If a number produces a digital root of exactly $b\; -\; 1$, then the number is a multiple of $b\; -\; 1$.

With this in mind the digital root of a positive integer $n$ may be defined by using floor function $\backslash lfloor\; x\backslash rfloor$, as

:$\backslash operatorname\{dr\}\_\{b\}(n)=n-(b\; -\; 1)\backslash left\backslash lfloor\backslash frac\{n-1\}\{b\; -\; 1\}\backslash right\backslash rfloor.$

• The digital root of $a\_1\; +\; a\_2$ in base $b$ is the digital root of the sum of the digital root of $a\_1$ and the digital root of $a\_2$: $$\backslash operatorname\{dr\}\_\{b\}(a\_1\; +\; a\_2)\; =\; \backslash operatorname\{dr\}\_\{b\}(\backslash operatorname\{dr\}\_\{b\}(a\_1)+\backslash operatorname\{dr\}\_\{b\}(a\_2)).$$ This property can be used as a sort of checksum, to check that a sum has been performed correctly.

• The digital root of $a\_1\; -\; a\_2$ in base $b$ is congruent to the difference of the digital root of $a\_1$ and the digital root of $a\_2$ modulo $(b\; -\; 1)$: $$\backslash operatorname\{dr\}\_\{b\}(a\_1\; -\; a\_2)\; \backslash equiv\; (\backslash operatorname\{dr\}\_\{b\}(a\_1)-\backslash operatorname\{dr\}\_\{b\}(a\_2))\; \backslash pmod\{(b\; -\; 1)\}.$$

• The digital root of $-n$ in base $b$ is $$\backslash operatorname\{dr\}\_\{b\}(-n)\; \backslash equiv\; -\backslash operatorname\{dr\}\_\{b\}(n)\; \backslash bmod\{b\; -\; 1\}.$$

• The digital root of the product of nonzero single digit numbers $a\_1\; \backslash cdot\; a\_2$ in base $b$ is given by the Vedic Square in base $b$.

• The digital root of $a\_1\; \backslash cdot\; a\_2$ in base $b$ is the digital root of the product of the digital root of $a\_1$ and the digital root of $a\_2$: $$\backslash operatorname\{dr\}\_\{b\}(a\_1\; a\_2)\; =\; \backslash operatorname\{dr\}\_\{b\}(\backslash operatorname\{dr\}\_\{b\}(a\_1)\backslash cdot\backslash operatorname\{dr\}\_\{b\}(a\_2)\; ).$$

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 $b$. Proof: For a given number $n$, the persistence of the number consisting of $n$ repetitions of the digit 1 is 1 higher than that of $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, ... {{OEIS|A006050}}

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.{{citation |last=Meimaris | first=Antonios | title=On the additive persistence of a number in base p| publisher=Preprint | year=2015| url=https://www.academia.edu/11654065}}

The example below implements the digit sum described in the definition above to search for digital roots and additive persistences in Python.

def digit_sum(x: int, b: int) -> int:

total = 0

while x > 0:

total = total + (x % b)

x = x // b

return total

def digital_root(x: int, b: int) -> int:

seen = set()

while x not in seen:

seen.add(x)

x = digit_sum(x, b)

return x

def additive_persistence(x: int, b: int) -> int:

seen = set()

while x not in seen:

seen.add(x)

x = digit_sum(x, b)

return len(seen) - 1

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.

{{Div col}}

• Arithmetic dynamics
• Base 9
• Casting out nines
• Digit sum
• Divisibility rule
• Hamming weight
• Multiplicative digital root

{{Div col end}}

{{reflist}}

• {{Citation|last1=Averbach|first1=Bonnie|author1-link=Bonnie Averbach|last2=Chein|first2=Orin|author2-link=Orin Chein|date=27 May 1999|title=Problem Solving Through Recreational Mathematics|title-link=Problem Solving Through Recreational Mathematics|publisher=Courier Dover Publications|location=Mineola, NY|edition=reprinted|series=Dover Books on Mathematics|isbn=0-486-40917-1|pages=[https://archive.org/details/isbn_9780486409177/page/125 125–127]}} ({{Google books|qtMoAwAAQBAJ|online copy|page=125}})
• {{Citation|last=Ghannam|first=Talal|author-link=Talal Ghannam|date=4 January 2011|title=The Mystery of Numbers: Revealed Through Their Digital Root|publisher=CreateSpace Publications|isbn=978-1-4776-7841-1|url=https://www.createspace.com/3529186|pages=68–73|access-date=11 February 2016|archive-url=https://web.archive.org/web/20160329004316/https://www.createspace.com/3529186|archive-date=29 March 2016|url-status=dead}} ({{Google books|PN4dzi8eoZQC|online copy|page=68}})
• {{Citation|last=Hall|first=F. M.|author-link=Frederick Michael Hall|year=1980|title=An Introduction into Abstract Algebra|publisher=CUP Archive|location=Cambridge, U.K.|edition=2nd|volume=1|isbn=978-0-521-29861-2|page=101}} ({{Google books|qqs8AAAAIAAJ|online copy|page=101}})
• {{Citation|last=O'Beirne|first=T. H.|author-link=T. H. O'Beirne|date=13 March 1961|title=Puzzles and Paradoxes|journal=New Scientist|publisher=Reed Business Information|volume=10|issue=230|issn=0262-4079|pages=53–54}} ({{Google books|j4VdAP43V7cC|online copy|page=53}})
• {{Citation|last1=Rouse Ball|first1=W. W.|author1-link=Walter William Rouse Ball|last2=Coxeter|first2=H. S. M.|author2-link=Harold Scott Macdonald Coxeter|date=6 May 2010|title=Mathematical Recreations and Essays|publisher=Dover Publications|location=NY|edition=13th|series=Dover Recreational Mathematics|isbn=978-0-486-25357-2}} ({{Google books|9lJqNJhYc9oC|online copy}})

• [http://people.revoledu.com/kardi/tutorial/DigitSum/index.html Patterns of digital roots using MS Excel]
• {{MathWorld|title=Digital Root|id=DigitalRoot}}

{{Classes of natural numbers}}

Category:Algebra

Category:Arithmetic dynamics

Category:Base-dependent integer sequences

Category:Number theory

de:Quersumme#Einstellige (oder iterierte) Quersumme