Digital sum in base b

The digital sum in base b of a set of natural numbers is calculated as follows: express each of the numbers in base b, then take the sum of corresponding digits and discard all carry overs. That is, the digital sum is the same as the normal sum except that no carrying is used.

For example, in decimal (base 10) arithmetic, the digital sum of 123 and 789 is 802:
3 + 9 = 12, discard the 10 leaving 2.
2 + 8 = 10, discard the 10 leaving 0.
1 + 7 = 8, there is no carry to discard.
 123
 789
 ---
 802

More usually the digital sum is calculated in binary (base 2) where the result only depends upon whether there are an even or odd number of 1s in each column. This is the same function as parity or multiple exclusive ors.

For example:
 011 (3)
 100 (4)
 101 (5)
 ---
 010 (2) is the binary digital sum of 3, 4 and 5.

The binary digital sum is crucial for the theory of the game of nim.

The digital sum in base b is an associative and commutative operation on the natural numbers; it has 0 as neutral element and every natural number has an inverse element under this operation. The natural numbers together with the base-b digital sum thus form an abelian group; this group is isomorphic to the direct sum of a countable number of copies of Z/bZ.

Category:Integers