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:

program castout9;
{$ifdef fpc}{$mode delphi}{$endif}
uses generics.collections;
type
  TIntegerList = TSortedList;
  
procedure co9(const start,base,lim:integer;kaprekars:array of integer);
var
  C1:integer = 0;
  C2:integer = 0;
  S:TIntegerlist;
  k,i:integer;
begin
  S:=TIntegerlist.Create;
  for k := start to lim do
  begin
    inc(C1);
    if k mod (base-1) = (k*k) mod (base-1) then
    begin
      inc(C2);
      S.Add(k);
    end;
  end;
  writeln('Valid subset: ');
  for i in Kaprekars do
    if not s.contains(i) then
      writeln('invalid ',i);
  
  for i in s do write(i:4);
  writeln;
  write('The Kaprekars in this range [');
  for i in kaprekars do write(i:4);
  writeln('] are included');  
  writeln('Trying ',C2, ' numbers instead of ', C1,' saves ',100-(C2 * 100 /C1):3:2,',%.');
  writeln;
  S.Free;
end;

begin 
  co9(1, 10, 99, [1,9,45,55,99]);
  co9(1, 10, 1000, [1,9,45,55,99,297,703,999]);
end.