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**The pattern**

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.

[…]