Perl Weekly Challenge 107: Self-descriptive Numbers

1210 is a four-digit self-descriptive number:

• position 0 has value 1 i.e. there is only one 0 in the number
• position 1 has value 2 i.e. there are two 1 in the number
• position 2 has value 1 i.e. there is only one 2 in the number
• position 3 has value 0 i.e. there is no 3 in the number

In essence, this is just a Hello, World! program. We don't even need to go to the OEIS to find the first three numbers — the challenge tells us what the output is!

To still have a tiny bit of a challenge, we will derive what the first three self-describing numbers are.

Let \(N_b\) be a self-describing number in base \(b\). \(N_b\) has \(b\) digits: \(N = d_{0} d_{1} \ldots d_{b-1}\). We then have the following observations:

1. \(0 < d_0\): we do not accept a leading \(0\).
2. \(b = \sum_{i=0}^{b-1} d_i\). This follows from the definition of a self-describing number: the sum of the digits must equal the number of digits, and the number of digits is \(b\).
3. \(\forall i: 0 \leq i \leq b - 1 \implies d_i < b - 1\). (A self-describing number in base \(b\) does not contain the digit \(b - 1\)). Suppose \(N_b\) does contain such a digit. Then by point ii, \(N_b\) contains a \(1\), and all other digits are \(0\). If \(b = 2\) that would imply that \(N_2 = 11\), but \(11\) clearly is not self describing. Otherwise \(d_0 > 0\) (by point i); \(d_1 > 0\) (since \(N_b\) contains at least one \(1\)), and all other digits are \(0\). But that means that \(d_{b-1}\) is \(0\), which contradicts that \(N_b\) contains the digit \(b - 1\).
4. \(b > 2 \implies d_{b-1} = 0\) (The last digit is a \(0\)). This follows directly from point iii.
5. \(b > 4 \implies d_0 > 1\) (For bases larger than \(4\), a self-describing number contains at least two \(0\)s). Suppose \(b > 4\), and \(d_0 = 1\). This means that \(N_b\) contains just a single \(0\), and this has to be \(d_{b-1}\) (by point iv). The digits \(d_1 \ldots d_{b-2}\) have to sum to \(b - 1\) (by point ii) which means that one of those digits is a \(2\), and the rest are \(1\)s. But then \(N_b\) contains \(b - 2\) \(1\)s, one \(2\) and one \(0\). And since \(b > 4\), \(b - 2 > 2\), so \(N_b\) cannot be self-describing.
6. \(b > 4 \implies d_0 < b - 2\). (For bases larger than \(4\), a self-describing number has at least three digits which are not \(0\)). the first digit must be less than \(b - 2\)). Suppose we would have a self-describing number \(N_b\), with \(d_0 = b - 2\). That means that only one of the digits \(d_1, d_2, \cdots, d_{b-1}\) is non-zero. Let \(d_k\) be this non-zero digit. By point ii, \(d_k = 2\), and by point i, \(k > 0\). But that implies that \(N_b\) contains the digit \(k\) twice. However, \(N_b\) contains the digit \(b - 2\) once (we did assume \(d_0 = b - 2\)), the digit \(2\) once, and the digit \(0\), \(b - 2\) times. \(b > 4 \implies b - 2 > 2\), so the number cannot be self-describing.
7. \(b > 5 \implies d_0 > 2\) (For bases larger than \(5\), a self-describing number contains more than two \(0\)s). By point v, we already know \(d_0 > 1\). Suppose we have a self-describing number \(N_b, b > 5\), with \(d_0 = 2\). That means, \(N_b\) has \(b - 2\) digits which are non-zero, and sum to \(b\). This implies \(N_b\) has two \(2\)s, \(b - 4\) 1s, and two \(0\)s. Two \(2\)s means \(d_0 = d_2 = 2\), which means \(d_1 = 0 \vee d_1 = 1\). But we also have \(d_1 = b - 2 > 3\), which leads to a contradiction.
8. \(b > 5 \implies d_0 < b - 3\) (For bases larger than \(5\), a self-describing number has at least four digits which are not \(0\)). By point vi, we already know \(d_0 < b - 2\). Suppose we have a self-describing number \(N_b, b > 5\), with \(d_0 = b - 3\). That means that outside of \(d_0\), \(N_b\) has two digits which are not \(0\). And since those two numbers must sum to \(3\) (by point ii), the only possibility for those numbers is that one of them is \(1\), and the other is \(2\). But that means we have three different digits which appear once: \(1\), \(2\) and \(b - 3\). And that would mean \(d_1 = 3\), which leads to a contraction.

We're now ready to derive the first three self-describing numbers.

1. There cannot be any self-describing numbers for base \(b = 1\). The only digits in that base are \(0\), but we cannot have a leading \(0\).
2. For base \(2\), point i implies any \(N_2\) must start with a \(1\). But this constradicts point iii, so we cannot have a self-describing number in base \(2\).
3. For base \(3\), points i and iii imply that for any \(N_3\) \(d_0 = 1\) (the first digit). Point iv implies the number end with a \(0\), so \(d_2 = 0\). Then, by point ii, \(d_1 = 2\), but this contradicts point iii. So there cannot be any self-describing numbers in base \(3\).
4. For base \(4\), points ii and iii imply any \(N_4\) has \(d_0 = 1\) or \(d_0 = 2\). Point iv implies that \(d_3 = 0\).
   • If \(d_0 = 1\), then \(d_1 + d_2 = 3\), so one of them is \(1\), and the other \(2\). \(d_1\) cannot be \(1\), because it describes the number of \(1\)s in the number, and we have 2 of them. So, \(d_1 = 2\) and \(d_2 = 1\). This does not lead to any contractions, so the first self-describing number is \(1210\).
   • If \(d_0 = 2\), then \(d_1 + d_2 = 2\). If \(d_1 = d_2 = 1\), then we have two \(1\)s, but \(d_1 = 1\), so that would not be self-describing. Which leaves the possibility one of \(d_1\) and \(d_2\) is \(0\), and the other \(2\). \(d_1 = 2\) is not going to work, as that would imply \(N_4\) has two \(1\)s — but there are none. If \(d_1 = 0\), we get \(d_2 = 2\), which does not lead to a contraction, so the second self-describing number is \(2020\).
5. For base \(5\), by points iii, v, and vi, we have one possiblity for the first digit: \(d_0 = 2\). That means any \(N_5\) contains contains two \(0\)s, including \(d_4\). Hence, \(d_1 + d_2 + d_3 = 3\), with one of those digits being \(0\). The other two must therefore be \(1\), and \(2\). This means \(N_5\) contains two \(2\)s, so \(d_2 = 2\). There are no \(3\)s, so \(d_3 = 0\), and \(d_1 = 1\). This makes \(21200\) the third self-describing number.
6. There are no self-describing numbers in base \(6\). From point vii it can be deduced that for any number \(N_6\), \(d_0 > 2\). From point viii it can be deduced that \(d_0 < 3\). But no such digit exists.
7. For any base \(b > 6\), there is at least one self-describing number. In particular, a number where \(d_0 = b - 4, d_1 = 2, d_2 = 1\), and \(d_{b-3} = 1\) and all other digits \(d_i\) are \(0\) is self-describing. For bases \(7, 8, 9\) and \(10\), this gives the self-describing numbers \(3211000, 42101000, 521001000\), and \(6210001000\).

As said above, we just have a glorified Hello, World! program, so all we need to do is use say and the text we want to display.

say "1210, 2020, 21200";

Find the full program on GitHub.

We also have boring solutions in AWK, Basic, Bc, Befunge-93, C, Cobol, Csh, Erlang, Forth, Fortran, Go, Java, Lua, m4, Node.js, OCaml, Pascal, PHP, PostScript, Python, R, Rexx, Ruby, Scheme, sed, SQL, and Tcl.