Fact-checked by Grok 2 weeks ago

Digital sum

The digital sum, also known as the sum-of-digits function, of a positive integer n in base b (where b \geq 2) is the sum of the digits of n when expressed in that base; in the common case of base 10, it is simply the sum of the decimal digits of n. For example, the digital sum of 123 in base 10 is $1 + 2 + 3 = 6. Denoted s_b(n), this function satisfies the key congruence n \equiv s_b(n) \pmod{b-1}, which implies that the digital sum preserves the value of n modulo b-1. In base 10, where b-1 = 9, this property underpins divisibility rules for 3 and 9: a number is divisible by 3 if its digital sum is divisible by 3, and similarly for 9. For instance, since the digital sum of 123 is 6 (divisible by 3), 123 is divisible by 3. The digital sum also relates closely to the digital root, obtained by iteratively applying the digital sum until a single digit remains; the digital root of n (except when n is a multiple of 9, where it is 9) equals n \mod 9. Beyond elementary applications, the digital sum function appears in number theory, including studies of its average value (approximately (b-1)/2 times the number of digits), harmonic series involving digital sums, and problems on digit sums of multiples or polynomials. It has further utility in computational contexts, such as checksum algorithms for error detection in data transmission, where the sum of digits modulo 10 verifies integrity.

Fundamentals

Definition

The digital sum of a positive integer n, often denoted s(n) or s_{10}(n), is the sum of its digits in base 10. Formally, if the decimal expansion of n is given by n = \sum_{k=0}^m d_k 10^k where each digit satisfies $0 \leq d_k \leq 9 and d_m \neq 0, then s(n) = \sum_{k=0}^m d_k. This function is defined for non-negative integers, with the digital sum of zero being 0, as its representation consists of a single digit 0. For example, s(123) = 1 + 2 + 3 = 6 and s(999) = 9 + 9 + 9 = 27. This differs from , which discards lower-order digits (e.g., truncating 123 to 12), or other digit-based operations like counting , as the digital sum aggregates their values additively. The , by contrast, results from repeated applications of the digital sum until a single digit is obtained.

Notation and Terminology

In , the sum of digits of a positive n is commonly denoted by s(n) or S(n), with the lowercase variant often used for the base and generalizations like s_b(n) for base b. In computational and recreational contexts, the abbreviation \mathrm{sod}(n) is sometimes employed for clarity. The primary terminology is "sum of digits," which serves as a for "digital sum," the latter emphasizing the process's relation to the . "Digital sum" specifically denotes a single of the , distinguishing it from the "iterated digital sum," which applies the repeatedly until a single results. In , "digit sum" is a prevalent alternative name, often used in puzzles and popular expositions. To avoid ambiguity with the sum-of-divisors function, conventionally denoted \sigma(n), the digit sum is contextualized by its notation and focus on positional representation rather than divisibility.

Properties

Basic Properties

The digital sum s(n) of a positive integer n with k digits satisfies $1 \leq s(n) \leq 9k, where the lower bound holds for numbers like $10^{k-1} and the upper bound is achieved for numbers consisting entirely of the digit 9, such as $999\ldots9 (k nines). A explicit formula for the digital sum in base 10 is s(n) = n - 9 \sum_{i=1}^{\infty} \left\lfloor \frac{n}{10^i} \right\rfloor, where the infinite sum terminates after a finite number of terms equal to the number of digits in n. The term \sum_{i=1}^{\infty} \left\lfloor \frac{n}{10^i} \right\rfloor, often denoted \phi(n), represents the cumulative excess contributed by higher place values, as each effectively subtracts multiples of 9 from the total compared to the number itself. When incrementing n by 1 to obtain n+1, the digital sum typically increases by 1, so s(n+1) = s(n) + 1, provided no carry-over occurs in the . Carry-over happens when n ends with one or more 9's, causing the sum to decrease: specifically, s(n+1) = s(n) + 1 - 9m, where m is the number of consecutive trailing 9's in n (the of the carry ). For instance, s(9) = 9 but s(10) = 1, a drop of 8; similarly, s([99](/page/99)) = 18 but s(100) = 1, a drop of 17. For the concatenation ab of two positive integers a and b (where b has no leading zeros), the digital sum satisfies s(ab) = s(a) + s(b), as the digits of ab are precisely the digits of a followed by those of b with no overlap or carry between them.

Congruences and Modular Arithmetic

The digital sum s(n) of a positive n satisfies the s(n) \equiv n \pmod{9}. This holds because, in base 10, $10 \equiv 1 \pmod{9}, so $10^k \equiv 1 \pmod{9} for each k, and thus n = \sum d_k 10^k \equiv \sum d_k = s(n) \pmod{9}. As a result, n is divisible by 9 if and only if s(n) is divisible by 9. A special case arises when s(n) = 9: here, n \equiv 0 \pmod{9}, but n \neq 0. For example, with n = 18, s(18) = 1 + 8 = 9, and $18 \div 9 = 2, so $18 \equiv 0 \pmod{9}. Similarly, for n = 19, s(19) = 1 + 9 = 10 and $10 \equiv 1 \pmod{9}, while $19 - 18 = 1, so $19 \equiv 1 \pmod{9}. The congruence extends to modulo 3, since $9 \equiv 0 \pmod{3}; thus, s(n) \equiv n \pmod{3}. Iteratively applying the digital sum until a single digit is reached produces the , which equals n \pmod{9} except when n \equiv 0 \pmod{9}, in which case it is 9 (for n > 0).

Iterative Digital Sum

Digital Root

The of a positive n, denoted \mathrm{dr}(n), is the single-digit value (from 1 to 9) obtained by iteratively summing the s of n until a single results. This value serves as the fixed point of the repeated digital sum process, where the initial step involves computing the sum of the s of n. A for the is given by \mathrm{dr}(n) = n - 9 \left\lfloor \frac{n-1}{9} \right\rfloor, or equivalently, \mathrm{dr}(n) = 1 + (n - 1) \mod 9, with the convention that \mathrm{dr}(9k) = 9 for any positive k \geq 1. These formulas allow direct computation without . The digital root possesses key properties related to : \mathrm{dr}(n) \equiv n \pmod{9}, meaning it preserves the residue class of n modulo 9 (except that multiples of 9 yield 9 rather than 0). Additionally, for single-digit numbers n from 1 to 9, \mathrm{dr}(n) = n. For example, \mathrm{dr}(999) = 9 (since $9+9+9 = 27 and $2+7 = 9), and \mathrm{dr}(1000) = 1.

Additive Persistence

The additive persistence of a positive n, denoted p(n), is defined as the smallest nonnegative k such that the k-fold iterated s^k(n) equals the \mathrm{dr}(n), where s denotes the sum of the base-10 digits. For single-digit numbers (1 through 9), p(n) = 0, as no is needed. For larger n, each application of s reduces the value significantly, typically to at most $9d where d is the number of digits of the current number. A representative example is n = [199](/page/199): s([199](/page/199)) = 1 + 9 + 9 = 19, s(19) = 1 + 9 = 10, s(10) = 1 + 0 = 1, yielding p([199](/page/199)) = 3 and \mathrm{dr}([199](/page/199)) = 1. The process terminates at the digital root, which serves as the fixed point of the . Numbers achieving higher persistence are constructed to maximize the steps, often starting with a leading 1 followed by many 9's to produce a sum that itself has high . The smallest numbers with additive persistence k in base 10 form the sequence A006050 in the OEIS, reflecting the minimal n requiring exactly k iterations. These are 10 (k=1), 19 (k=2), (k=3), and 19999999999999999999999 (a 23-digit number, k=4). The next term for k=5 is a number with over $10^{22} digits, following the recursive construction a(k) = 2 \times 10^{(a(k-1) - 1)/9} - 1 for k > 1. This pattern highlights the relation to minimal numbers for high persistence, where each step builds on the previous to delay reaching a single digit. In general, p(n) = O(\log n), as the number of iterations is bounded above by roughly the number of digits of n plus one, ensuring logarithmic growth with the size of n. Large values of p(n) are rare and occur only for enormous n near certain powers of 10 adjusted with 9's, but there is no fixed upper limit beyond this asymptotic bound; higher persistence is theoretically possible with sufficiently .

Applications

Divisibility Tests

A number n is divisible by 3 if and only if the sum of its digits s(n) is divisible by 3. If s(n) > 9, the process can be repeated recursively on s(n) until a single is reached to simplify the check. Similarly, n is divisible by 9 if and only if s(n) is divisible by 9, or equivalently, if the digital \mathrm{dr}(n) = 9. These rules arise from the property that numbers are congruent to their digit sums 9. For instance, with 123, s(123) = 1 + 2 + 3 = 6, and 6 is divisible by 3, so 123 is divisible by 3 (indeed, $123 \div 3 = 41). For 456, s(456) = 4 + 5 + 6 = 15, then s(15) = 1 + 5 = 6, which is divisible by 3 (so 456 is divisible by 3, as $456 \div 3 = 152) but not by 9 (since 6 is not divisible by 9, and $456 \div 9 = 50.\overline{6}). This approach enables rapid assessment of divisibility for by iteratively shrinking them to small values, facilitating . It has been utilized in practices for centuries. While highly effective for 3 and 9, simple digit-sum tests do not apply to other primes like 7, which instead require more intricate methods such as doubling the last digit and subtracting from the remaining number.

Checksums and Error Detection

Digital sums play a crucial role in algorithms for in identification numbers, where the sum of digits or their weighted variants, taken a small integer like 10 or 11, helps verify against transcription or transmission . These methods leverage the properties of to detect common mistakes, such as single-digit substitutions or adjacent transpositions, without requiring complex computations. By appending a derived from the digital sum, systems ensure that invalid numbers fail the validation sum, providing a simple yet effective layer of in applications like financial and inventory systems. The , developed by scientist and patented in 1960, exemplifies the use of digital sums in validation. Starting from the rightmost digit (excluding the ), every second digit is doubled; if the doubled value exceeds 9, its digits are summed (equivalent to subtracting 9 from the doubled value), and all resulting values are totaled with the undoubled digits. A valid number has a total sum divisible by 10. This process detects all single-digit errors and approximately 98% of adjacent errors, making it suitable for protecting against common input mistakes in payment processing. In book identification, the ISBN-10 format employs a weighted digital sum 11 to compute its , as defined by the (ISO 2108). The first nine digits are multiplied by weights decreasing from 10 to 2 (left to right), summed, and the (0-9 or 'X' for 10) is selected so the total weighted sum, including the weighted by 1, is congruent to 0 11. This scheme detects 100% of single-digit errors and all adjacent transpositions, owing to the prime modulus and consecutive weights ensuring nonzero changes for such errors. For example, the ISBN 0-306-40615-2 yields a weighted sum of $0 \times 10 + 3 \times 9 + 0 \times 8 + 6 \times 7 + 4 \times 6 + 0 \times 5 + 6 \times 4 + 1 \times 3 + 5 \times 2 + 2 \times 1 = 132, and $132 \equiv 0 \pmod{11}, confirming validity. The Universal Product Code (UPC-A) system, introduced in the 1970s and first scanned on June 26, 1974, at a in , incorporates a modulo 10 using a weighted of its 12 digits for detection in retail inventory. Positions are numbered from the left (leftmost as position 1, excluding the ); digits in odd positions (1,3,5,7,9,11) are multiplied by 3, even positions (2,4,6,8,10) by 1, summed; the (position 12, weighted by 1) is chosen so the total weighted is divisible by 10. This detects 100% of single-digit errors, safeguarding against scanning or entry mistakes in high-volume commerce. Although digital sums underpin these practical checksums, their application in modern hash functions is constrained by vulnerability to collisions, where distinct inputs produce identical outputs, undermining integrity checks. Cryptographic hash functions, such as SHA-256, instead use iterative mixing and bitwise operations on larger outputs to achieve negligible collision probabilities, rendering simple digital sums inadequate for secure in contemporary systems.

Extensions and Variations

Generalized Digital Sums

Generalized digital sums extend the basic concept of summing the digits of a number by incorporating weights or multiple applications to capture congruences larger numbers or in non-decimal bases. In particular, weighted digital sums assign coefficients to each digit based on its position, often derived from powers of the base a , to facilitate divisibility tests. For instance, the divisibility rule for 11 in base 10 uses an alternating of digits with weights + and -, since $10 \equiv -1 \pmod{11}, making the weighted congruent to the number itself 11. Similarly, for modulus 7, weights cycle through , 3, 2 (derived from successive powers of 10 7), allowing the weighted to detect divisibility efficiently. In a general base b \geq 2, the unweighted digital sum s_b(n) of a positive n satisfies s_b(n) \equiv n \pmod{[b-1](/page/List_of_punk_rap_artists)}, a property fundamental to many divisibility rules and extensions. This holds because each power of b is congruent to 1 modulo b-1, so n = \sum d_i b^i \equiv \sum d_i \pmod{b-1}. For example, in 16 (), s_{16}(n) \equiv n \pmod{15}, enabling checks for divisibility by factors of 15 using the hex . provide a specific application of this idea: a positive n is a Harshad number in b if n is divisible by s_b(n). The term was introduced by in 1955, derived from for "joy-giver." In 10, 18 is a Harshad number since s_{10}(18) = 1 + 8 = 9 and $18 / 9 = 2. Higher-order digital sums, such as the double digital sum, approximate congruences 99 in base 10 by first summing digits within pairs (leveraging $100 \equiv 1 \pmod{99}) and then summing those results, providing a practical for verifying divisibility by 99 without full computation. This approach generalizes the single sum's utility for 9, extending it to larger moduli while maintaining computational efficiency for larger numbers.

Multibase Digital Sums

The digital sum of a n in base b > 1, denoted s_b(n), is defined as the sum of its digits when n is expressed in the base-b . For instance, the number 10 in base 2 is represented as 1010, yielding s_2(10) = 1 + 0 + 1 + 0 = 2; in base 3, it is 101, so s_3(10) = 1 + 0 + 1 = 2. This generalizes the familiar decimal , where b = 10, to arbitrary bases relevant in computing and . A fundamental property of the base-b digital sum is the congruence s_b(n) \equiv n \pmod{b-1}, which holds because each digit position contributes a multiple of b^k \equiv 1 \pmod{b-1}. Iterating the digital sum process—repeatedly summing the digits until a single digit is obtained—yields the base-b , which equals n \mod (b-1) if this value is nonzero, or b-1 otherwise (except for n = 0). For a k-digit number in base b, the maximum possible digital sum is (b-1)k, achieved when all digits are b-1. In , multibase digital sums find applications in error detection and . Notably, in base 2, the digital sum coincides with the , the count of 1s in the binary representation, which is essential for parity checks, error-correcting codes like Hamming codes, and assessing in digital systems. Similar principles extend to higher bases for computations in non-decimal encodings, leveraging the modular property for efficient validation.