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

Для проверки этой статьи нужны дополнительные цитаты . Помогите улучшить эту статью , добавив ссылки на надежные источники . Материалы без источников могут быть оспорены и удалены. Найти источники:  «Polydivisible number» – новости  · газеты  · книги  · ученый  · JSTOR ( октябрь 2018 г. ) ( Узнайте, как и когда удалять это сообщение )

В математике многократным числом (или магическим числом ) называется число в данной системе счисления с цифрами 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^{ki}}}\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 , где A−Z представляют цифровые значения от 10 до 35.

База${\displaystyle б}$	Максимальное полиделимое число ( OEIS : A109032 )	Количество цифр в системе счисления с основанием b ( OEIS : A109783 )
2	10 2	2
3	20 0220 3	6
4	222 0301 4	7
5	40220 42200 5	10
10	36085 28850 36840 07860 36725 [2] [3] [4]	25
12	6068 903468 50BA68 00B036 206464 12	28

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

Если — полиделимое число в системе счисления с цифрами, то его можно расширить, чтобы создать полиделимое число с цифрами, если существует число между и , которое делится на . Если меньше или равно , то всегда можно расширить полиделимое число с цифрами до полиделимого числа с цифрами таким образом, и действительно может быть более одного возможного расширения. Если больше , не всегда можно расширить полиделимое число таким образом, и по мере увеличения шансы расширить данное полиделимое число уменьшаются. В среднем каждое полиделимое число с цифрами можно расширить до полиделимого числа с цифрами разными способами. Это приводит к следующей оценке для :${\displaystyle к}$${\displaystyle б}$${\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)}$

База${\displaystyle b}$	${\displaystyle \Sigma (b)}$	Оценка${\displaystyle \Sigma (b)}$	Процент ошибки
2	2	${\displaystyle {\frac {e^{2}-1}{2}}\approx 3.1945}$	59,7%
3	15	${\displaystyle {\frac {2}{3}}(e^{3}-1)\approx 12.725}$	-15,1%
4	37	${\displaystyle {\frac {3}{4}}(e^{4}-1)\approx 40.199}$	8,64%
5	127	${\displaystyle {\frac {4}{5}}(e^{5}-1)\approx 117.93}$	−7,14%
10	20456 [2]	${\displaystyle {\frac {9}{10}}(e^{10}-1)\approx 19823}$	-3,09%

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

Длина н	Ф 3 ( н )	Оценка F 3 ( n )	Многократно делимые числа
1	2	2	1, 2
2	3	3	11, 20, 22
3	3	3	110, 200, 220
4	3	2	1100, 2002, 2200
5	2	1	11002, 20022
6	2	1	110020, 200220
7	0	0	${\displaystyle \varnothing }$

Длина н	Ф 4 ( н )	Оценка F 4 ( н )	Многократно делимые числа
1	3	3	1, 2, 3
2	6	6	10, 12, 20, 22, 30, 32
3	8	8	102, 120, 123, 201, 222, 300, 303, 321
4	8	8	1020, 1200, 1230, 2010, 2220, 3000, 3030, 3210
5	7	6	10202, 12001, 12303, 20102, 22203, 30002, 32103
6	4	4	120012, 123030, 222030, 321030
7	1	2	2220301
8	0	1	${\displaystyle \varnothing }$

Многократно делимые числа в системе счисления с основанием 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...

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

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. Это панцифровое полиделимое число.

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