Casting Out Nines
November 17, 2017
Here is our solution. The loop sums the digits, and the ifs 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.
Programming Praxis 
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)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)Goes quite nicely into a double fold:
Here’s a generalization to any radix (so we are “casting out n’s” for radix n+1). More Haskell:
import Data.Digits (digits) cast radix = foldl (foldl addmod) 0 . map (digits radix) where addmod n m = mmod (n+m) (radix - 1) mmod n k = if n < k then n else n-k -- cast radix s = (sum s) mod (radix-1) 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]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_sumAnd the test:
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 # add remaining digits 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: