# Perl Weekly Challenge 107: Self-descriptive Numbers

by Abigail ## Challenge

Write a script to display the first three self-descriptive numbers. As per wikipedia, the definition of Self-descriptive Number is

In mathematics, a self-descriptive number is an integer m that in a given base b is b digits long in which each digit d at position n (the most significant digit being at position 0 and the least significant at position b - 1) counts how many instances of digit n are in m.

### Example

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

### Output

1210, 2020, 21200


## Discussion

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$$.

## Solution

### Perl

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.

### Other languages

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.