Полиделимое число - Polydivisible number
В математике polydivisible номер (или магическое число ) является число в данной системе счисления с цифрами ABCDE ... , которая имеет следующие свойства:
- Его первая цифра а не 0.
- Число, образованное его первыми двумя цифрами ab, кратно 2.
- Число, образованное его первыми тремя цифрами abc, кратно 3.
- Число, образованное его первыми четырьмя цифрами abcd, кратно 4.
- и т.п.
Определение
Позвольте быть положительным целым числом, и позвольте быть количеством цифр в n, записанных в базе b . Число п является polydivisible числа , если для всех ,
- .
- Пример
Например, 10801 - это семизначное полиделимое число по основанию 4 , так как
Перечисление
Для любой данной базы существует только конечное число полиделимых чисел.
Максимальное полиделимое число
В следующей таблице перечислены максимальные полиделимые числа для некоторых оснований b , где A – Z представляют собой числовые значения от 10 до 35.
База | Максимальное полиделимое число ( 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 год |
Оценка для и
Позвольте быть количество цифр. Функция определяет количество полиделимых чисел с цифрами в базе , а функция - это общее количество полиделимых чисел в базе .
Если это polydivisible номер в базе с цифрами, то она может быть расширена , чтобы создать polydivisible число с цифрами , если есть число между и что делится на . Если меньше или равно , то всегда можно таким образом расширить полиделимое число цифр до полиделимого числа, и действительно может быть более одного возможного расширения. Если больше чем , не всегда возможно расширить полиделимое число таким образом, и по мере того, как становится больше, шансы на расширение данного полиделимого числа становятся меньше. В среднем каждое полиделимое число с цифрами может быть расширено до полиделимого числа с цифрами разными способами. Это приводит к следующей оценке :
Суммируя все значения n, эта оценка предполагает, что общее количество полиделимых чисел будет примерно
База | Стандартное восточное время. из | Процент ошибки | |
---|---|---|---|
2 | 2 | 59,7% | |
3 | 15 | -15,1% | |
4 | 37 | 8,64% | |
5 | 127 | −7,14% | |
10 | 20456 | -3,09% |
Конкретные базы
Все числа представлены в базе с использованием A-Z для обозначения цифровых значений от 10 до 35.
База 2
Длина n | F 2 ( п ) | Стандартное восточное время. из F 2 ( n ) | Полиделимые числа |
---|---|---|---|
1 | 1 | 1 | 1 |
2 | 1 | 1 | 10 |
База 3
Длина n | F 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 |
База 4
Длина n | F 4 ( п ) | Стандартное восточное время. из F 4 ( 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 |
База 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 5 ( п ) | Стандартное восточное время. из F 5 ( 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 10 ( n ) | Стандартное восточное время. из F 10 ( 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 число.