Task   (in three parts)



Part 1
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.

Part 2
Notwithstanding past Intel microcode errors, checking computer calculations like this would not be sensible. To find a computer use for your procedure:

 Consider the statement "318682 is 101558 + 217124 and squared is 101558217124" (see: Kaprekar numbers#Casting Out Nines (fast)).
 note that 



318682


{\displaystyle 318682}

 has the same checksum as (



101558
+
217124


{\displaystyle 101558+217124}

);
 note that 



101558217124


{\displaystyle 101558217124}

 has the same checksum as (



101558
+
217124


{\displaystyle 101558+217124}

) because for a Kaprekar they are made up of the same digits (sometimes with extra zeroes);
 note that this implies that for Kaprekar numbers the checksum of 



k


{\displaystyle k}

 equals the checksum of 




k

2




{\displaystyle k^{2}}

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

Part 3
Considering this MathWorld page, produce a efficient algorithm based on the more mathematical treatment of Casting Out Nines, and realizing:

 





c
o
9


(
x
)


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

 is the residual of 



x


{\displaystyle x}

 mod 



9


{\displaystyle 9}

;
 the procedure can be extended to bases other than 9.
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.



related tasks
 First perfect square in base N with N unique digits
 Kaprekar numbers


/*REXX program demonstrates the  casting─out─nines  algorithm  (with Kaprekar numbers). */
parse arg LO HI base .                           /*obtain optional arguments from the CL*/
if LO=='' | LO==","  then do; LO=1; HI=1000; end /*Not specified?   Then use the default*/
if HI=='' | HI==","  then HI= LO                 /* "      "          "   "   "     "   */
if base=='' | base==","  then base= 10           /* "      "          "   "   "     "   */
numeric digits max(9, 2*length(HI**2) )          /*insure enough decimal digits for HI².*/
numbers= castOut(LO, HI, base)                   /*generate a list of (cast out) numbers*/
@cast_out= 'cast-out-'  || (base-1)     "test"   /*construct a shortcut text for output.*/
say 'For'     LO     "through"     HI', the following passed the'       @cast_out":"
say numbers;         say                         /*display the list of cast out numbers.*/
q= HI - LO + 1                                   /*Q:   is the range of numbers in list.*/
p= words(numbers)                                /*P"    "  " number  "    "     "   "  */
pc= format(p/q * 100, , 2) / 1  ||  '%'          /*calculate the percentage (%) cast out*/
say 'For'   q   "numbers,"   p   'passed the'    @cast_out    "("pc') for base'    base"."
if base\==10  then exit                          /*if radix isn't ten, then exit program*/
Kaps= Kaprekar(LO, HI)                           /*generate a list of Kaprekar numbers. */
say;  say   'The Kaprekar numbers in the same range are:'   Kaps
say
      do i=1  for words(Kaps);    x= word(Kaps, i)                 /*verify 'em in list.*/
      if wordpos(x, numbers)\==0  then iterate                     /*it's OK so far ··· */
      say 'Kaprekar number'   x   "isn't in the numbers list."     /*oops─ay!           */
      exit 13                                                      /*go spank the coder.*/
      end   /*i*/
 
say 'All Kaprekar numbers are in the'     @cast_out     "numbers list."             /*OK*/
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
castOut:  procedure;  parse arg low,high,radix;       rm= word(radix 10, 1) - 1;        $=
                          do j=low  to  word(high low, 1)    /*test a range of numbers. */
                          if j//rm == j*j//rm  then $= $ j   /*did number pass the test?*/
                          end   /*j*/                        /* [↑]  Then add # to list.*/
          return strip($)                        /*strip and leading blanks from result.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
Kaprekar: procedure;  parse arg L,H;   $=;   if L<=1  then $= 1  /*add unity if in range*/
            do j=max(2, L)  to H;        s= j*j  /*a slow way to find Kaprekar numbers. */
               do m=1  for length(s)%2
               if j==left(s, m) + substr(s, m+1)  then do;  $= $ j;   leave;    end
               end   /*m*/                       /*     [↑]  found a Kaprekar number.   */
            end       /*j*/
          return strip($)                        /*return Kaprekar numbers to invoker.  */