## Casting Out Nines

### November 17, 2017

Here is our solution. The `loop` sums the digits, and the `if`s perform the casts:

```(define (nines n)
(let loop ((n n) (s 0))
(if (< 0 n)
(let ((q (quotient n 10))
(r (remainder n 10)))
(loop q (+ r s)))
(if (< 9 s) (nines s)
(if (= 9 s) 0 s)))))```

We test the function and verify the addition like this:

```> (do ((n 0 (+ n 1))) ((= n 1000) 'done)
(assert (nines n) (modulo n 9)))
done
> (= (nines (+ (nines  3074)
(nines  6017)
(nines 13814)
(nines  1810)
(nines    27)
(nines  3611)))
(nines           28353))
#t```

You can run the program at https://ideone.com/sWqNxO.

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 ) [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 =  * 10
digits.each { |digit| digit_table[digit] += 1 }
# cast out nines
digit_table = 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
```