## Casting Out Nines

### November 17, 2017

It doesn’t seem to be taught any more (neither of my daughters have ever heard of it), but casting out nines is a useful computational trick for verifying manual arithmetic calculations. Consider the sum below:

``` 3074
6017
13814
1810
27
3611
-----
28353```

The sum of the digits of 3074 is 14, and the sum of the digits of 14 is 5, so the result of casting out nines from 3074 is 5. The sum of the digits of 6017 is 14, and the sum of the digits of 14 is 5, so the result of casting out nines from 6107 is 5. The number 13814 includes digits 1 and 8, which sum to 9, so we can ignore them and sum the digits 3, 1 and 4, so the result of casting out nines from 13814 is 8. Likewise, the 1 and 8 of 1810 sum to 9, so we ignore them, and the result of casting nines out of 1810 is 1. The digits of the 27 sum to 9, which we cast out, so the result of casting nines out of 27 is 0. Finally, we can cast out the 3 and 6 from 3611, so the result of casting nines out of 3611 is 2. Now the nines results of the six numbers are 5, 5, 8, 1, 0 and 2, and again we cast out the 8 and 1, leaving 12. The sum of the digits of 12 is 3, which is the final result of casting out nines from the addends.

The sum of the digits of 28353 is 21, and the sum of the digits of 21 is 3, so the result of casting nines out of 28353 is 3. Since the addends and the sum have the same result when casting out nines, it is plausible that the sum is correct. If the process of casting out nines yielded different results from the addends and the sum, we could be sure that the sum was incorrect.

Although that formulation sounds complicated, in practice this goes faster than you can think. Consider 28353. The first two digits sum to 10, so cast out a nine and count 1. Then add 3, giving a running nine-sum of 4, and add 5, giving a running nine-sum of 9, which can be cast out. The only remaining digit is 3, which is the result of casting out nines from the sum.

Casting out nines from the addends is even easier, because there are more ways to make nine. From the first two addends, cast out the 3 and 6, then cast out the 7, 4, and 7, leaving 1. Adding the third number gives 0; cast out the 1 and 8 immediately, leaving the 1 carried from the first two numbers, plus 3, 1 and 4, which sums to 9, which is equivalent to 0. Cast out 1 and 8 from the fourth number, leaving 1, cast out the fifth number entirely, and cast out 3 and 6 from the sixth number, leaving the carry of 1 plus the two 1s at the end of the sixth number, for a total of 3.

With a little bit of practice, this becomes ridiculously fast. Your friends will be amazed when you quickly tell them their sum is wrong; they will also hate you.

Mathematically, casting out nines is the same as addition modulo 9. MathWorld gives a good explanation. The process of casting out nines works for multiplication and exponentiation as well as addition.

Your task is to write a program to cast out nines; avoid the temptation to simply take the remainder on division by 9 and do the actual work of summing the digits and casting out nines. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 6 Responses to “Casting Out Nines”

1. chaw said

This code tries to stay true to the spirit of the “by hand”
procedure (as opposed to being efficient for a computer). For
instance, it uses a naive conversion to digits as one would do by
hand (by simply “writing digits separately”). The code uses only
addition, subtraction, and comparison of small numbers (in
particular, no division). One point of divergence is that it only
considers digits sequentially when casting out nines; i.e.,
non-consecutive digits that sum to 9 are not eliminated (e.g., the
3 and 6 from the first two addends of the example).

``` (import (scheme base) (scheme write) (only (srfi 1) fold first second)) (define addends-101 '(3074 6017 13814 1810 27 3611)) (define sum-101 28353) (define (add-mod-9 a b) (let ((s (+ a b))) (if (< s 9) s (- s 9)))) (define (digits n) (map string->number (map string (string->list (number->string n))))) (define (cast-out-nines n) (let f ((n n)) (if (< n 9) n (f (fold add-mod-9 0 (digits n)))))) (define (cast-out-nines/casts ds) (let f ((ds ds)) (if (null? (cdr ds)) (car ds) (f (cons (add-mod-9 (first ds) (second ds)) (cddr ds)))))) (define (check-addition/casting-out-nines addends sum) (= (cast-out-nines/casts (map cast-out-nines addends)) (cast-out-nines sum))) (display (check-addition/casting-out-nines addends-101 sum-101)) (newline) ```

2. chaw said

On second thought, my earlier code can be much simplified. (I decided
to use fold part-way through and didn’t finish the job.)

``` (import (scheme base) (scheme write) (only (srfi 1) fold first second delete)) (define addends-101 '(3074 6017 13814 1810 27 3611)) (define sum-101 28353) (define (add-mod-9 a b) (let ((s (+ a b))) (if (< s 9) s (- s 9)))) (define (digits n) (map string->number (map string (string->list (number->string n))))) (define (cast-out-nines n) (cast-out-nines/casts (delete 9 (digits n)))) ;; each d is in 0..8 (define (cast-out-nines/casts ds) (fold add-mod-9 0 ds)) (define (check-addition/casting-out-nines addends sum) (= (cast-out-nines/casts (map cast-out-nines addends)) (cast-out-nines sum))) (display (check-addition/casting-out-nines addends-101 sum-101)) (newline) ```

3. matthew said

Goes quite nicely into a double fold:

```import Data.Digits (digits)

addmod k n m = (n+m) `mod` k

main =
print (f 0 (digits 10 28353)) >>
print (foldl f 0 (map (digits 10) [3074, 6017, 13814, 1810, 27, 3611]))
```
4. matthew said

Here’s a generalization to any radix (so we are “casting out n’s” for radix n+1). More Haskell:

```import Data.Digits (digits)

mmod n k = if n < k then n else n-k

main =
print (map (28353 `mod`) [1..19]) >>
print (map (flip cast [28353]) [2..20]) >>
print (map (flip cast [3074, 6017, 13814, 1810, 27, 3611]) [2..20])
-- [0,1,0,1,3,3,3,1,3,3,6,9,0,3,3,1,14,3,5]
-- [0,1,0,1,3,3,3,1,3,3,6,9,0,3,3,1,14,3,5]
-- [0,1,0,1,3,3,3,1,3,3,6,9,0,3,3,1,14,3,5]
```
5. Alex B said

Python 3 solution, not using recursion.

```def cast_nines(n):
if not isinstance(n, int):
raise TypeError('Expected integer')
if n < 0:
raise ValueError('Must be positive')

running_sum = 0

while n > 0:
n, last_digit = divmod(n, 10)
running_sum += last_digit
if running_sum >= 9:
running_sum -= 9
return running_sum
```

And the test:

```>>> assert all(cast_nines(i) == i%9 for i in range(1001)), 'FAILED'
>>>
```
6. Daniel said

Here’s a solution in Ruby.

```# Returns the digits in a number
# E.g., digits(39412) -> [3,9,4,1,2]
def get_digits(number)
output = []
number = number.abs
while number > 0
number, digit = number.divmod(10)
output.push(digit)
end
output.reverse
end

# Sums numbers
def sum(numbers)
numbers.inject(0, :+)
end

# Multiplies numbers
def multiply(numbers)
numbers.inject(1, :*)
end

def cast_out_nines(number)
loop do
digits = get_digits(number)
# digit_table maps digits to counts (indices correspond to digits)
digit_table = [0] * 10
digits.each { |digit| digit_table[digit] += 1 }
# cast out nines
digit_table[9] = 0
# cast out pairs that sum to nine:
#   (1,8), (2,7), (3,6), (4,5)
# (0,9) excluded since 9 already cast out.
(1..4).each do |digit|
other_digit = 9 - digit
digit_count = digit_table[digit]
other_digit_count = digit_table[other_digit]
num_cast_outs = [digit_count, other_digit_count].min
digit_table[digit] -= num_cast_outs
digit_table[other_digit] -= num_cast_outs
end
number = sum((0..9).zip(digit_table).map(&method(:multiply)))
break if number < 9
end
number
end

puts "cast_out_nines(input)"
puts cast_out_nines(
cast_out_nines(3074)  +
cast_out_nines(6017)  +
cast_out_nines(13814) +
cast_out_nines(1810)  +
cast_out_nines(27)    +
cast_out_nines(3611)
)
puts "cast_out_nines(output)"
puts cast_out_nines(28353)
```

Output:

```cast_out_nines(input)
3
cast_out_nines(output)
3
```