Followup to my "self-describing numbers" story: https://projectatmos.space/profile/1p8WCZnqqG6N3ZOsJxBgUTo/p1cNCw1OTsioTQBRk
This post is split into three parts because of Atmos's character limit. This is part 1.
Part 2: https://projectatmos.space/profile/1p8WCZnqqG6N3ZOsJxBgUTo/p1zcNRQIrjGHqXHN0
Part 3: https://projectatmos.space/profile/1p8WCZnqqG6N3ZOsJxBgUTo/p1mZOwFRzbxYBjidY
It wasn't clear to everyone I showed the previous post to, what the actual sequence was. So I'll explain it here:
The last 8 digits are always
232x32x1, where x is the length of the number (number of digits) divided by 2, minus 3. Everything before that is filled up with pairs of digits where the first is always 1 and the second is arbitrary (as long as it's not 1, 2, 3 or x and as long as it's unique). In the ones I chose I didn't use 0 and otherwise used the lowest digits possible, so it always started with 4 and increased by 1 each time, skipping x, ending with x+3.
Here are the first 20 self-describing numbers, only the first four don't follow the pattern:
22 12143133 14212332 1415223133 15161723243241 1416171823253251 141517181923263261 14151618191A23273271 14151617191A1B23283281 14151617181A1B1C23293291 1415161718191B1C1D232A32A1 1415161718191A1C1D1E232B32B1 1415161718191A1B1D1E1F232C32C1 1415161718191A1B1C1E1F1G232D32D1 1415161718191A1B1C1D1F1G1H232E32E1 1415161718191A1B1C1D1E1G1H1I232F32F1 1415161718191A1B1C1D1E1F1H1I1J232G32G1 1415161718191A1B1C1D1E1F1G1I1J1K232H32H1 1415161718191A1B1C1D1E1F1G1H1J1K1L232I32I1 1415161718191A1B1C1D1E1F1G1H1I1K1L1M232J32J1
Why this list is complete
Now the complicated part: Why are there no self-describing numbers that don't follow this pattern (except for the first four)?
To make wording for myself easier, I'll now split up each number into digit pairs, of which the first digit is always the "describer" and the second digit always the "described number/digit". For example, in
12143133, the first 1 describes how many twos there are: one. So it is the describer of the twos. The amount of twos gets described by the describer, so the 2 is the described digit.
It's easiest to first generate all the describers (that was my "new algorithm" idea) and later fill in the described numbers. For example if you have a set of describers like
1,1,3,3, then you already know that you'll have to put a 1 as described number behind a describer 3, because so far two 1s have been used (in the describers) and you have to use the 1 as a described number exactly once (you can't not use it, because it was used, so it needs to be described, and you can't use it twice, because you would redundantly describe it). So you put a described 1 behind any of the describer 3s. Since I want to exclude rearrangements as well, I'll pick the lowest possible number resulting from rearrangements, so you insert the 1 after the first 3 (3133 is smaller than 3331). Then the same for the 3, because that was used as a describer as well. It was used two times so far, plus 1 for the occurrence in the described numbers, makes 3, so put it behind the other describer 3.
If you can't fit all the describers in as described digits, then that set of describers is invalid, because you can't let the number describe itself. If you end up with anything else than 1s left as describers, then it's also invalid, because either you would have to describe a number redundantly to have it in the set of described digits twice or you would have conflicting/false statements about the number of occurrences (like 2939). The describer 1s can then just be filled up with arbitrary numbers, as long as those aren't anywhere else in the number yet.
Since you always put the describers in at the first possible described position, every set of describers has either one or no possible set of described digits. I'll show next why only the sets of describers that follow the above pattern can be in valid numbers, so because the pattern obviously works that means that every valid set of describers has exactly one set of valid described digits: the one in the pattern. This means that we already don't need to worry about the described digits anymore, only the describers are important from now on.