en.wikipedia.org

Digital root - Wikipedia

From Wikipedia, the free encyclopedia

The digital root (also repeated digital sum) of a natural number in a given radix is the (single digit) value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached. For example, in base 10, the digital root of the number 12345 is 6 because the sum of the digits in the number is 1 + 2 + 3 + 4 + 5 = 15, then the addition process is repeated again for the resulting number 15, so that the sum of 1 + 5 equals 6, which is the digital root of that number. In base 10, this is equivalent to taking the remainder upon division by 9 (except when the digital root is 9, where the remainder upon division by 9 will be 0), which allows it to be used as a divisibility rule.

Let {\displaystyle n} be a natural number. For base {\displaystyle b>1}, we define the digit sum {\displaystyle F_{b}:\mathbb {N} \rightarrow \mathbb {N} } to be the following:

{\displaystyle F_{b}(n)=\sum _{i=0}^{k-1}d_{i}}

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

{\displaystyle d_{i}={\frac {n{\bmod {b^{i+1}}}-n{\bmod {b}}^{i}}{b^{i}}}}

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

All natural numbers {\displaystyle n} are preperiodic points for {\displaystyle F_{b}}, regardless of the base. This is because if {\displaystyle n\geq b}, then

{\displaystyle n=\sum _{i=0}^{k-1}d_{i}b^{i}}

and therefore

{\displaystyle F_{b}(n)=\sum _{i=0}^{k-1}d_{i}<\sum _{i=0}^{k-1}d_{i}b^{i}=n}

because {\displaystyle b>1}. If {\displaystyle n<b}, then trivially

{\displaystyle F_{b}(n)=n}

Therefore, the only possible digital roots are the natural numbers {\displaystyle 0\leq n<b}, and there are no cycles other than the fixed points of {\displaystyle 0\leq n<b}.

In base 12, 8 is the additive digital root of the base 10 number 3110, as for {\displaystyle n=3110}

{\displaystyle d_{0}={\frac {3110{\bmod {12^{0+1}}}-3110{\bmod {1}}2^{0}}{12^{0}}}={\frac {3110{\bmod {12}}-3110{\bmod {1}}}{1}}={\frac {2-0}{1}}={\frac {2}{1}}=2}
{\displaystyle d_{1}={\frac {3110{\bmod {12^{1+1}}}-3110{\bmod {1}}2^{1}}{12^{1}}}={\frac {3110{\bmod {144}}-3110{\bmod {1}}2}{12}}={\frac {86-2}{12}}={\frac {84}{12}}=7}
{\displaystyle d_{2}={\frac {3110{\bmod {12^{2+1}}}-3110{\bmod {1}}2^{2}}{12^{2}}}={\frac {3110{\bmod {1728}}-3110{\bmod {1}}44}{144}}={\frac {1382-86}{144}}={\frac {1296}{144}}=9}
{\displaystyle d_{3}={\frac {3110{\bmod {12^{3+1}}}-3110{\bmod {1}}2^{3}}{12^{3}}}={\frac {3110{\bmod {20736}}-3110{\bmod {1}}728}{1728}}={\frac {3110-1382}{1728}}={\frac {1728}{1728}}=1}
{\displaystyle F_{12}(3110)=\sum _{i=0}^{4-1}d_{i}=2+7+9+1=19}

This process shows that 3110 is 1972 in base 12. Now for {\displaystyle F_{12}(3110)=19}

{\displaystyle d_{0}={\frac {19{\bmod {12^{0+1}}}-19{\bmod {1}}2^{0}}{12^{0}}}={\frac {19{\bmod {12}}-19{\bmod {1}}}{1}}={\frac {7-0}{1}}={\frac {7}{1}}=7}
{\displaystyle d_{1}={\frac {19{\bmod {12^{1+1}}}-19{\bmod {1}}2^{1}}{12^{1}}}={\frac {19{\bmod {144}}-19{\bmod {1}}2}{12}}={\frac {19-7}{12}}={\frac {12}{12}}=1}
{\displaystyle F_{12}(19)=\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,

{\displaystyle F_{12}(8)=8}.

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

The formula in base {\displaystyle b} is:

{\displaystyle \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,

{\displaystyle \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 (sequence A010888 in the OEIS).

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

{\displaystyle \operatorname {dr} _{b}(n)\equiv d_{2}b^{2}+d_{1}b^{1}+d_{0}b^{0}\equiv d_{2}(1)+d_{1}(1)+d_{0}(1)\equiv d_{2}+d_{1}+d_{0}{\pmod {(b-1)}}.}

To obtain the modular value with respect to other numbers {\displaystyle m}, one can take weighted sums, where the weight on the {\displaystyle i}-th digit corresponds to the value of {\displaystyle b^{i}{\bmod {m}}}. In base 10, this is simplest for {\displaystyle m=2,5,{\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 {\displaystyle m=b+1}. Since {\displaystyle b\equiv -1{\pmod {(b+1)}},} and thus {\displaystyle b^{2}\equiv (-1)^{2}\equiv 1{\pmod {(b+1)}},} taking the alternating sum of digits yields the value modulo {\displaystyle (b+1)}.

Using the floor function

[edit]

It helps to see the digital root of a positive integer as the position it holds with respect to the largest multiple of {\displaystyle 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 {\displaystyle 6-1=5}. Likewise, in base 10 the digital root of 2035 is 1, which means that {\displaystyle 2035-1=2034|9}. If a number produces a digital root of exactly {\displaystyle b-1}, then the number is a multiple of {\displaystyle b-1}.

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

{\displaystyle \operatorname {dr} _{b}(n)=n-(b-1)\left\lfloor {\frac {n-1}{b-1}}\right\rfloor .}

Additive persistence

[edit]

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

The next number in the sequence (the smallest number of additive persistence 5) is 2 × 102×(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.[1]

Programming example

[edit]

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.

  1. ^ Meimaris, Antonios (2015), On the additive persistence of a number in base p, Preprint