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