Misplaced Pages

Digital sum in base b

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.
Find sources: "Digital sum in base b" – news · newspapers · books · scholar · JSTOR (July 2024)
This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (December 2009) (Learn how and when to remove this message)
Some of this article's listed sources may not be reliable. Please help improve this article by looking for better, more reliable sources. Unreliable citations may be challenged and removed. (December 2024) (Learn how and when to remove this message)
(Learn how and when to remove this message)

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.

References


Stub icon

This article about a number is a stub. You can help Misplaced Pages by expanding it.

Categories: