Discussion on: Challenge: find 'Kaprekar numbers'

[Heiko Dudzus]

Some last improvements:

1. Use fixed-width Ints instead of arbitrary sized Integers (by function signature) Large improvement!
2. It pays off to spend an additional modulo division if the number of possible divisors for the critical division can be heavily reduced.
3. 'any' slightly outperforms 'elem'. (in this case?)
4. A hand-rolled recursion sometimes performs better (without additional division) and sometimes worse (with additional division) than the folding recursions hidden in the 'elem' or 'any' functions. (But code with builtin folds is much nicer to read.)

The improvement steps were: 1000s - 500s - 90s - 60s - 19s - 13s - 9s. Quite funny to squeeze the algorithm like that. :-) This is what I came up with:

isKaprekar :: Int -> Int -> Bool
isKaprekar base n = let sqr = n^2 in
  any (\div -> (sqr-n) `mod` (div-1) == 0) $ -- any rem = 0? <=> kaprekar!
  takeWhile (\div -> (sqr `mod` div) < n) $  -- sensible bounds for divisors
  dropWhile (<=n) $                          
  map (base^) [1..]                          -- infinite list of divisors

main = print $ 1:(filter (isKaprekar 10) [1..10^8])

I wanted to have it in C for reference. Even expressed imperatively, it is now a very simple and nice algorithm. (2-3s)

#include <stdio.h>

int isKaprekar (int b, long long n) {
  long long sqr = n*n;
  long long div = 1;
  while (div <= n) div *= b;
  while (sqr % div < n) {
    if ((sqr - n) % (div - 1) == 0) return 1;
    div *= b;
  }
  return 0;
}

int main() {
  int base = 10;
  printf("%i ", 1);
  for (long long n=2; n<=100000000; n++) {
    if (isKaprekar(base,n)) printf("%i ", n);
  }
  return 0;
}

C profited more by the additional division, it reduced the execution time by 75%, Haskell profited only by 50 %.

I hope, I'm really done, now. :)