# Challenge: find 'Kaprekar numbers'

### Peter Kim Frank Nov 13, 2017

I saw this tweet over the weekendâ€”

Via Wikipediaâ€”

In mathematics, a Kaprekar number for a given base is a non-negative integer, the representation of whose square in that base can be split into two partsâ€”either or both of which may include leading zeroesâ€”that add up to the original number. For instance, 45 is a Kaprekar number, because 452 = 2025 and 20 + 25 = 45.

## Challenge

In the language of your choice, write a script to find the first 8 Kaprekar numbers. `1, 9, 45, 55, 99, 297, 703, 999`

Two clarifications via @ripsup here:

First gotcha is the second part of the split numbers must be positive (no zeros). The second part was that you add a zero to the front if the length is odd.

Post your solution in the comments below!

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

^{m}) with n^{2}= xd+r with the constraint n=x+r. (x beeing the quotient and r the remainder)^{2}= xd +n -x = x(d-1) + n^{m}>n.The improvements are:

The computation time for the search up to 10

^{8}is reduced to 4 % compared to my original code.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?

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:

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%.

Some last improvements:

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:

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

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. :)

Time to get my repl up and running. Not very clean, but gets the job done. Here's some Clojure:

Thanks to Richard Orelup' tip to zero-pad the number if its length is odd.

Taking inspiration from Thomas Much's answer, I refactored my code to be more functional-esque and idiomatic:

For those a fan of Guile:

Here is my Javascript version of Kaprekar numbers

As far as I can see, most (if not all) programs use the strategy to convert the square to a string, pad it with 0 if the length is not even, and split it in the middle.

This seems to work for the range of Kaprekar numbers in the given range [1..999]. However, when I tried to speed up my program by splitting in the middle, I found out a problem with 5292. It is a Kaprekar number:

But to recognize it, you have to split 2 and 6 of 8 digits.

The implicit assumption about the Kaprekar property to show up when the number is split in the middle seems to be wrong. I tested some Javascript programs of this challenge with 5292 and it is not recognized as Kaprekar number.

Dang, that's a great point. I should have made the OP more detailed to clarify that the "split" isn't always right down the middle â€” even if it happens to work in the [1...999] range.

I definitely didn't think of that possibly while creating the post, or while working on my personal solution.

~~What does your approach to this look like? Now you've got me curious about how you're going about solving it.~~NVM, now I see your other comment.Is anyone interested in finding another 'strange' Kaprekar number like 5292?

I searched among the first 91 Kaprekar numbers in the range [ 1..10

^{8}]. So far, 5252 is the only one you have to split asymmetrically.What makes 5292 so special?

4879 is 'strange', too:

4879 = 238 + 04641

Ok, I see. I've missed it because of the leading zero in the second part.

I think your OP is really ok. I also didn't expect something like this. I think I will inspect some higher Kaprekar number.

But I am looking forward to see how the JS/Java/Clojure/LISP-like solutions get fixed (and I apologize for beeing such a killjoy ;-)

I'm not pretty good at coding but I tried in my own way :) just for fun and I hope is ok.

Here is my JS version:

Here is the JSFiddle link:

jsfiddle.net/kw95nv45/2/

This was a lot harder than I thought mainly because I had to look up why some numbers were and weren't Kaprekar numbers because the above description doesn't include all the details. First gotcha is the second part of the split numbers must be positive (no zeros). The second part was that you add a zero to the front if the length is odd.

And I already refactored my answer. I'm happier with this one.

Awesome job refactoring, and apologies for not including the pertinent info re: zeros in the OP!! I'll add that info to the main post.

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 is like:

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

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 %.Ok, here's a Java 8 version:

As Heiko points out, the solution was incorrect, because the split was always done in the middle of the string...

So, here's a (hopefully correct) Java 9 solution (Java 9 because I use takeWhile):

I chose to output the first 16 numbers so we can see the output includes numbers 4879 and 5292.

I really like to see your use of Streams and lambdas solving this problem. Nice occasion for me to learn a little bit more about them.

OK - this was way more of a rabbit hole than I thought... :) Here's two, new (F#) and old (COBOL). Both of these work within the constraints of the initial challenge, but will fail outside of that; had I not spent the amount of time I already spent on these, I might have at least made the F# version be able to handle others.

p.s. 0 also fits the description from the tweet! (0

^{2}= 0; 00 = 0 + 0 = 0; 0 = 0)## F#

## COBOL

(Free format, "*>" denotes a comment)

OK - fixed format, just for grins...

(Fixed format: col 1-6 reserved, usually line numbers or blank; col 7 - "*" = comment, blank otherwise; col 8-11 - division/section identifiers, paragraph names, top-level data items; col 12-72 - executable code, data item sub-definitions; col 73+ - ignored)Holy cow - the formatter knows COBOL! If I'd used fixed format, it wouldn't even look weird.

Seems I'm pretty late for this, but anyway, here's some Rust solution:

And if you consider that parts of a number should not necessarily be of equal size, the solution becomes a bit more wordy (suppose, a lot can be improved here):

Figure it's only fair to throw my answer into the ring. Clearly very novice and verbose ðŸ˜‡. Added a number of comments for the other #beginners out there.

Elixir (naiÌˆve, absolutely not optimized):

I have much sympathy for LISP and Clojure but have not that much experience with it. So, to stay in touch with it, here is my Clojure program, mostly a one-to-one translation of my latest Haskell program:

I really like the threading macros. :-) Computing up to 10

^{8}, the execution time of the jar file is ten times the execution time of the compiled Haskell. Did I make a serious mistake, performance-wise? Of course, there is the JVM, but I didn't expect this program to be slower with factor 10.Because I haven't done Groovy for a while. I miss it!

Something like this in python

Pythonic mine's:

Usage:

`python script.py max`

`max`

is the maximum integer to look up to (3037000499):