(*
** D. R. Kaprekar's method of testing a number, N, to see if it is a
** self-number is as follows. Obtain N's digital root by adding its
** digits, then adding the digits of the result and so on until only one
** digit remains. If the digital root is odd, add 9 to it and divide by
** 2. If it is even, simply divide by 2. In either case call the result
** C. Subtract C from N. Check the remainder to see if it generates N.
** If it does not, subtract 9 from the last result and check again.
** Continue subtracting 9's, each time checking the result to see if it
** generates N. If this fails to produce a generator of N in k steps,
** where k is the number of digits in N, then N is a self-number.
**
** For example, we want to test the year 1975. Its digital root, 4, is
** even, so that we divide 4 by 2 to obtain C = 2. 1975 minus 2 is 1973,
** which fails to generate 1975. 1973 minus 9 is 1964. This also fails.
** But 1964 minus 9 is 1955, and 1955 plus the sum of its digits, 20, is
** 1975; therefore 1975 is a generated number. Since 1975 has four digits,
** we would have had only one more step to go to settle the matter.
*)
fun self i j =
let
fun self' i j cnt =
if i > j then cnt
else
let
fun self_test_fails i =
if i < 10 then (i mod 2) = 0
else
let
fun dr n = (* digital root: sum of n's digits *)
if n < 10 then n else (n mod 10) + dr (n div 10);
fun sddr n = (* single digit digital root *)
let val t = dr n; in if t <= 9 then t else dr t end;
fun d n = n + (dr n);
val t = sddr i;
val c = if t mod 2 = 0 then t div 2 else (t+9) div 2;
val r = i - c;
fun gen r n = (* true if r generates n *)
if r > n then false else if r = n then true else gen (d r) n;
fun gen_i i r n = (* performs the iteration *)
if i < 0 then false
else if gen r n then true else gen_i (i-1) (r-9) n;
fun ndigits n acc =
if n < 10 then acc else ndigits (n div 10) (acc+1);
in
gen_i (ndigits i 1) r i
end;
in
self' (i+1) j (if self_test_fails i then cnt else (cnt+1))
end;
in
self' i j 0
end;