Problem Statement

Write a procedure (say

c o 9

( x )

{\displaystyle {\mathit {co9}}(x)}

) which implements Casting Out Nines as described by returning the checksum for

x

{\displaystyle x}

. Demonstrate the procedure using the examples given there, or others you may consider lucky. Note that this function does nothing more than calculate the least positive residue, modulo 9. Many of the solutions omit Part 1 for this reason. Many languages have a modulo operator, of which this is a trivial application. With that understanding, solutions to Part 1, if given, are encouraged to follow the naive pencil-and-paper or mental arithmetic of repeated digit addition understood to be "casting out nines", or some approach other than just reducing modulo 9 using a built-in operator. Solutions for part 2 and 3 are not required to make use of the function presented in part 1. Notwithstanding past Intel microcode errors, checking computer calculations like this would not be sensible. To find a computer use for your procedure: Demonstrate that your procedure can be used to generate or filter a range of numbers with the property

c o 9

( k )

c o 9

(

k

2

)

{\displaystyle {\mathit {co9}}(k)={\mathit {co9}}(k^{2})}

and show that this subset is a small proportion of the range and contains all the Kaprekar in the range. Considering this MathWorld page, produce a efficient algorithm based on the more mathematical treatment of Casting Out Nines, and realizing: Demonstrate your algorithm by generating or filtering a range of numbers with the property

k % (

B a s e

− 1 )

(

k

2

) % (

B a s e

− 1 )

{\displaystyle k%({\mathit {Base}}-1)==(k^{2})%({\mathit {Base}}-1)}

and show that this subset is a small proportion of the range and contains all the Kaprekar in the range.

Let's start with the solution:

;;A macro was used to ensure that the filter is inlined.  
;;Larry Hignight.  Last updated on 7/3/2012.
(defmacro kaprekar-number-filter (n &optional (base 10))
  `(= (mod ,n (1- ,base)) (mod (* ,n ,n) (1- ,base))))

(defun test (&key (start 1) (stop 10000) (base 10) (collect t))
  (let ((count 0)
	(nums))
    (loop for i from start to stop do
	  (when (kaprekar-number-filter i base)
	    (if collect (push i nums))
	    (incf count)))
    (format t "~d potential Kaprekar numbers remain (~~~$% filtered out).~%"
	    count (* (/ (- stop count) stop) 100))
    (if collect (reverse nums))))