DEV Community

Discussion on: Challenge: find 'Kaprekar numbers'

View post
Collapse
 
heikodudzus profile image
Heiko Dudzus • • Edited

I managed to reduce the number of divisions by throwing some mathematics on it. Put very short:

  1. If n is a Kaprekar number (to a base b) there must be a divisor ( d=b^m ) with n^2 = xd+r with the constraint n=x+r. (x beeing the quotient and r the remainder)
  2. Substituting r with n-x, we get: n^2 = xd +n -x = x(d-1) + n
  3. So: n(n-1) = x (d-1) --> x = n(n-1)/(d-1) This division can have no remainder!
  4. The quotient x has to be < n (because n=x+r (with r>0)). Conclusion: d>n. It tells me, I should start with exponents m so that b^m >n.

The improvements are:

  • One modulo division is enough, where my original code had to compute quotient and remainder.
  • The lower bound for the divisor is increased and, more important, preserved before divisions take place.

The computation time for the search up to 10^8 is reduced to 4 % compared to my original code.

isKaprekar base n =
  elem 0 $                                  -- any remainders 0? 
  takeWhile (<n) $ -- remainder has to be < n. Now the list is finite.
  map (\div -> (n*(n-1)) `mod` (div-1)) $ -- compute the critical remainders
  dropWhile (<=n) $ map (base^) [2..]       -- divisors must be > n

main = print $ filter (isKaprekar 10) [1..10^8]
Collapse
 
peter profile image
Peter Kim Frank •

I love seeing the iterations of your solutions. Not that this challenge was intended to have any "winners," but if we had to choose...

Do you have any ideas for new #challenge posts?

Collapse
 
heikodudzus profile image
Heiko Dudzus •

Thanks. I enjoyed learning about Kaprekar number as well as I enjoyed iterating my solutions as I digged deeper into it.

You encouraged me to pose a challenge, hoping it's not too easy and not too hard. dev.to/heikodudzus/challenge---pri...

BTW: I saw a possible error in my last iteration. takeWhile (<n) is not proven to be correct. It's better to do it that way:

isKaprekar base n = let sqr = n^2 in
  elem 0 $                              -- any remainder = 0? <=> is kaprekar!
  map (\div -> (sqr-n) `mod` (div-1)) $ -- compute the critical remainders
  takeWhile (<sqr) $ dropWhile (<=n) $  -- sensible bounds for divisors
  map (base^) [1..]                     -- infinite list of divisors

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

Also, it's nicer to use upper and lower bounds for divisors before computing the devisions. This is proven to be correct now, but I lost speed. ;-) The speed improvement by melting construction and restriction together is only 86% instead of 96%.

Thread Thread
 
heikodudzus profile image
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. :)