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:

# syntax: GAWK -f CASTING_OUT_NINES.AWK
# converted from C
BEGIN {
    base = 10
    for (k=1; k<=base^2; k++) {
      c1++
      if (k % (base-1) == (k*k) % (base-1)) {
        c2++
        printf("%d ",k)
      }
    }
    printf("\nTrying %d numbers instead of %d numbers saves %.2f%%\n",c2,c1,100-(100*c2/c1))
    exit(0)
}