Discussion on: Challenge: find 'Kaprekar numbers'

[Heiko Dudzus]

Solution in Haskell:

I didn't want to take the route to String representation and back, I considered it as a computational problem and I wanted to find a purely computational solution. So I used digit values. Drawbacks: It appends number 1 as being kaprekar by convention. Benefit: It works for all bases (although output is decimal).

f base n =
  map ((+) <$> fst <*> snd) $
  filter ((/= 0).snd) $ takeWhile ((/=0).fst) $
  map ((quotRem (n^2)).(base^)) [1..]

kaprekar base = (1:) $ filter (elem <*> f base) [1..999]

f is like:

1. Divide the square by all powers of the base. -> infinite list of possibilities to split the number.
2. quotRem builds a tuple of integer quotient and remainder.
3. Keep the list entries until the quotient gets 0 to make the list finite. (Nothing interesting is happening beyond that point).
4. Remove the entries having a remainder of 0.
5. Build the sum of quotient and remainder.

f returns a list of sums of quotient and remainder. Now filter in the solution function, if n is an element of f n.

[Heiko Dudzus]

I tried to compute the Kaprekar numbers up to 10^8. A simple improvement in taking the interesting part and dropping the rest: If quotient or remainder are > n the sum of both must be > n. This reduced execution time by 50 %.

f base n =
  map ((+) <$> fst <*> snd) $
  takeWhile ((<n).snd) $ dropWhile ((>=n).fst) $
  map ((quotRem (n^2)).(base^)) [1..]

kaprekar n base = (1:) $ filter (elem <*> f base) [1..n]

[0nomat0]

Could I trouble someone to comment this code? Oops, I guess that's in the parent comment, thanks! I don't know Haskell but I'm interested in it. Does this solution work for the 'strange' ones like 4789, 5292?

Trying to wrap my head around how to interpret the definition of a Kaprekar number, in a way that includes these oddball numbers.

I'm currently studying Ruby -- I'll necro-post my Ruby solution if I manage to get it working with the oddballs.