Movatterモバイル変換

[0]ホーム

Jump to content

Digital root

Edit links

From Wikipedia, the free encyclopedia

Repeated sum of a number's digits

"Digital roots" redirects here. For the Deltarune Chapter 2 track, seeMusic of Deltarune § Deltarune Chapter 2 OST.

This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(January 2016) (Learn how and when to remove this message)

Thedigital root (alsorepeated digital sum) of anatural number in a givenradix is the (single digit) value obtained by an iterative process ofsumming 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 adivisibility rule.

Formal definition

[edit]

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

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

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

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 $n {\displaystyle n}$ is adigital root if it is afixed point for $F_{b}$ , which occurs if $F_{b}(n)=n$ .

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

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

and therefore

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

because $b>1$ .If $n<b$ , then trivially

F_{b}(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

[edit]

Inbase 12, 8 is the additive digital root of thebase 10 number 3110, as for $n=3110$

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

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

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

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

F_{12}(3110)=\sum _{i=0}^{4-1}d_{i}=2+7+9+1=19

This process shows that 3110 is 1972 inbase 12. Now for $F_{12}(3110)=19$

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

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

F_{12}(19)=\sum _{i=0}^{2-1}d_{i}=1+7=8

shows that 19 is 17 inbase 12. And as 8 is a 1-digit number inbase 12,

F_{12}(8)=8

Direct formulas

[edit]

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

Congruence formula

[edit]

The formula in base $b {\displaystyle b}$ is:

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

\operatorname {dr} _{b}(n)={\begin{cases}0&{\mbox{if}}\ n=0,\\1\ +\ ((n-1){\bmod {(b-1)}})&{\mbox{if}}\ n\neq 0.\end{cases}}

Inbase 10, the corresponding sequence is (sequenceA010888 in theOEIS).

The digital root is the value modulo $(b-1)$ because $b\equiv 1{\pmod {(b-1)}},$ and thus $b^{i}\equiv 1^{i}\equiv 1{\pmod {(b-1)}}.$ So regardless of the position $i {\displaystyle i}$ of digit $d_{i}$ , $d_{i}b^{i}\equiv d_{i}{\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}$ ,

\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 $m {\displaystyle m}$ , one can takeweighted sums, where the weight on the $i {\displaystyle i}$ -th digit corresponds to the value of $b^{i}{\bmod {m}}$ . Inbase 10, this is simplest for $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 $m=b+1$ . Since $b\equiv -1{\pmod {(b+1)}},$ and thus $b^{2}\equiv (-1)^{2}\equiv 1{\pmod {(b+1)}},$ taking thealternating sum of digits yields the value modulo $(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 $b-1$ less than the number itself. For example, inbase 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 {\displaystyle n}$ may be defined by usingfloor function $\lfloor x\rfloor$ , as

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

Properties

[edit]

The digital root of $a_{1}+a_{2}$ in base $b {\displaystyle b}$ is the digital root of the sum of the digital root of $a_{1}$ and the digital root of $a_{2}$ : $\operatorname {dr} _{b}(a_{1}+a_{2})=\operatorname {dr} _{b}(\operatorname {dr} _{b}(a_{1})+\operatorname {dr} _{b}(a_{2})).$ This property can be used as a sort ofchecksum, to check that a sum has been performed correctly.

The digital root of $a_{1}-a_{2}$ in base $b {\displaystyle b}$ is congruent to the difference of the digital root of $a_{1}$ and the digital root of $a_{2}$ modulo $(b-1)$ : $\operatorname {dr} _{b}(a_{1}-a_{2})\equiv (\operatorname {dr} _{b}(a_{1})-\operatorname {dr} _{b}(a_{2})){\pmod {(b-1)}}.$

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

The digital root of the product of nonzero single digit numbers $a_{1}\cdot a_{2}$ in base $b {\displaystyle b}$ is given by theVedic Square in base $b {\displaystyle b}$ .

The digital root of $a_{1}\cdot a_{2}$ in base $b {\displaystyle b}$ is the digital root of the product of the digital root of $a_{1}$ and the digital root of $a_{2}$ : $\operatorname {dr} _{b}(a_{1}a_{2})=\operatorname {dr} _{b}(\operatorname {dr} _{b}(a_{1})\cdot \operatorname {dr} _{b}(a_{2})).$

Additive persistence

[edit]

Theadditive persistence counts how many times we mustsum its digits to arrive at its digital root.

For example, the additive persistence of 2718 inbase 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 {\displaystyle b}$ . Proof: For a given number $n {\displaystyle n}$ , the persistence of the number consisting of $n {\displaystyle n}$ repetitions of the digit 1 is 1 higher than that of $n {\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, ... (sequenceA006050 in theOEIS)

The next number in the sequence (the smallest number of additive persistence 5) is 2 × 10^{2×(10²² − 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 itslogarithm; therefore, the additive persistence is proportional to theiterated 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 inJava.

importjava.util.HashSet;publicclassDigitFunctions{// Sum of digits in base bstaticintdigitSum(intx,intb){inttotal=0;while(x>0){total+=x%b;x/=b;}returntotal;}// Digital root in base bstaticintdigitalRoot(intx,intb){HashSet<Integer>seen=newHashSet<>();while(!seen.contains(x)){seen.add(x);x=digitSum(x,b);}returnx;}// Additive persistence in base bstaticintadditivePersistence(intx,intb){HashSet<Integer>seen=newHashSet<>();while(!seen.contains(x)){seen.add(x);x=digitSum(x,b);}returnseen.size()-1;}// Example usagepublicstaticvoidmain(String[]args){intx=9876;intb=10;System.out.println("Digit Sum: "+digitSum(x,b));System.out.println("Digital Root: "+digitalRoot(x,b));System.out.println("Additive Persistence: "+additivePersistence(x,b));}}

In popular culture

[edit]

Digital roots are used in Westernnumerology, 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 gameNine Hours, Nine Persons, Nine Doors.

References

[edit]

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

Averbach, Bonnie;Chein, Orin (27 May 1999),Problem Solving Through Recreational Mathematics, Dover Books on Mathematics (reprinted ed.), Mineola, NY: Courier Dover Publications, pp. 125–127,ISBN 0-486-40917-1 (online copy, p. 125, atGoogle Books)
Ghannam, Talal (4 January 2011),The Mystery of Numbers: Revealed Through Their Digital Root, CreateSpace Publications, pp. 68–73,ISBN 978-1-4776-7841-1, archived fromthe original on 29 March 2016, retrieved11 February 2016 (online copy, p. 68, atGoogle Books)
Hall, F. M. (1980),An Introduction into Abstract Algebra, vol. 1 (2nd ed.), Cambridge, U.K.: CUP Archive, p. 101,ISBN 978-0-521-29861-2 (online copy, p. 101, atGoogle Books)
O'Beirne, T. H. (13 March 1961), "Puzzles and Paradoxes",New Scientist,10 (230), Reed Business Information:53–54,ISSN 0262-4079 (online copy, p. 53, atGoogle Books)
Rouse Ball, W. W.;Coxeter, H. S. M. (6 May 2010),Mathematical Recreations and Essays, Dover Recreational Mathematics (13th ed.), NY: Dover Publications,ISBN 978-0-486-25357-2 (online copy atGoogle Books)

External links

[edit]

Classes ofnatural numbers

Powers and related numbers
Achilles Power of 2 Power of 3 Power of 10 Square Cube Fourth power Fifth power Sixth power Seventh power Eighth power Perfect power Powerful Prime power

Of the forma × 2^b ± 1
Cullen Double Mersenne Fermat Mersenne Proth Thabit Woodall

Other polynomial numbers
Hilbert Idoneal Leyland Loeschian Lucky numbers of Euler

Recursively defined numbers
Fibonacci Jacobsthal Leonardo Lucas Narayana Padovan Pell Perrin Graham

Possessing a specific set of other numbers
Amenable Congruent Knödel Riesel Sierpiński

Expressible via specific sums
Nonhypotenuse Polite Practical Primary pseudoperfect Ulam Wolstenholme

Figurate numbers

2-dimensional

centered	Centered triangular Centered square Centered pentagonal Centered hexagonal Centered heptagonal Centered octagonal Centered nonagonal Centered decagonal Star
non-centered	Triangular Square Square triangular Pentagonal Hexagonal Heptagonal Octagonal Nonagonal Decagonal Dodecagonal

3-dimensional

centered	Centered tetrahedral Centered cube Centered octahedral Centered dodecahedral Centered icosahedral
non-centered	Tetrahedral Cubic Octahedral Dodecahedral Icosahedral Stella octangula
pyramidal	Square pyramidal

4-dimensional

non-centered	Pentatope Squared triangular Tesseractic

Combinatorial numbers
Bell Cake Catalan Dedekind Delannoy Euler Eulerian Fuss–Catalan Lah Lazy caterer's sequence Lobb Motzkin Narayana Ordered Bell Schröder Schröder–Hipparchus Stirling first Stirling second Telephone number Wedderburn–Etherington

Primes
Wieferich Wall–Sun–Sun Wolstenholme prime Wilson

Pseudoprimes
Carmichael number Catalan pseudoprime Elliptic pseudoprime Euler pseudoprime Euler–Jacobi pseudoprime Fermat pseudoprime Frobenius pseudoprime Lucas pseudoprime Lucas–Carmichael number Perrin pseudoprime Somer–Lucas pseudoprime Strong pseudoprime

Arithmetic functions anddynamics

Divisor functions	Abundant Almost perfect Arithmetic Betrothed Colossally abundant Deficient Descartes Hemiperfect Highly abundant Highly composite Hyperperfect Multiply perfect Perfect Practical Primitive abundant Quasiperfect Refactorable Semiperfect Sublime Superabundant Superior highly composite Superperfect
Prime omega functions	Almost prime Semiprime
Euler's totient function	Highly cototient Highly totient Noncototient Nontotient Perfect totient Sparsely totient
Aliquot sequences	Amicable Perfect Sociable Untouchable
Primorial	Euclid Fortunate

Otherprime factor ordivisor related numbers
Blum Cyclic Erdős–Nicolas Erdős–Woods Friendly Giuga Harmonic divisor Jordan–Pólya Lucas–Carmichael Pronic Regular Rough Smooth Sphenic Størmer Super-Poulet

Numeral system-dependent numbers

Arithmetic functions
anddynamics

Persistence
- Additive
- Multiplicative

Digit sum	Digit sum Digital root Self Sum-product
Digit product	Multiplicative digital root Sum-product
Coding-related	Meertens
Other	Dudeney Factorion Kaprekar Kaprekar's constant Keith Lychrel Narcissistic Perfect digit-to-digit invariant Perfect digital invariant Happy