Posted on September 14, 2020

Self-describing Numbers: Part 2

In my previous blog post, I introduced the self-describing numbers, as well as some associated theorems and definitions.

In this blog post, I’ll show how the non-repeating self-describing numbers can be efficiently found. To the best of my knowledge, I am the first to find such an algorithm.

The first observation is that when a self-describing number is written as an n-tuple of pairs, any permutation of these pairs is also a self-describing number.

This implies that we need only generate the sorted n-tuples of pairs that form self-describing numbers, because we can then compute their permutations to get the self-describing numbers.

The second observation is that when a non-repeating self-describing number is written as an \(n\)-tuple of pairs, the sum of the left elements of these pairs must be \(2n\).

In combinatrics, a partition of an integer \(m\) is a sorted n-tuple of positive integers such that the sum of the n-tuple is \(m\).

As an example, the partitions of \(4\) are as follows:

  • \(4\)
  • \(1,\ 3\)
  • \(2,\ 2\)
  • \(1,\ 1,\ 2\)
  • \(1,\ 1,\ 1,\ 1\)

A partition of an integer \(m\) with \(k\) parts is a partition of \(m\) of length \(k\). For example, the \(3\)-tuple \((1,\ 1,\ 2)\) is a partition of \(4\) with \(3\) parts.

When a non-repeating self-describing number in base \(b\) is written as an \(n\)-tuple of pairs, the left elements of the pairs must be a permutation of a partition of \(2n\) with \(n\) parts, and each part at most \(b-1\).

We can restrict our focus to computing only the possible partitions of \(2n\) with \(n\) parts, and each part at most \(b-1\), since we can then compute their permutations in order to find all possible \(n\)-tuples that can occur as the left elements of pairs.

Consider the non-repeating self-describing numbers in base \(10\). Any such number with \(6\) digits in base \(10\) will consist of \(3\) pairs, where the left elements of these pairs is a permutation of a partition of \(6\) with each part at most \(9\).

The partitions of \(6\) with \(3\) parts are:

  • \(1,\ 1,\ 4\)
  • \(1,\ 2,\ 3\)
  • \(2,\ 2,\ 2\)

When a non-repeating self-describing number in base \(b\) is written as an \(n\)-tuple of pairs, if a digit \(d\) exists in the \(n\)-tuple of left-elements of pairs with multiplicity \(m\), then the left element of the pair with right element \(d\) must be \(m + 1\).

This means that we can exclude certain partitions. Returning to our example of the non-repeating self-describing numbers in base \(10\) with \(6\) digits, consider those numbers where the left elements of pairs are \(1,\ 1,\ 4\). Such a number must representable as a permutation of an n-tuple of the form \([(1,\ x),\ (1,\ y),\ (4,\ z)]\). Since the digit \(1\) occurs in the \(3\)-tuple of left elements with multiplicity \(2\), we know that the left element of the pair with right element \(1\) must be \(2\). Since \(2\) does not occur in the \(3\)-tuple of left elements, we can conclude that there is no non-repeating self-describing number in base \(10\) with \(6\) digits such that the left elements are a permutation of the \(3\)-tuple \(1,\ 1,\ 4\). Similarly, we can exclude the \(3\)-tuple \(2,\ 2,\ 2\), since the digit \(2\) occurs with multiplicity \(3\), but the digit \(4\) does not occur.

How about the \(3\)-tuple \(1,\ 2,\ 3\)? Consider the numbers represented as \(3\)-tuples of the form \([(1,\ x),\ (2,\ y),\ (3,\ z)]\). Since \(1\), \(2\), and \(3\) all have multiplicity \(1\) in the left, we would require that the digit \(2\) occurs with multiplicity \(3\) in the left. Therefore, we can exclude the \(3\)-tuple \(1,\ 2,\ 3\), and conclude that there are no non-repeating self-describing numbers in base \(10\) with \(6\) digits.

We can express the above observation more generally; When a non-repeating self-describing number in base \(b\) is written as an \(n\)-tuple of pairs, if there are \(d\) digits in the \(n\)-tuple of left-elements of pairs with multiplicity \(m\), then the digit \(m + 1\) must occur with multiplicity \(d\).

Consider now the non-repeating self-describing numbers in base \(10\) with \(8\) digits. The partitions of \(8\) with \(4\) parts are:

  1. \(1,\ 1,\ 1, 5\)
  2. \(1,\ 1,\ 2, 4\)
  3. \(1,\ 1,\ 3, 3\)
  4. \(1,\ 2,\ 2, 3\)
  5. \(2,\ 2,\ 2, 2\)

We can exclude partition 1 since the digit \(1\) occurs with multiplicity \(3\), but \(4\) does not occur. We can exclude partition 2 since the digit \(1\) occurs with multiplicity \(2\), but \(3\) does not occur. We can exclude partition 5 since the digit \(2\) occurs with multiplicity \(4\), but \(5\) does not occur.

Considering partition 3, note that this partition corresponds to numbers that are permutations of the form \([(3,\ 1),\ (3,\ 3),\ (1,\ x),\ (1, y)]\), where \(x\) and \(y\) are neither \(1\) or \(3\). Indeed any permutation of this form is non-repeating self-describing in base \(10\); Examples are \(31331219\) and \(17153133\).

Considering partition 4, note that this partition corresponds to numbers that are permutations of the form \([(2,\ 1),\ (3,\ 2),\ (2,\ 3),\ (1, x)]\), where \(x\) is neither \(1\), \(2\), or \(3\). Any permutation of this form is non-repeating self-describing in base \(10\); Examples are \(23211632\) and \(32142321\).

This strategy of computing non-repeating self-describing numbers in base \(b\) with \(2n\) digits by considering the partitions of \(2n\) with \(n\) parts and each part less than \(b\) and then eliminating impossible partitions is remarkable effective. It is possible to express all of the non-repeating self-describing numbers in base \(10\) as permutations of particular forms, given only a pen and paper, and a few minutes.

In my next blog post, I’ll write a program that computes all non-repeating self-describing numbers in base \(b\), based on the algorithm expressed above.