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 numberSo, 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
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.00002666There 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.00000066A big drop, back in line with the earlier trend. One more round, even slower.
8: 21 of 90000000 0.00000023Another 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. -----