Номер Кейта

В развлекательной математике число Кейта или число-репфигита (сокращение от rept etive Fibonacci -like digit ) — это натуральное число в данной системе счисления с цифрами , такими, что когда последовательность создается так, что первые члены являются цифрами , а каждый последующий член является суммой предыдущих членов, является частью последовательности. Числа Кейта были введены Майком Кейтом в 1987 году. ^[1] Их вычислительно очень сложно найти, известно всего около 100. ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$

Определение

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

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

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

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

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

и для ${\displaystyle i\geq k}$

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

Если существует такое , что , то говорят, что это число Кейта . ${\displaystyle i}$ ${\displaystyle S(i)=n}$ ${\displaystyle n}$

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

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

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

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

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

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

и . ${\displaystyle S(7)=88}$

Нахождение чисел Кейта

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

Примеры

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, ... ^[4]

Другие базы

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

Числа Кейта в системе счисления с основанием 12 , записанные в системе счисления с основанием 12, следующие:

11, 15, 1Ɛ, 22, 2ᘔ, 31, 33, 44, 49, 55, 62, 66, 77, 88, 93, 99, ᘔᘔ, ƐƐ, 125, 215, 24ᘔ, 405, 42ᘔ, 654, 80ᘔ, 8ᘔ3, ᘔ59, 1022, 1662, 2044, 3066, 4088, 4ᘔ1ᘔ, 4ᘔƐ1, 50ᘔᘔ, 8538, Ɛ18Ɛ, 17256, 18671, 24ᘔ78, 4718Ɛ, 517Ɛᘔ, 157617, 1ᘔ265ᘔ, 5ᘔ4074, 5ᘔƐ140, 6Ɛ1449, 6Ɛ8515, ...

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

Кит кластеры

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

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

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

def  is_repfigit ( x :  int ,  b :  int )  ->  bool : """Определяет, является ли число в определенной системе счисления числом Кейта.""" if x == 0 : return True        последовательность  =  []  у  =  х пока  y  >  0 :  последовательность.append ( y % b ) y = y // b​​        digit_count  =  len ( последовательность )  последовательность.reverse ( )​ пока  последовательность [ len ( последовательность )  -  1 ]  <  x :  n  =  0  для  i  в  диапазоне ( 0 ,  digit_count ):  n  =  n  +  последовательность [ len ( последовательность )  -  digit_count  +  i ]  последовательность . append ( n ) обратная  последовательность [ len ( последовательность )  -  1 ]  ==  x

Смотрите также

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

Ссылки

1. Кит, Майк (1987). «Числа Repfigit». Журнал занимательной математики . 19 (2): 41–42.
2. Эрлз, Джейсон ; Лихтблау, Даниэль; Вайсштейн, Эрик В. «Кит Номер». Математический мир .
3. Кит, Майк . «Числа Кита».
4. Слоан, Н. Дж. А. (ред.). "Последовательность A007629 (Repfigit (REPetitive FIbonacci-like) diGIT) числа (или числа Кейта))". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
5. Коупленд, Эд. "14 197 и другие числа Кита". Numberphile . Брэди Харан . Архивировано из оригинала 2017-05-22 . Получено 2013-04-09 .