user
Task   (in three parts)

Part 1

Write a procedure (say 

c
o
9
(
x
)
{\displaystyle {\displaystyle {\mathit {co9}}(x)}}
) which implements Casting Out Nines as described by returning the checksum for 

x
{\displaystyle {\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.

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 {\displaystyle 318682}}
     has the same checksum as (

    101558
    +
    217124
    {\displaystyle {\displaystyle 101558+217124}}
    );
:   note that 

    101558217124
    {\displaystyle {\displaystyle 101558217124}}
     has the same checksum as (

    101558
    +
    217124
    {\displaystyle {\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 {\displaystyle k}}
     equals the checksum of 

    k

    2
    {\displaystyle {\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 {\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 {\displaystyle {\mathit {co9}}(x)}}
     is the residual of 

    x
    {\displaystyle {\displaystyle x}}
     mod 

    9
    {\displaystyle {\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 {\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
assistant
(formerly Perl 6)

**Translation of**: Python

**Works with**: Rakudo version 2015.12

```
sub cast-out(\BASE = 10, \MIN = 1, \MAX = BASE**2 - 1) {
  my \B9 = BASE - 1;
  my @ran = ($_ if $_ % B9 == $_**2 % B9 for ^B9);
  my $x = MIN div B9;
  gather loop {
    for @ran -> \n {
      my \k = B9 * $x + n;
      take k if k >= MIN;
    }
    $x++;
  } ...^ * > MAX;
}

say cast-out;
say cast-out 16;
say cast-out 17;

```

Output:

```
(1 9 10 18 19 27 28 36 37 45 46 54 55 63 64 72 73 81 82 90 91 99)
(1 6 10 15 16 21 25 30 31 36 40 45 46 51 55 60 61 66 70 75 76 81 85 90 91 96 100 105 106 111 115 120 121 126 130 135 136 141 145 150 151 156 160 165 166 171 175 180 181 186 190 195 196 201 205 210 211 216 220 225 226 231 235 240 241 246 250 255)
(1 16 17 32 33 48 49 64 65 80 81 96 97 112 113 128 129 144 145 160 161 176 177 192 193 208 209 224 225 240 241 256 257 272 273 288)
```