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

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

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

Определение

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

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

Пример

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

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

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

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

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

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

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

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

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

Для любой заданной базы $b$, существует только конечное число многоделимых чисел.

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

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

База $b$	Максимальное кратное число ( 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	25
12	6068 903468 50BA68 00B036 206464 12	28

Оценка для F _b ( n ) и Σ ( b )

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

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

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

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

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

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

База $b$	$\Sigma (b)$	Восток. из $\Sigma (b)$	Процентная ошибка
2	2	${\frac {e^{2}-1}{2}}\approx 3.1945$	59.7%
3	15	${\frac {2}{3}}(e^{3}-1)\approx 12.725$	-15.1%
4	37	${\frac {3}{4}}(e^{4}-1)\approx 40.199$	8.64%
5	127	${\frac {4}{5}}(e^{5}-1)\approx 117.93$	−7.14%
10	20456	${\frac {9}{10}}(e^{10}-1)\approx 19823$	-3.09%

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

Все числа представлены в базе $b$, используя A-Z для представления цифр от 10 до 35.

База 2

Длина н	Ф 2 ( п )	Восток. F2 ​ ( n )	Многократные числа
1	1	1	1
2	1	1	10

База 3

Длина н	F 3 ( n )	Est. of 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	$\varnothing$

База 4

Длина н	Ф 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	$\varnothing$

База 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, 4022, 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, 402204220, 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, нет...

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

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

Длина н	F5 ) ( н	Восток. F 5 ( п )
1	4	4
2	10	10
3	17	17
4	21	21
5	21	21
6	21	17
7	13	12
8	10	8
9	6	4
10	4	2

База 10

Многократные числа по основанию 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, 10200616206046, 102006162060465, 1020061620604656, 10200616206046568, 108054801036000018, 1080548010360000180, 10805480103600001800, ... (sequence A214437 in the OEIS)

Наибольшие числа, делящиеся по основанию 10, состоящие из n цифр:

9, 98, 987, 9876, 98765, 987654, 9876545, 98765456, 987654564, 9876545640, 98765456405, 987606963096, 9876069630960, 98760696309604, 987606963096045, 9876062430364208, 98485872309636009, 984450645096105672, 9812523240364656789, 96685896604836004260, ... (sequence A225608 in the OEIS)

Число кратных десятичных чисел с 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, ... (последовательность A143671 в OEIS )

Длина н	F 10 ( n )	Восток. F 10 ( н )
1	9	9
2	45	45
3	150	150
4	375	375
5	750	750
6	1200	1250
7	1713	1786
8	2227	2232
9	2492	2480
10	2492	2480
11	2225	2255
12	2041	1879
13	1575	1445
14	1132	1032
15	770	688
16	571	430
17	335	253
18	180	141
19	90	74
20	44	37
21	18	17
22	12	8
23	6	3
24	3	1
25	1	1

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

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

def find_polydivisible(base: int) -> list[int]:
    """Find polydivisible number."""
    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

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

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

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

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

381 654 729

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

• Нахождение многоделимых чисел с дополнительными ограничениями на цифры - например, самое длинное многоделимое число, в котором используются только четные цифры, - это

48 000 688 208 466 084 040

• Нахождение палиндромных многоделимых чисел - например, самое длинное палиндромное многоделимое число - это

30 000 600 003

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

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

• YouTube — панцифровое число, которое к тому же делится на несколько частей.