A few months ago I discovered "self-describing" numbers, like for example 12143133, which includes one two, one four, three ones and three threes, abbreviated: 1 2, 1 4, 3 1s and 3 3s, put together 12143133 again.
I wanted to figure out the pattern behind them. But first some additional restrictions:
Because you can arbitrarily rearrange the number pairs (31331412, 12143331, 14123331, …), I excluded rearrangements.
Because you can choose arbitrary numbers where you say "one <?>" (12153133, 12163133, 12173133, …), I chose to only include one set of arbitrary digits per set of digits that actually "matter". Completely excluding those would limit the entire set of self-describing numbers to only the number 22 (proving that is hard, see followup posts).
Some numbers also partially describe themselves, like 1421, which does include one four and two ones, but doesn't actually tell you how many twos it contains. I excluded those as well.
Some numbers describe themselves redundantly, like 4444, which does include four fours and four fours, but the second pair doesn't tell you anything new, so I excluded those as well.
And a clarification: The base doesn't actually matter at all. You can pretend that "12143133" was written in base 5, base 8, base 10, base 16, base 42069, …, it always gives you a self-describing number.
So then I started writing a program that generates these numbers. First brute force checking every number (1111, 1112, 1113, 1114, …), then with more and more optimisations. The brute force version didn't even finish going through the 12-digit numbers in an entire night, but after a LOT of optimisations it took less than 0.15 seconds. These optimisations already came from a lot of interesting mathematical considerations. Then I rewrote a big part of the program in a new class to make it even faster, but before I could re-integrate that into the program, I had to pause because I didn't have much free time anymore.
At that point I had already come up with a way to generate arbitrarily long self-describing numbers, but I had no idea whether there would be any more that didn't follow this pattern.
Today I wanted to continue and mainly just clean up the program, comment a few things and so on, so that I could attach it in applications for programming jobs. But after not even 30 minutes of thinking about the program, I came up with a MUCH better algorithm that essentially skips all the number trying and generates a very small amount of numbers to check. For example the latest version of the program tried 341907 12-digit numbers, this new one would have had to try only 10. I could have thrown away most of the program and rewritten it for a performance gain with an estimated factor of a few million again (for bigger numbers). But then I optimised this idea even further, for many hours today, until I had it down to only 2 12-digit numbers to check and for example only 4 20-digit numbers. And then I thought about it even more and eventually I proved to myself that the pattern I already knew for weeks actually contained ALL self-describing numbers (at least with a length of 14 or more).
Sooo… I now have no program to write anymore. I started with a better algorithm and optimised this algorithm so far that I ended up with practically nothing. This is amazing from a mathematical standpoint, it's really great to know the exact pattern to generate these numbers, but I also don't have a program anymore with which I can brag about my programming and algorithm optimisations skills. I basically did my job too well. :D
About the proof that all self-describing numbers follow this pattern: That's pretty complicated to write down. I'll do it at some point, but not in this post, it will be a followup post at a later date. But the pattern itself is pretty easy to understand, I don't think I even need to explain it:
22 12143133 14212332 1415223133 (pattern starts here) 15161723243241 1416171823253251 141517181923263261 …
Edit: I wrote down the proof now, split into three posts:
Part 1: https://projectatmos.space/profile/1p8WCZnqqG6N3ZOsJxBgUTo/p1SJCxFjA6yCA52Hz
Part 2: https://projectatmos.space/profile/1p8WCZnqqG6N3ZOsJxBgUTo/p1zcNRQIrjGHqXHN0
Part 3: https://projectatmos.space/profile/1p8WCZnqqG6N3ZOsJxBgUTo/p1mZOwFRzbxYBjidY