Номер Кита

В теории чисел , А число Кита или repfigit номер (сокращенно повторение etitive Р ibonacci типа д ИГИТА ) представляет собой натуральное число в данной системе счисления с цифрами таким образом, что , когда последовательность создана таким образом, что первые терминами являются цифрами и каждый последующий член является суммой предыдущих членов, является частью последовательности. Числа Кита были введены Майком Кейтом в 1987 году. ^[1] Их очень сложно найти в вычислительном отношении, известно всего около 100. ${\ displaystyle n}$ ${\ displaystyle b}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle n}$

Определение [ править ]

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

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

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

Определим линейное рекуррентное отношение такое, что при , ${\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 ожидаются в среднем числа Кейта между последовательными степенями 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Ɛ1514 ...

Кейт Кластерс [ править ]

Кластер Кейта - это связанный набор чисел Кейта, одно из которых кратно другому. Например, в базе 10 , , и все кластеры Keith. Возможно, это единственные три примера кластера Кита в базе 10 . ^[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  =  x пока  y  >  0 :  последовательность . append ( y  %  b )  y  =  y  //  b digit_count  =  len ( последовательность )  последовательность . обратный () в то время как  последовательность [ len ( последовательность )  -  1 ]  <  x :  n  =  0  для  i  в  диапазоне ( 0 ,  digit_count ):  n  =  n  +  последовательность [ len ( последовательность )  -  digit_count  +  i ]  последовательность . добавить ( п ) return  ( последовательность [ len ( последовательность )  -  1 ]  ==  x )

См. Также [ править ]

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

Ссылки [ править ]