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


program castout9;
{$ifdef fpc}{$mode delphi}{$endif}
uses generics.collections;
type
  TIntegerList = TSortedList<integer>;
 
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.