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.

Advertisements

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
    
    f = foldl (addmod 9)
    
    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)
    
    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]
    
  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
        # 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:

    cast_out_nines(input)
    3
    cast_out_nines(output)
    3
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: