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


sub co9 {  # Follows the simple procedure asked for in Part 1
  my $n = shift;
  return $n if $n < 10;
  my $sum = 0; $sum += $_ for split(//,$n);
  co9($sum);
}
 
sub showadd {
  my($n,$m) = @_;
  print "( $n [",co9($n),"] + $m [",co9($m),"] ) [",co9(co9($n)+co9($m)),"]", 
        "   =   ", $n+$m," [",co9($n+$m),"]\n";
}
 
sub co9filter {
  my $base = shift;
  die unless $base >= 2;
  my($beg, $end, $basem1) = (1, $base*$base-1, $base-1);
  my @list = grep { $_ % $basem1 == $_*$_ % $basem1 } $beg .. $end;
  ($end, scalar(@list), @list);
}
 
print "Part 1: Create a simple filter and demonstrate using simple example.\n";
showadd(6395, 1259);
 
print "\nPart 2: Use this to filter a range with co9(k) == co9(k^2).\n";
print join(" ", grep { co9($_) == co9($_*$_) } 1..99), "\n";
 
print "\nPart 3: Use efficient method on range.\n";
for my $base (10, 17) {
  my($N, $n, @l) = co9filter($base);
  printf "[@l]\nIn base %d, trying %d numbers instead of %d saves %.4f%%\n\n",
         $base, $n, $N, 100-($n/$N)*100;
}