## 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.

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).

On second thought, my earlier code can be much simplified. (I decided

to use fold part-way through and didn’t finish the job.)

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:

Python 3 solution, not using recursion.

And the test:

Here’s a solution in Ruby.

Output: