Самоописывающиеся числа в математике: определение, свойства и примеры в разных системах счисления. Редкие числа, где каждая цифра указывает её количество.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В математике самоописывающее число — это целое число m, которое в заданной системе счисления с основанием b имеет длину b цифр, при этом каждая цифра d в позиции n (начиная с 0 для самой старшей цифры и заканчивая b−1 для самой младшей) указывает, сколько раз цифра n встречается в числе m.
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.
На разных основаниях
В базах 2, 3 или 6 нет самоописательных чисел. В основаниях 7 и выше существует ровно одно самоописательное число, которое содержит b−4 цифр 0, две цифры 1, одну цифру 2, одну цифру b – 4 и не содержит других цифр. В следующей таблице приведены некоторые самоописательные числа для нескольких выбранных оснований:
There are no self descriptive numbers in bases 2, 3 or 6. In bases 7 and greater, there is exactly one self descriptive number: , 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:
Основание Самоописательные числа Значения в десятичной системе
4 1210 16
10 2020 2020
12 136521200 14257321
16 117210000 18649222
20 225331310 78011282
22 1000001000 100060730
36 W21000 (Эллипсис опускает 23 нуля) Приблизительно 9.4733 × 10⁵⁵
BaseSelf descriptive numbers Values in base 10 41210, 2020100, 1365212001425732110003893058421010008946176952100100022533171310621000100062100010001172100001000186492227801128210000010006073061476032 16C21000000000100013983676842985394176 36W21000 0001000(Ellipsis omits 23 zeroes)Approx. 9.4733 × 1055
Свойства
Из чисел, перечисленных в таблице, следует, что сумма цифр каждого самоописательного числа равна его основанию, и что эти числа кратны этому основанию. Первый факт тривиально вытекает из определения самоописательного числа: сумма цифр равна общему количеству цифр, которое, по определению, равно основанию. Тот факт, что самоописательное число в основании *b* должно быть кратно этому основанию (или, что эквивалентно, последняя цифра самоописательного числа должна быть 0), можно доказать от противного: предположим, что существует самоописательное число *m* в основании *b*, состоящее из *b* цифр, но не кратное *b*. Цифра в позиции *b* – 1 должна быть не меньше 1, что означает, что в числе *m* есть хотя бы одна цифра *b* – 1. В любой позиции *x*, где встречается цифра *b* – 1, должно быть не менее *b* – 1 экземпляров цифры *x* в *m*. Следовательно, в *m* есть хотя бы одна цифра 1 и не менее *b* – 1 цифр *x*. Если *x* > 1, то число *m* содержит больше, чем *b* цифр, что противоречит нашему исходному предположению. И если *x* = 0 или 1, это также приводит к противоречию. Таким образом, самоописательное число в основании *b* является числом Харшада в основании *b*.
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.
Автобиографические номера
Обобщение самоописательных чисел, называемых автобиографическими числами, допускает использование меньшего количества цифр, чем основание системы счисления, при условии, что включенных в число цифр достаточно для его полного описания. Например, в десятичной системе счисления число 3211000 содержит три нуля, две единицы, одну двойку и одну тройку. Важно отметить, что это возможно благодаря разрешению включать любое количество конечных нулей, не добавляя при этом дополнительной информации о других присутствующих цифрах. Поскольку ведущие нули не записываются, каждое автобиографическое число содержит как минимум один ноль, поэтому его первая цифра не равна нулю. Если же рассматривать гипотетический случай, когда цифры интерпретируются в обратном порядке – цифра в разряде единиц указывает количество нулей, цифра в разряде десятков – количество единиц, и так далее – то самоописательных чисел не существует. Попытки их построить приводят к экспоненциально возрастающей необходимости добавлять все больше и больше цифр.
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.