Self-descriptive number

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

For example, in base 10, the number 6210001000 is self-descriptive because of the following reasons:

In base 10, the number has 10 digits, indicating its base;
It contains 6 at position 0, indicating that there are six 0s in 6210001000;
It contains 2 at position 1, indicating that there are two 1s in 6210001000;
It contains 1 at position 2, indicating that there is one 2 in 6210001000;
It contains 0 at position 3, indicating that there is no 3 in 6210001000;
It contains 0 at position 4, indicating that there is no 4 in 6210001000;
It contains 0 at position 5, indicating that there is no 5 in 6210001000;
It contains 1 at position 6, indicating that there is one 6 in 6210001000;
It contains 0 at position 7, indicating that there is no 7 in 6210001000;
It contains 0 at position 8, indicating that there is no 8 in 6210001000;
It contains 0 at position 9, indicating that there is no 9 in 6210001000.

In different bases

There are no self-descriptive numbers in bases 1, 2, 3 or 6. In bases 7 and above, there is, if nothing else, a self-descriptive number of the form (b - 4)b^{b - 1} + 2b^{b - 2} + b^{b - 3} + b^3, which has b - 4 instances of the digit 0, two instances of the digit 1, one instance of the digit 2, one instance of digit b - 4, and no instances of any other digits. The following table lists some self-descriptive numbers in a few selected bases:

Base Self-descriptive numbers (sequence A138480 in OEIS) Values in base 10 (sequence A108551 in OEIS)
4 1210, 2020 100, 136
5 21200 1425
7 3211000 389305
8 42101000 8946176
9 521001000 225331713
10 6210001000 6210001000
11 72100001000 186492227801
12 821000001000 6073061476032
... ... ...
16 C210000000001000 13983676842985394176
... ... ...
36 W21000...0001000
(Ellipsis omits 23 zeroes)
Approx. 2.14349 × 1053
... ... ...

Properties

From the numbers listed in the table, it would seem that all self-descriptive numbers have digit sums equal to their base, and that they're multiples of that base. The first fact follows trivially from the fact that the digit sum equals the total number of digits, which is equal to the base, from the definition of self-descriptive number.

That a self-descriptive number in base b must be a multiple of that base (or equivalently, that the last digit of the self-descriptive number must be 0) can be proven by contradiction as follows: assume that there is in fact a self-descriptive number m in base b that is b-digits long but not a multiple of b. The digit at position b - 1 must be at least 1, meaning that there is at least one instance of the digit b - 1 in m. At whatever position x that digit b - 1 falls, there must be at least b - 1 instances of digit x in m. Therefore, we have at least one instance of the digit 1, and b - 1 instances of x. If x > 1, then m has more than b digits, leading to a contradiction of our initial statement. And if x = 0 or 1, that also leads to a contradiction.

It follows that a self-descriptive number in base b is a Harshad number in base b.

Autobiographical numbers

A generalization of the self-descriptive numbers, called the autobiographical numbers, allow fewer digits than the base, as long as the digits that are included in the number suffice to completely describe it.

References

This article is issued from Wikipedia - version of the Monday, January 11, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.