Номер Кита

Эта статья о концепции математики. О политической концепции см. « Обратный отсчет с Китом Ольберманном» .

В развлекательной математике число Кита или число повторений (сокращение от повторяющейся цифры ) типа Фибоначчи . натуральное представляет собой число $n$ в заданной системе счисления $b$ с $k$ цифры такие, что при создании последовательности такая, что первая $k$ условия - это $k$ цифры $n$ и каждое последующее слагаемое представляет собой сумму предыдущих $k$ условия, $n$ является частью последовательности. Числа Кита были введены Майком Китом в 1987 году. Их очень сложно найти с вычислительной точки зрения, известно всего около 100.

Определение

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

$d_{i}={\frac {n{\bmod {b}}^{i+1}-n{\bmod {b}}^{i}}{b^{i}}}$

быть значением каждой цифры $n$.

Определим последовательность $S(i)$ по линейному рекуррентному соотношению . Для $0\leq i<k$,

$S(i)=d_{k-i-1}$

и для $i\geq k$

$S(i)=\sum _{j=0}^{k}S(i-k+j)$

Если существует $i$ такой, что $S(i)=n$, затем $n$ Говорят, что это число Кита .

Например, 88 — это число Кита по основанию 6 , так как

$S(0)=d_{3-0-1}=d_{2}={\frac {88{\bmod {6}}^{2+1}-88{\bmod {6}}^{2}}{6^{2}}}={\frac {88{\bmod {2}}16-88{\bmod {3}}6}{36}}={\frac {88-16}{36}}={\frac {72}{36}}=2$

$S(1)=d_{3-1-1}=d_{1}={\frac {88{\bmod {6}}^{1+1}-88{\bmod {6}}^{1}}{6^{1}}}={\frac {88{\bmod {3}}6-88{\bmod {6}}}{6}}={\frac {16-4}{6}}={\frac {12}{6}}=2$

$S(2)=d_{3-2-1}=d_{0}={\frac {88{\bmod {6}}^{0+1}-88{\bmod {6}}^{0}}{6^{0}}}={\frac {88{\bmod {6}}-88{\bmod {1}}}{1}}={\frac {4-0}{1}}={\frac {4}{1}}=4$

и вся последовательность

$S(i)=\{2,2,4,8,14,26,48,88,162,\ldots \}$

и $S(7)=88$.

7 чисел

Существует ли бесконечно много чисел Кита в определенной базе. $b$ в настоящее время является предметом спекуляций. Числа Кита редки, и их трудно найти. Их можно найти перебором, и более эффективного алгоритма не известно. По словам Кита, в основанию 10 среднем по $\textstyle {\frac {9}{10}}\log _{2}{10}\approx 2.99$ Числа Кита ожидаются между последовательными степенями 10 . Известные результаты, кажется, подтверждают это.

Примеры

14 , 19 , 28 , 47 , 61 , 75 , 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909, 31331, 34285, 34348, 55604, 62662, 86935, 93993, 120284, 129106, 147640, 156146, 174680, 183186, 298320, 355419, 694280, 925993, 1084051, 7913837, 11436171, 33445755, 44121607, 129572008, 251133297, ...

Другие базы

В системе счисления 2 существует метод построения всех чисел Кита.

Числа Кита по основанию 12 , записанные по основанию 12, равны

11, 15, 1Е, 22, 2Е, 31, 33, 44, 49, 55, 62, 66, 77, 88, 93, 99, ЕЕ, 125, 215, 24Е, 8, 0 4 4 8В3, ϔ59, 1022 , 1662, 2044, 3066, 4088, 4ϔ1ϔ, 4ϔA1, 50ϔϔ, 8538, E18E, 17251, 8ϔ 8,7 184641 157617, 1U265BO, 5U4074, 5UA140, 6A1449, 6 А8515, ...

где ᘔ представляет собой 10, а Ɛ представляет собой 11.

Кит Кластерс

Кластер Кита — это связанный набор чисел Кита, одно из которых кратно другому. Например, в базе 10 , $\{14,28\}$, $\{1104,2208\}$, и $\{31331,62662,93993\}$ все являются кластерами Кита. Возможно, это единственные три примера кластера Кита с основанием 10 .

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

В приведенном ниже примере реализуется последовательность, определенная выше в Python, для определения того, является ли число в определенной базе числом Кита:

def is_repfigit(x: int, b: int) -> bool:    """Determine if a number in a particular base is a Keith number."""    if x == 0:        return True    sequence = []    y = x    while y > 0:        sequence.append(y % b)        y = y // b    digit_count = len(sequence)    sequence.reverse()    while sequence[len(sequence) - 1] < x:        n = 0        for i in range(0, digit_count):            n = n + sequence[len(sequence) - digit_count + i]        sequence.append(n)    return sequence[len(sequence) - 1] == x

См. также

• Арифметическая динамика
• Число Фибоначчи
• Линейное рекуррентное соотношение