Многократное число

Число, первые n цифр которого кратны n

В математике многократным числом (или магическим числом ) называется число в данной системе счисления с цифрами abcde..., которое обладает следующими свойствами: ^[1]

1. Его первая цифра a не равна 0.
2. Число, образованное первыми двумя цифрами ab , кратно 2.
3. Число, образованное первыми тремя цифрами abc , кратно 3.
4. Число, образованное первыми четырьмя цифрами abcd , кратно 4.
5. и т. д.

Определение

Пусть будет положительным целым числом, и пусть будет числом цифр в числе n, записанном в системе счисления с основанием b . Число n является полиделимым числом, если для всех , ${\displaystyle n}$ ${\displaystyle k=\lfloor \log _{b}{n}\rfloor +1}$ ${\displaystyle 1\leq i\leq k}$

${\displaystyle \left\lfloor {\frac {n}{b^{k-i}}}\right\rfloor \equiv 0{\pmod {i}}}$.

Пример

Например, 10801 — это семизначное полиделимое число в системе счисления с основанием 4 , как

${\displaystyle \left\lfloor {\frac {10801}{4^{7-1}}}\right\rfloor =\left\lfloor {\frac {10801}{4096}}\right\rfloor =2\equiv 0{\pmod {1}},}$

${\displaystyle \left\lfloor {\frac {10801}{4^{7-2}}}\right\rfloor =\left\lfloor {\frac {10801}{1024}}\right\rfloor =10\equiv 0{\pmod {2}},}$

${\displaystyle \left\lfloor {\frac {10801}{4^{7-3}}}\right\rfloor =\left\lfloor {\frac {10801}{256}}\right\rfloor =42\equiv 0{\pmod {3}},}$

${\displaystyle \left\lfloor {\frac {10801}{4^{7-4}}}\right\rfloor =\left\lfloor {\frac {10801}{64}}\right\rfloor =168\equiv 0{\pmod {4}},}$

${\displaystyle \left\lfloor {\frac {10801}{4^{7-5}}}\right\rfloor =\left\lfloor {\frac {10801}{16}}\right\rfloor =675\equiv 0{\pmod {5}},}$

${\displaystyle \left\lfloor {\frac {10801}{4^{7-6}}}\right\rfloor =\left\lfloor {\frac {10801}{4}}\right\rfloor =2700\equiv 0{\pmod {6}},}$

${\displaystyle \left\lfloor {\frac {10801}{4^{7-7}}}\right\rfloor =\left\lfloor {\frac {10801}{1}}\right\rfloor =10801\equiv 0{\pmod {7}}.}$

Перечисление

Для любого данного основания существует лишь конечное число многократных чисел. ${\displaystyle b}$

Максимальное полиделимое число

В следующей таблице перечислены максимальные многократные числа для некоторых оснований b , где A−Z представляют цифровые значения от 10 до 35.

Оценка дляФ б(н) и Σ(б)

График количества -значных многократных чисел в десятичной системе счисления по сравнению с оценкой ${\displaystyle n}$ ${\displaystyle F_{10}(n)}$ ${\displaystyle F_{10}(n)}$

Пусть будет числом цифр. Функция определяет число многократных чисел, имеющих цифры в системе счисления с основанием , а функция — общее число многократных чисел в системе счисления с основанием . ${\displaystyle n}$ ${\displaystyle F_{b}(n)}$ ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle \Sigma (b)}$ ${\displaystyle b}$

Если — полиделимое число в системе счисления с цифрами, то его можно расширить, чтобы создать полиделимое число с цифрами, если существует число между и , которое делится на . Если меньше или равно , то всегда можно расширить полиделимое число с цифрами до полиделимого числа с цифрами таким образом, и действительно может быть более одного возможного расширения. Если больше , не всегда можно расширить полиделимое число таким образом, и по мере увеличения шансы расширить данное полиделимое число уменьшаются. В среднем каждое полиделимое число с цифрами можно расширить до полиделимого числа с цифрами разными способами. Это приводит к следующей оценке для : ${\displaystyle k}$ ${\displaystyle b}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle bk}$ ${\displaystyle b(k+1)-1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle {\frac {b}{n}}}$ ${\displaystyle F_{b}(n)}$

${\displaystyle F_{b}(n)\approx (b-1){\frac {b^{n-1}}{n!}}.}$

Суммируя по всем значениям n, эта оценка предполагает, что общее число многократных чисел будет приблизительно равно

${\displaystyle \Sigma (b)\approx {\frac {b-1}{b}}(e^{b}-1)}$

Конкретные базы

Все числа представлены в системе счисления , в которой для обозначения цифровых значений от 10 до 35 используются буквы A−Z. ${\displaystyle b}$

База 2

База 3

База 4

База 5

Многократно делимые числа в системе счисления с основанием 5:

1, 2, 3, 4, 11, 13, 20, 22, 24, 31, 33, 40, 42, 44, 110, 113, 132, 201, 204, 220, 223, 242, 311, 314, 330, 333, 402, 421, 424, 440, 443, 1102, 1133, 1322, 2011, 2042, 2200, 2204, 2231, 2420, 2424, 3113, 3140, 3144, 3302, 3333, 40 22, 4211, 4242, 4400, 4404, 4431, 11020, 11330, 13220, 20110, 20420, 22000, 22040, 22310, 24200, 24240, 31130, 31400, 31440, 33020, 33330, 40220, 42110, 42420, 44000, 44040, 44310, 110204, 113300, 132204, 201102, 204204, 220000, 220402, 223102, 242000, 242402, 311300, 314000, 314402, 330204, 333300, 402204, 421102, 424204, 440000, 440402, 443102, 1133000, 1322043, 2011021, 2042040, 2204020, 2420003, 2424024, 3113002, 3140000, 3144021, 4022042, 4211020, 4431024, 11330000, 13220431, 20110211, 20420404, 24200031, 31400004, 31440211, 40220422, 42110202, 44310242, 132204314, 201102110, 242000311, 314000044, 40220422 0, 443102421, 1322043140, 2011021100, 3140000440, 4022042200

Наименьшие полиделимые числа с основанием 5, состоящие из n цифр, — это

1, 11, 110, 1102, 11020, 110204, 1133000, 11330000, 132204314, 1322043140, нет...

Наибольшие полиделимые числа с основанием 5, состоящие из n цифр, — это

4, 44, 443, 4431, 44310, 443102, 4431024, 44310242, 443102421, 4022042200, нет...

Число поликратных чисел с основанием 5, состоящих из n цифр, равно

4, 10, 17, 21, 21, 21, 13, 10, 6, 4, 0, 0, 0...

База 10

Многократно делимые числа в десятичной системе счисления:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 102, 105, 108, 120, 123, 126, 129, 141, 144, 147, 162, 165, 168, 180, 183, 186, 189, 201, 204, 207, 222, 225, 228, 243, 246, 249, 261, 264, 267, 282, 285, 288. .. (последовательность A144688 в OEIS )

Наименьшие полиделимые числа с основанием 10, состоящие из n цифр, — это

1, 10, 102, 1020, 10200, 102000, 1020005, 10200056, 102000564, 1020005640, 10200056405, 102006162060, 1020061620604, 10200 616206046, 102006162060465, 1020061620604656, 10200616206046568, 108054801036000018, 1080548010360000180, 10805480103600001800, ... (последовательность A214437 в OEIS )

Наибольшие поликратные числа с основанием 10, состоящие из n цифр, — это

9, 98, 987, 9876, 98765, 987654, 9876545, 98765456, 987654564, 9876545640, 98765456405, 987606963096, 9876069630960, 98760 696309604, 987606963096045, 9876062430364208, 98485872309636009, 984450645096105672, 9812523240364656789, 96685896604836004260, ... (последовательность A225608 в OEIS )

Число поликратных чисел с основанием 10, состоящих из n цифр, равно

9, 45, 150, 375, 750, 1200, 1713, 2227, 2492, 2492, 2225, 2041, 1575, 1132, 770, 571, 335, 180, 90, 44, 18, 12, 6, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... (последовательность A143671 в OEIS )

Пример программирования

В приведенном ниже примере выполняется поиск многократных чисел в Python .

def  find_polydivisible ( base :  int )  ->  list [ int ]: """Найти многократные числа.""" numbers = [] previous = [ i for i in range ( 1 , base )] new = [] digits = 2 while not previous == []: numbers . append ( previous ) for n in previous : for j in range ( 0 , base ): number = n * base + j if number % digits == 0 : new . append ( number ) previous = new new = [] digits = digits + 1 return numbers                                                            

Связанные проблемы

Многократно делимые числа представляют собой обобщение следующей известной ^[2] задачи в занимательной математике :

Расположите цифры от 1 до 9 в таком порядке, чтобы первые две цифры образовали число, кратное 2, первые три цифры образовали число, кратное 3, первые четыре цифры образовали число, кратное 4 и т. д., и, наконец, все число стало кратным 9.

Решением задачи является девятизначное полиделимое число с дополнительным условием, что оно содержит цифры от 1 до 9 ровно по одному разу. Существует 2492 девятизначных полиделимых числа, но единственное, которое удовлетворяет дополнительному условию, это

381 654 729 ^[6]

Другие проблемы, связанные с многократными числами, включают в себя:

• Поиск многократных чисел с дополнительными ограничениями на цифры — например, самое длинное многократный число, которое использует только четные цифры, это

48 000 688 208 466 084 040

• Поиск палиндромных многоделимых чисел — например, самое длинное палиндромное многоделимое число —

30 000 600 003

• Обычным, тривиальным расширением вышеупомянутого примера является расстановка цифр от 0 до 9 для получения 10-значного числа таким же образом; результатом будет 3816547290. Это панцифровое полиделимое число.

Ссылки

1. Де, Молой, МАТЕМАТИКА, ХОТИТЕ ВЕРИТЬ, ХОТИТЕ НЕТ
2. Parker, Matt (2014), «Вы можете оцифровать?», Что делать и делать в четвертом измерении , Отдельные книги, стр. 7–8, ISBN 9780374275655– через Google Книги
3. Уэллс, Дэвид (1986), Словарь любопытных и интересных чисел Penguin, Penguin Books, стр. 197, ISBN 9780140261493– через Google Книги
4. Лайнс, Малкольм (1986), «Как заканчиваются эти серии?», Номер для ваших мыслей , Taylor and Francis Group, стр. 90, ISBN 9780852744956
5. (последовательность A143671 в OEIS )
6. Ланье, Сьюзи, Девятизначное число

Внешние ссылки

• YouTube — панцифровое число, которое также является многократным