ENIGMA 1561 — Some check!
by Bob Walker
Checksums have been used for years to check the accuracy of calculations.
To calculate the checksum of a number you add up its digits.
If that total is a single digit then that is the checksum;
if not, the digits in the total are added to produce a new total, and the process is repeated
until a single-digit answer is produced.
That single digit is the original number’s checksum.
What is the checksum of the number (2100 + 3200)300 ?
There are two steps to the solution, firstly to prove a vital property about checksums, and them to use it to get the solution.
Let us write the check sum of a positive integer (i.e. not zero)
n as cs(n).
We wish to show that:
cs(n + m) = cs(n) + cs(m)
Let us first consider the case where
m has only one non−zero digit, (e.g. 1, 5, 6, 9, 70, 700, 500, 400000),
and denote the sum of all the digits in
n by Σ n.
The check sum
cs(n) is achieved by doing first
Σ n and then Σ Σ n and then Σ Σ Σ n, etc,
stopping when the answer is just a single digit,
which can never be zero.
Of course:
cs(n) = cs(Σ n)
The sum of all the digits in
n + m :
Σ(n + m) = Σ n + m if no carry occurs
Σ(n + m) = Σ n + m − 9 if carry occurs once
Σ(n + m) = Σ n + m − 18 if carry occurs twice
etc
If we can show that subtracting 9 from a number does not alter its check sum, we can get rid
of the -9 or -18 by subtracting it from
Σ n,
and so prove that:
cs(n + m) = cs(n) + cs(m)
when m has only one significant digit.
We can break down any number into a sum of such numbers, e.g. 753 = 700 + 50 + 3,
and so the proposition will be true for any value of
m.
We wish to show that numbers that differ by 9 or a multiple of 9 have the same check sum.
Let us consider the case of
cs(n+9).
If the least significant digit of
n is non−zero, in calculating n+9
there will be a carry with the least significant digit
(denoted by n0) being reduced by 1,
while the next digit
(n1) is increased by 1 (unless it happens to be 9, see below) leaving the total sum of the digits
(Σ n) unchanged.
Going back to the case with the least significant digit
n0 being 0,
the sum of all the digits in
n+9:
Σ(n+9) = Σ n + 9
This number will necessarily have more than one digit, so that we will need to do another
Σ,
which will repeat the process, and the extra 9 will have to be absorbed eventually, because
when we get down to a
Σ n which is just a single digit, we can see imediately that the propositin is true.
The other exception condition occurs when there are two carries.
In this case 9 is subtracted from
Σ n,
just as before, thus cancelling out the extra 9 immediately.
So we now know that:
cs(n + m) = cs(n) + cs(m)
We also need to show that:
cs(n × m) = cs(n) × cs(m)
Our result for addition means that:
cs(n × m) = cs( m × cs(n) )
and also that:
cs(n × m) = cs( cs(m) × cs(n) )
Actually we should have shown earlier that:
cs(n + m) = cs( cs(n) + cs(m) )
So now for the actual question (the answer to which is due to Chris):
What is the checksum of the number (2100 + 3200)300 ?
2100 = (26)16 × 24
cs(26) = cs(64) = cs(10) = 1
cs((26)16) = 116 = 1
cs(2100) = cs(24) = cs(16) = 7
3200 = 9100
Any multiple of 9 has a checksum of 9.
(Just consider the nine times table.):
cs(3200) = 9
and
cs(2100 + 3200) = cs(7 + 9) = 7
7300 = (73)100
cs(73) = cs(cs(49) × 7) = cs(13 × 7) = cs(91) = 1
Thus:
cs( (2100 + 3200)300 ) = 1