This post is split into three parts because of Atmos's character limit. This is part 3.

Part 1: https://projectatmos.space/profile/1p8WCZnqqG6N3ZOsJxBgUTo/p1SJCxFjA6yCA52Hz

Part 2: https://projectatmos.space/profile/1p8WCZnqqG6N3ZOsJxBgUTo/p1zcNRQIrjGHqXHN0

[…]

The last two describers can only be `3,3`

if there are at least two describer 1s (otherwise the sum wouldn't be equal to the length). Because there is no describer higher than 3, the 1 and 3 automatically need to be described by the two 3s and the only other describer that can occur is 2. It can't occur 3 times or more, because then you would need a describer 4 and `3,3`

wouldn't be the last two anymore. It can't occur 2 times, because then you would need another 3 and the 3 would occur 4 times. So it can only occur once or not at all. That limits the length of the number to at most 10 digits. Again, these can be tested and I did that, the list is above.

The last two describers can only be `4,4`

if there are at most 3 of any number in the describers, including the 1. But if there are at most three 1s, that means that the sum can't be equal to the length anymore: For every 4 you need two 1s, so for two 4s you would need four 1s already (which would need to be described by a 5). The same logic also excludes `5,5`

, `6,6`

and any other pair of describers that are equal and higher than 3 from being the last two describers.

If the last two describers were `4,5`

, `4,6`

, `4,7`

, …, `5,6`

, `5,7`

, … (the second to last describer 4 or more and the last describer higher), then you would need as many describer 1s as the last two describers added minus 4 (because you need to balance the difference from `2,2,2,2,2,…`

). But that would mean for `4,5`

already five 1s, which would mean that the 1 would need to be described by at least a 6, which doesn't occur. Increasing the last describer does nothing to change this and increasing the second to last describer only makes the difference worse.

If the last two describers are `2,4`

, `2,5`

, `2,6`

, … (2 and a number higher than 3), that means that there are exactly as many 1s as the last digit minus two (again, to balance the difference from 2 so that the sum fits). So in the case of `2,4`

at the end the number would be `1?1?2?(2?(2?(…)))4?`

, with a so far unknown amount of 2s in the middle. In this case it's two 1s, so the describer for the 1s would need to be 3. But there is no 3 in this number. The same happens for `2,5`

at the end, the 1s would need to be described by a 4. And so on.

So if the last two digits of a self-describing number with at least 14 digits can't be `1,1`

or `1,2`

or `2,2`

or `2,3`

or `2,x`

with x>2 or `3,3`

or `x,x`

with x>3 or `x,y`

with y>x>3, then that leaves `3,x`

with x>3 as the only option.

Since x is the highest describer, it needs to describe either 1 or 2. The differences from 2 need to be balanced with 1s, so you need x-2+1 1s (x-2 to balance the x and 1 to balance the 3), plus as many 1s as there are additional 3s. That means that the 1 needs to be described by x-2+1+1 plus the number of additional 3s, so at least x. Since x is already the biggest describer that means that you have to have exactly x-1 1s and only the one 3. So only the number of 2s is now unknown.

The highest describer left is 3, because x is already taken by 1. That means that 2 can occur at most two times. But 2 is also needed at least twice, to describe 3 and x.

So in summary, you have to have exactly x-1 1s, two 2s, one 3 and one x as describers. But that's exactly the pattern:

```
1?1?1?2?2?3?4?
1?1?1?1?2?2?3?5?
1?1?1?1?1?2?2?3?6?
…
```

Now it's just a matter of filling in the described digits: 1 needs to be described by x, 2 needs to be described by 3, 3 and x need to be described by the two 2s, that leaves only the 1s to fill. Those are arbitrary, as long as the described digit doesn't appear anywhere else in the number. Because I only select one set of arbitrary digits per set of digits that "matter", that means that this pattern describes all self-describing numbers with 14 or more digits. The ones with less digits were figured out by just letting a computer try all candidates.

q.e.d.

View older comments...

FaRo: • I optimised every little bit of the code. I researched a lot about which alternative ways of programming had better or worse performance in Java, for example I used arrays instead of lists for almost everything, I didn't use any method calls apart from the initial thread start (because of the tiny overhead it causes), I even refactored the entire program multiple times, especially to save the garbage collector as much work as possible (for example by reusing variables wherever possible), because at 100% CPU usage every bit of garbage collector work is less CPU time for the program itself. On one day I measured how much a few hours of doing these tiny optimisations combined sped up the program, it was a factor of about 2. The downside of programming like this was just that the program was pretty hard to read. Not because of code style, but because what the program actually did was incredibly complex. I would definitely recommend going into such extremes for performance in any project where performance isn't everything that counts. Or anything where other people need to read the code. That's also why I never showed the code itself to anyone, it's already confusing myself, even with about every tenth line being a comment. • I used a special way of looping over the numbers (from the third digit on), which already included multiple big optimisations in just the loop head. Again, I honestly don't fully understand it anymore today, I programmed this months ago: for(posIncr=length-3;posIncr>1&&++digits[posIncr]==maxNumber+1;posIncr--){ if(posIncr==2) return; digits[posIncr]=1; } I'm pretty sure that maxNumber had something to do with the length. • I planned to replace the ~10 line number generator with a new one that was 130 lines long and included way more optimisations. This would have sped up the program by another massive factor once again, to a total speedup relative to the original version in the billions or trillions (also depends on the length of the number, it might have even changed it from an exponential or quadratic runtime behaviour to a logarithmic one). But before I could integrate it into the main program I had to pause for multiple weeks and after my pause I came up with the way faster algorithm (that I then optimised into nothingness) within 30 minutes of thinking about the program again. The amount of numbers that were even checked is also interesting. The original brute-force version that only worked with base 10 needed 10^6, 10^8, 10^10, … tries for the numbers with 6, 8, 10, … digits. The last actually fully programmed version (which worked for arbitrary bases) needed 24, 536, 17179, 574170, 14314415, 556353114, 843787044 tries for 6, 8, 10, 12, 14, 16, 18 digits. Its number generator was a tiny bit slower, because it was more complex, but this version also discarded invalid numbers WAY faster, so it took even less time per checked number. The "new" generator that I had programmed in a new class would have had to check only 4, 23, 66, 156, 442, 1151, 3331 numbers with 6, 8, 10, 12, 14, 16, 18 digits. And the latest version, the mathematical concept: 0, 2, 1, 0, 1, 1, 1.

FaRo: But now an actual Atmos bug, a pretty bad one: Attempting to submit a comment with over 3000 characters fails silently. Luckily I copied the entire thing to the clipboard before clicking "send".

James Shiffer: The character limit is supposed to be there. Not preserving your message is the bug