digital root
   HOME

TheInfoList



OR:

The digital root (also repeated digital sum) of a
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
in a given
radix In a positional numeral system, the radix (radices) or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal system (the most common system in use today) the radix is ten, becaus ...
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 A divisibility rule is a shorthand and useful way of determining whether a given integer is divisible by a fixed Divisor (number theory), divisor without performing the division, usually by examining its digits. Although there are divisibility test ...
.


Formal definition

Let n be a natural number. For base b > 1, we define the
digit sum In mathematics, the digit sum of a natural number in a given radix, number base is the sum of all its numerical digit, digits. For example, the digit sum of the decimal number 9045 would be 9 + 0 + 4 + 5 = 18. Definition Let n be a natural number. ...
F_ : \mathbb \rightarrow \mathbb to be the following: :F_(n) = \sum_^ d_i where k = \lfloor \log_ \rfloor + 1 is the number of digits in the number in base b, and :d_i = \frac 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_, which occurs if F_(n) = n. All natural numbers n are preperiodic points for F_, regardless of the base. This is because if n \geq b, then :n = \sum_^ d_i b^i and therefore :F_(n) = \sum_^ d_i < \sum_^ d_i b^i = n because b > 1. If n < b, then trivially :F_(n) = n Therefore, the only possible digital roots are the natural numbers 0 \leq n < b, and there are no cycles other than the fixed points of 0 \leq n < b.


Example

In base 12, 8 is the additive digital root of the
base 10 The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers (''decimal fractions'') of t ...
number 3110, as for n = 3110 : d_0 = \frac = \frac = \frac = \frac = 2 : d_1 = \frac = \frac = \frac = \frac = 7 : d_2 = \frac = \frac = \frac = \frac = 9 : d_3 = \frac = \frac = \frac = \frac = 1 : F_(3110) = \sum_^ d_i = 2 + 7 + 9 + 1 = 19 This process shows that 3110 is 1972 in base 12. Now for F_(3110) = 19 : d_0 = \frac = \frac = \frac = \frac = 7 : d_1 = \frac = \frac = \frac = \frac = 1 : F_(19) = \sum_^ 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_(8) = 8.


Direct formulas

We can define the digit root directly for base b > 1 \operatorname_ : \mathbb \rightarrow \mathbb in the following ways:


Congruence formula

The formula in base b is: : \operatorname_(n) = \begin 0 & \mbox\ n = 0, \\ b - 1 & \mbox\ n \neq 0,\ n\ \equiv 0 \pmod,\\ n \bmod & \mbox\ n \not\equiv 0 \pmod \end or, : \operatorname_(n) = \begin 0 & \mbox\ n = 0, \\ 1\ +\ ((n-1) \bmod) & \mbox\ n \neq 0. \end In
base 10 The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers (''decimal fractions'') of t ...
, the corresponding sequence is . The digital root is the value modulo (b - 1) because b \equiv 1 \pmod, and thus b^i \equiv 1^i \equiv 1 \pmod. So regardless of the position i of digit d_i, d_i b^i\equiv d_i \pmod, 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, :\operatorname_(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. 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 \bmod. In
base 10 The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers (''decimal fractions'') of t ...
, this is simplest for m=2, 5,\text10, 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 \equiv -1 \pmod, and thus b^2 \equiv (-1)^2 \equiv 1 \pmod, taking the ''alternating'' sum of digits yields the value modulo (b + 1).


Using the floor function

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 In mathematics, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least integer greater than or eq ...
\lfloor x\rfloor , as :\operatorname_(n)=n-(b - 1)\left\lfloor\frac\right\rfloor.


Properties

* 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: \operatorname_(a_1 + a_2) = \operatorname_(\operatorname_(a_1)+\operatorname_(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): \operatorname_(a_1 - a_2) \equiv (\operatorname_(a_1)-\operatorname_(a_2)) \pmod. * The digital root of -n in base b is \operatorname_(-n) \equiv -\operatorname_(n) \bmod. * The digital root of the product of nonzero single digit numbers a_1 \cdot a_2 in base b is given by the Vedic Square in base b. * The digital root of a_1 \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: \operatorname_(a_1 a_2) = \operatorname_(\operatorname_(a_1)\cdot\operatorname_(a_2) ).


Additive persistence

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 The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers (''decimal fractions'') of t ...
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, ... 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 In mathematics, the logarithm of a number is the exponent by which another fixed value, the base, must be raised to produce that number. For example, the logarithm of to base is , because is to the rd power: . More generally, if , the ...
; therefore, the additive persistence is proportional to the iterated logarithm.


Programming example

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


In popular culture

Digital roots are used in Western
numerology Numerology (known before the 20th century as arithmancy) is the belief in an occult, divine or mystical relationship between a number and one or more coinciding events. It is also the study of the numerical value, via an alphanumeric system, ...
, 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''.


See also

*
Arithmetic dynamics Arithmetic dynamics is a field that amalgamates two areas of mathematics, dynamical systems and number theory. Part of the inspiration comes from complex dynamics, the study of the Iterated function, iteration of self-maps of the complex plane or o ...
* Base 9 * Casting out nines *
Digit sum In mathematics, the digit sum of a natural number in a given radix, number base is the sum of all its numerical digit, digits. For example, the digit sum of the decimal number 9045 would be 9 + 0 + 4 + 5 = 18. Definition Let n be a natural number. ...
*
Divisibility rule A divisibility rule is a shorthand and useful way of determining whether a given integer is divisible by a fixed Divisor (number theory), divisor without performing the division, usually by examining its digits. Although there are divisibility test ...
*
Hamming weight The Hamming weight of a string (computer science), string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the mo ...
* Multiplicative digital root


References

* () * () * () * () * ()


External links


Patterns of digital roots using MS Excel
* {{Classes of natural numbers Algebra Arithmetic dynamics Base-dependent integer sequences Number theory de:Quersumme#Einstellige (oder iterierte) Quersumme