View source for Self-descriptive number

{{Short description|Integer describing itself}}
{{Use dmy dates|date=May 2020}}
{{No footnotes|date=April 2015}}
In [[mathematics]], a '''self-descriptive number''' is an [[integer]] ''m'' in a given [[radix|base]] ''b'' that is ''b'' [[Numerical digit|digit]]s long, and 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;<br />
It contains 6 at position 0, indicating that there are six 0s in 6210001000;<br />
It contains 2 at position 1, indicating that there are two 1s in 6210001000;<br />
It contains 1 at position 2, indicating that there is one 2 in 6210001000;<br />
It contains 0 at position 3, indicating that there is no 3 in 6210001000;<br />
It contains 0 at position 4, indicating that there is no 4 in 6210001000;<br />
It contains 0 at position 5, indicating that there is no 5 in 6210001000;<br />
It contains 1 at position 6, indicating that there is one 6 in 6210001000;<br />
It contains 0 at position 7, indicating that there is no 7 in 6210001000;<br />
It contains 0 at position 8, indicating that there is no 8 in 6210001000;<br />
It contains 0 at position 9, indicating that there is no 9 in 6210001000.<br />
<!-- 'Because it has six 0s, two 1s, one 2, one 6, and no 3s, 4s, 5s, 7s, 8s or 9s,' is not a reason. It doesn't answer why this is a self-descriptive number. It only tells you what digit it contains and how many. It doesn't tell you why at all. -->

==In different bases==
There are no self-descriptive numbers in bases 2, 3 or 6. In bases 7 and greater, there is exactly one self-descriptive number: <math>(b - 4)b^{b-1} + 2b^{b-2} + b^{b-3} + b^3</math>, 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:

{| class="wikitable"
!Base
!Self-descriptive numbers {{OEIS|id=A138480}}
!Values in base 10 {{OEIS|id=A108551}}
|-
|4
|1210, 2020
|[[100 (number)|100]], [[136 (number)|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<br>([[Ellipsis]] omits 23 zeroes)
|Approx. 9.4733 &times; 10<sup>55</sup>
|-
|...
|...
|...
|}

==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. e.g. in base 10, 3211000 has 3 zeros, 2 ones, 1 two, and 1 three.  Note that this depends on being allowed to include as many trailing zeros as suit, without them adding any further information about the other present digits.

Because leading zeros are not written down, every autobiographical number contains at least one zero, so that its first digit is nonzero.

Considering a hypothetical case where the digits are treated in the opposite order: the units is the count of zeros, the 10s the count of ones, and so on, there are no such self-describing numbers.  Attempts to construct one result in an explosive requirement to add more and more digits.

== References ==
* {{cite book |first= Clifford |last= Pickover |title= Keys to Infinity |chapter= Chapter 28, Chaos in Ontario |location= New York |publisher= Wiley |pages= [https://archive.org/details/keystoinfinity00clif/page/217 217–219] |date= 1995 |isbn= 978-0471118572 |chapter-url-access= registration |chapter-url= https://archive.org/details/keystoinfinity00clif/page/217 }} 
* {{MathWorld|title=Self-Descriptive Number|urlname=Self-DescriptiveNumber}}
* {{Cite OEIS|sequencenumber=A108551|name=Self-descriptive numbers in various bases }}
* {{Cite OEIS|sequencenumber=A046043|name=Autobiographical numbers}}
* {{Citation|url=http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=881|title=Autobiographical Numbers|last1=Khovanova |first1=Tanya |year=2008 |arxiv=0803.0270 }}

== External links ==
* {{cite web |url= https://ed.ted.com/lessons/can-you-solve-the-leonardo-da-vinci-riddle-tanya-khovanova |publisher= TED-Ed |work= Lesson about autobiographical numbers |title= Can You Solve the Leonardo da Vinci Riddle? |first= Tanya |last= Khovanova |date= 23 August 2018 }} <!-- -aka- {{youtube|lRfdMiURV4s}} -->

{{Classes of natural numbers}}

[[Category:Base-dependent integer sequences]]