Полиделимое число - Polydivisible number

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

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

Определение

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

{\ 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}$

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

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

База ${\ displaystyle b}$	Максимальное полиделимое число ( OEIS : A109032 )	Количество цифр в основании b ( OEIS : A109783 )
2	$102$	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 год

Оценка для и ${\ Displaystyle F_ {b} (п)}$ ${\ displaystyle \ Sigma (b)}$

График количества -разрядных полиделимых чисел по основанию 10 в сравнении с оценкой

{\ displaystyle n}

{\ Displaystyle F_ {10} (п)}

{\ Displaystyle F_ {10} (п)}

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

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

{\ displaystyle F_ {b} (n) \ приблизительно (b-1) {\ frac {b ^ {n-1}} {n!}}.}

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

{\ Displaystyle \ Sigma (b) \ приблизительно {\ гидроразрыва {b-1} {b}} (e ^ {b} -1)}

База ${\ displaystyle b}$	${\ displaystyle \ Sigma (b)}$	Стандартное восточное время. из ${\ displaystyle \ Sigma (b)}$	Процент ошибки
2	2	${\ displaystyle {\ frac {e ^ {2} -1} {2}} \ приблизительно 3,1945}$	59,7%
3	15	${\ displaystyle {\ frac {2} {3}} (e ^ {3} -1) \ приблизительно 12,725}$	-15,1%
4	37	${\ displaystyle {\ frac {3} {4}} (e ^ {4} -1) \ приблизительно 40,199}$	8,64%
5	127	${\ displaystyle {\ frac {4} {5}} (e ^ {5} -1) \ приблизительно 117,93}$	−7,14%
10	20456	${\ displaystyle {\ frac {9} {10}} (e ^ {10} -1) \ приблизительно 19823}$	-3,09%

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

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

База 2

Длина n	F ₂ ( п )	Стандартное восточное время. из F ₂ ( n )	Полиделимые числа
1	1	1	1
2	1	1	10

База 3

Длина n	F ₃ ( п )	Стандартное восточное время. из F ₃ ( 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

Длина n	F ₄ ( п )	Стандартное восточное время. из F ₄ ( n )	Полиделимые числа
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

Полиделимые числа в базе 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, 201102000, 204021, 20203 2424024, 3113002, 3140000, 3144021, 4022042, 4211020, 4431024, 11330000, 13220431, 20110211, 20420404, 24200031, 31400004, 31440211, 40220422, 42110202, 44310242, 132204310422, 42110202, 44310242, 132104310424001, 201202102, 44310242, 132104310424001 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 ...

Длина n	F ₅ ( п )	Стандартное восточное время. из F ₅ ( n )
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, ... (последовательность A144688 в OEIS )

Наименьшие полиделимые числа по основанию 10 с n цифрами равны

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

Наибольшие полиделимые числа по основанию 10 с n цифрами равны

9, 98, 987, 9876, 98765, 987654, 9876545, 98765456, 987654564, 9876545640, 98765456405, 987606963096, 9876069630960, 98760696309604, 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, ... (последовательность A143671 в OEIS )

Длина n	F ₁₀ ( n )	Стандартное восточное время. из F ₁₀ ( n )
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 = []
    for i in range(1, base):
        previous.append(i)
    new = []
    digits = 2
    while not previous == []:
        numbers.append(previous)
        for i in range(0, len(previous)):
            for j in range(0, base):
                number = previous[i] * base + j
                if number % digits == 0:
                    new.append(number)
        previous = new
        new = []
        digits = digits + 1
    return numbers

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

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

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

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

381 654 729

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

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

48 000 688 208 466 084 040

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

30 000 600 003

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

использованная литература

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

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

Languages

In other projects

Полиделимое число - Polydivisible number

СОДЕРЖАНИЕ

Определение