View Single Post
Old 2021-07-20, 15:34   #1
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

23·223 Posts
Default A real thread about digit sums

Here, [x] is the integer floor of x, n is a positive integer, and b is an integer greater than or equal to 2. The base-b digits of n can be computed by repeated integer division with quotient and remainder:

n = b*[n/b] + d0,

[n/b] = b*[n/b2] + d1

[n/b2] = b*[n/b3] + d2

etc

where 0 <= dk <= b-1

For a given n, this process terminates in a finite number of steps, the number of steps being about log(n)/log(b).

Then we have n = d0 + d1*b + d2*b2 + ...

Note: The fact that [n/b2] = [[n/b]/b] etc is left as an exercise for the reader.

Adding the two sets of equations, we have

n + [n/b] + [n/b2] + ... = b*([n/b] + n/b2] + ...) + d0 + d1 + ...

n - (d0 + d1 + ...) = (b-1)*([n/b] + [n/b2] + ...)

When b = ten, this relation makes explicit that n differs from the sum of its decimal digits by a multiple of 9 (it gives the multiplier). This fact is the basis for the long-used process of "casting out nines," which was used to check arithmetic operations by (in effect) checking them modulo 9. If we used base three, we could check arithmetic operations by "casting out twos."

It is not hard to show another formulation of the base-b generalization of "casting out nines." If m and n are positive integers, the sum of the base-b digits of m plus the sum of the base-b digits of n, minus the sum of the base-b digits of (m + n), is (b-1) times the number of carries in the addition.

When the base b = p, a prime number, the sum [n/p] + [n/p2] + ... is the exponent of the p-power factor of n! (factorial n).

Combining the previous observations, we can deduce that if p is a prime number, then the power of p which divides the binomial coefficient m+n choose m (or m+n choose n) is the number of carries in the base-p addition m + n. In particular, when m > 0, n > 0, and m+n is a power of p, there is always at least one carry in the base-p addition m + n. So pk choose m is divisible by p if 0 < m < pk.

Another sort of question about digit sums is, the distribution of values among numbers with a given number of base-b digits. There are b-1 base-b integers with 1 base-b digit; b*(b-1) with two, b2*(b-1) with three, and so on. It is easily shown by induction that the average digit sum of k-digit numbers to the base b is

k*(b-1)/2 + 1/2.

There is a formula of sorts for the number of blocks of k base-b digits with a given sum n. Namely, the coefficient of xn in

\(\sum_{i=0}^{b-1}x^i\)^{k}

The block of k 0's corresponds to the term 1, and the block of k b-1's to x(b-1)*k. One can use this formula for k-1 digits, and prepend with the digits 1 to b-1, for positive integers with k base-b digits.

When b = 2, we get the binomial coefficients. We would thus expect the sum of binary digits of k-digit numbers to base 2 to be strongly concentrated areound the average.

From looking around online, it seems that something similar happens with digit sums of k-digit numbers to any base.

As to digit sums of primes greater than the base b, the final base-b digit must be relativley prime to b, and the digit sum itself must be relatively prime to b-1. In particular, for base ten, the ones digit of a prime greater than ten can only be 1, 3, 7, or 9; and the digit sum can not be divisible by 3.

Apart from that, I would guess that the digit sums of primes with a given number of decimal digits are probably concentrated around the average.

Last fiddled with by Dr Sardonicus on 2021-07-23 at 12:59 Reason: xingif posty;reformat exponents
Dr Sardonicus is offline   Reply With Quote