
The digit sum
The sum of the digits of a number in base b has the same remainder as the number modulo b - 1; apart from that it spreads evenly over residue classes, among all numbers and among the primes.
Write a whole number n in base b and add up its digits; call the total s_b(n). In base ten s_10(4731) = 4 + 7 + 3 + 1 = 15. In base two 11 is 1011, so s_2(11) = 3, the number of 1s. In base three 11 is 102, so s_3(11) = 1 + 0 + 2 = 3.
Casting out nines is the first fact about it: n - s_b(n) is a multiple of b - 1, so s_b(n) and n leave the same remainder on division by b - 1, written s_b(n) = n mod (b - 1). The reason is that b = 1 + (b - 1) leaves remainder 1, so every power b^j does, and n = sum d_j b^j leaves the remainder of sum d_j. In base ten, s_10(4731) = 15, adding again gives 1 + 5 = 6, and 4731 = 9 x 525 + 6. In base three the remainder is modulo 2, the parity: s_3(11) = 3 and 11 are both odd. In base eight it is modulo 7: 100 is 144 in base 8, s_8(100) = 9, and 9 and 100 both leave 2 on division by 7. Base two says nothing, because b - 1 = 1.
A modulus that shares a factor with b - 1 therefore teaches nothing new: the class of s_b(n) modulo a divisor g of b - 1 is just the class of n modulo g. In base ten the digit sum is a multiple of 3 exactly when the number is, so no prime but 3 has a digit sum divisible by 3.
The figure plots s_10(n) for n = 0 to 99, one dot a number. Each run of ten climbs by 1 a step, from height k to k + 9, falls back by 8 where the tens digit moves up, and starts one higher than the run before, ending at s_10(99) = 18. Three hairlines mark the heights 0, 9 and 18, the multiples of 9. The 12 multiples of 9 are the yellow dots, and they are exactly the dots on the hairlines, 1, 10 and 1 of them at the three heights. That is casting out nines drawn: a dot's height and its place leave the same remainder on division by 9, so a height that is a multiple of 9 belongs to a multiple of 9 and to nothing else.
Take a modulus m with no common factor with b - 1 and casting out is silent, so the digit sum is free to land in every class. In base 2 with m = 3, the numbers below 64 with j ones number C(6, j), which is 1, 6, 15, 20, 15, 6, 1 for j = 0 to 6, and the classes of j modulo 3 collect 1 + 20 + 1 = 22, 6 + 15 = 21 and 15 + 6 = 21 of them. Nearly a third each.
Gelfond proved in 1968 that this is the rule (Gelfond 1968, stated here as Mauduit and Rivat restate it, the original unread). Fix a base b, a modulus m with no common factor with b - 1, and any arithmetic progression n = l mod k. Among the n < x in the progression, a share 1/m have s_b(n) = a mod m, whatever a is. The digit sum and the progression do not see each other.
Gelfond also asked about the primes. A prime is defined by multiplication and says nothing about how a number is written, so there is no reason to expect it to spread its digit sum evenly, and the question is hard. Mauduit and Rivat 2010 answered yes. For every base q >= 2 and every m with no common factor with q - 1, the number of primes p <= x with s_q(p) = a mod m is (1 + o(1)) pi(x)/m for each a, where pi(x) counts the primes up to x. Their Theorem 3 gives every modulus, and their Theorem 1 is the bound behind it: the exponential sums over the primes, sum e(alpha s_q(p)) weighted by log p, save a power of x whenever (q - 1) alpha is not an integer. At base 2 and m = 3 the 25 primes below 100 have their digit sums in the three classes 9, 8 and 8 times. The condition on m cannot be dropped: in base ten with m = 3 the class of s_10(p) is the class of p, and one class holds only the prime 3.
The proofs run through exponential sums. Write e(t) = e^(2 pi i t). Because (1/m) sum_(r < m) e(r t/m) is 1 when m divides t and 0 otherwise, the number of n < N with s_b(n) = a mod m is (1/m) sum_(r < m) e(-r a/m) sum_(n < N) e(r s_b(n)/m). The term r = 0 is N/m, the fair share, and the rest are the error, so equidistribution says that the sums sum e(alpha s_b(n)) at alpha = r/m, with r not a multiple of m, are small next to N. When m has no common factor with b - 1, (b - 1) r/m is never an integer for such r; when g > 1 is a common factor, r = m/g makes it one. That is the condition of the theorems, seen through the sums.
Over a full block of numbers the sum is a product. A number below b^k is k digits d_j, each from 0 to b - 1 and chosen independently, and e(alpha s_b(n)) = prod_j e(alpha d_j), so sum_(n < b^k) e(alpha s_b(n)) = (1 + e(alpha) + e(2 alpha) + ... + e((b - 1) alpha))^k. At base 2 and k = 3, the numbers 0 to 7 have digit sums 0, 1, 1, 2, 1, 2, 2, 3, so the sum is 1 + 3 e(alpha) + 3 e(2 alpha) + e(3 alpha), which is (1 + e(alpha))^3. The size of that factor is abs(1 + e(alpha)) = 2 abs(cos(pi alpha)). At alpha = 1/2 it is 0 and the sum vanishes: the digit sum is odd as often as even, the Thue-Morse sequence summing to 0 over a block. At alpha = 1/3 it is exactly 1, so (1 + e(1/3))^k has size 1 against 2^k terms. Put that into the count above with m = 3 and N = 64: r = 0 gives 64, r = 1 gives (1 + e(1/3))^6 = 1 and r = 2 gives (1 + e(2/3))^6 = 1, so the classes hold (64 + 1 + 1)/3 = 22, (64 - 1)/3 = 21 and 21, the counts found by hand.
At base 3 and k = 2, the numbers 0 to 8 have digit sums 0, 1, 2, 1, 2, 3, 2, 3, 4, so the sum is 1 + 2 e(alpha) + 3 e(2 alpha) + 2 e(3 alpha) + e(4 alpha) = (1 + e(alpha) + e(2 alpha))^2. At alpha = 1/3 the factor 1 + e(1/3) + e(2/3) is 0, so the sum is 0 at every k and each class modulo 3 holds exactly 3^(k-1) of the first 3^k numbers: 3, 3 and 3 at k = 2. At alpha = 1/2 the factor is 1 - 1 + 1 = 1 and the sum is 1, but this is the case casting out nines predicted: (b - 1) alpha = 1 is an integer, s_3(n) has the parity of n, and e(s_3(p)/2) = -1 at every odd prime, so no sum over the primes can cancel.
The product handles whole blocks n < b^k only. A range that stops at an arbitrary x, a progression, or the primes is the work of the theorems above. Digit sums also count carries: Kummer's theorem reads the power of a prime in a binomial coefficient off s_p(k) + s_p(n - k) - s_p(n).
In the tree
The digit-sum twist on a design asks Gelfond's question of the primes inside a missing-digit set, and carries the product over digits of the last paragraphs onto that set. A Power Saving for the Digit Sum on Missing Digits is the same work written for an outside reader.