TITLE: A Programming Digression: Kaprekar Numbers AUTHOR: Eugene Wallingford DATE: November 15, 2017 4:03 PM DESC: ----- BODY: Earlier this week I learned about Kaprekar numbers when someone re-tweeted this my way:
Kaprekar numbers are numbers whose square in that base can be split into 2 parts that add up to the original number
So, 9 is a Kaprekar number, because 9 squared is 81 and 8+1 equals 9. 7777 is, too, because 7777 squared is 60481729 and 6048 + 1729 equals 7777. This is the sort of numerical problem that is well-suited for the language my students are writing a compiler for this semester. I'm always looking out for fun little problems that I can to test their creations. In previous semesters, I've blogged about computing Farey sequences and excellent numbers for just this purpose. Who am I kidding. I just like to program, even in small language that feels like integer assembly language, and these problems are fun! So I sat down and wrote Klein functions to determine if a given number is a Kaprekar number and to generate all of the Kaprekar numbers less than a given number. I made one small change to the definition, though: I consider only numbers whose squares consist of an even-number of digits and thus can be split in half, a lá excellent numbers. Until we have a complete compiler for our class language, I always like to write a reference program in a language such as Python so that I can validate my logic. I had a couple of meetings this morning, which gave just the time I needed to port my solution to a Klein-like subset of Python. When I finished my program, I still had a few meeting minutes available, so I started generating longer and longer Kaprekar numbers. I noticed that there are a bunch more 6-digit Kaprekar numbers than at any previous length:
``` 1: 1
2: 3
3: 2
4: 5
5: 4
6: 24
```
I started wondering why that might be... and then realized that there are a lot more 6-digit numbers overall than 5-digit -- ten times as many, of course. (D'oh!) My embarrassing moment of innumeracy didn't kill my curiosity, though. How does that 24 compare to the trend line of Kaprekar numbers by length?
``` 1: 1    of        9  0.11111111
2: 3    of       90  0.03333333
3: 2    of      900  0.00222222
4: 5    of     9000  0.00055555
5: 4    of    90000  0.00004444
6: 24   of   900000  0.00002666
```
There is a recognizable drop-off at each length up to six, where the percentage is an order of magnitude different than expected. Are 6-digit numbers a blip or a sign of a change in the curve? I ran another round. This took much longer, because my Klein-like Python program has to compute operations like length recursively and has no data structures for caching results. Eventually, I had a count:
``` 7: 6    of  9000000  0.00000066
```
A big drop, back in line with the earlier trend. One more round, even slower.
``` 8: 21   of 90000000  0.00000023
```
Another blip in the rate of decline. This calls for some more experimentation... There is a bit more fun to have the next time I have a couple of meetings to fill. Image: courtesy of the Simpsons wiki. -----