Template:Short description Template:About In recreational mathematics, a Keith number or repfigit number (short for repetitive Fibonacci-like digit) is a natural number <math>n</math> in a given number base <math>b</math> with <math>k</math> digits such that when a sequence is created such that the first <math>k</math> terms are the <math>k</math> digits of <math>n</math> and each subsequent term is the sum of the previous <math>k</math> terms, <math>n</math> is part of the sequence. Keith numbers were introduced by Mike Keith in 1987.<ref>Template:Cite journal</ref> They are computationally very challenging to find, with only about 125 known.
DefinitionEdit
Let <math>n</math> be a natural number, let <math>k = \lfloor \log_{b}{n} \rfloor + 1</math> be the number of digits of <math>n</math> in base <math>b</math>, and let
- <math>d_i = \frac{n \bmod b^{i + 1} - n \bmod b^{i}}{b^{i}}</math>
be the value of each digit of <math>n</math>.
We define the sequence <math>S(i)</math> by a linear recurrence relation. For <math>0 \leq i < k</math>,
- <math>S(i) = d_{k - i - 1}</math>
and for <math>i \geq k</math>
- <math>S(i) = \sum_{j = 0}^{k} S(i - k + j)</math>
If there exists an <math>i</math> such that <math>S(i) = n</math>, then <math>n</math> is said to be a Keith number.
For example, 88 is a Keith number in base 6, as
- <math>S(0) = d_{3 - 0 - 1} = d_2 = \frac{88 \bmod 6^{2 + 1} - 88 \bmod 6^{2}}{6^{2}} = \frac{88 \bmod 216 - 88 \bmod 36}{36} = \frac{88 - 16}{36} = \frac{72}{36} = 2</math>
- <math>S(1) = d_{3 - 1 - 1} = d_1 = \frac{88 \bmod 6^{1 + 1} - 88 \bmod 6^{1}}{6^{1}} = \frac{88 \bmod 36 - 88 \bmod 6}{6} = \frac{16 - 4}{6} = \frac{12}{6} = 2</math>
- <math>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</math>
and the entire sequence
- <math>S(i) = \{2, 2, 4, 8, 14, 26, 48, 88, 162, \ldots\}</math>
and <math>S(7) = 88</math>.
Finding Keith numbersEdit
Whether or not there are infinitely many Keith numbers in a particular base <math>b</math> is currently a matter of speculation. Keith numbers are rare and hard to find. They can be found by exhaustive search, and no more efficient algorithm is known.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> According to Keith, in base 10, on average <math>\textstyle\frac{9}{10}\log_2{10}\approx 2.99</math> Keith numbers are expected between successive powers of 10.<ref name="keith_web">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> Known results seem to support this.
ExamplesEdit
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, ...<ref name=OEIS>Template:Cite OEIS</ref>
Other basesEdit
In base 2, there exists a method to construct all Keith numbers.<ref name="keith_web" />
The Keith numbers in base 12, written in base 12, are
- 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, ...
where ᘔ represents 10 and Ɛ represents 11.
Keith clustersEdit
A Keith cluster is a related set of Keith numbers such that one is a multiple of another. For example, in base 10, <math>\{14, 28\}</math>, <math>\{1104, 2208\}</math>, and <math>\{31331, 62662, 93993\}</math> are all Keith clusters. These are possibly the only three examples of a Keith cluster in base 10.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
Programming exampleEdit
The example below implements the sequence defined above in Python to determine if a number in a particular base is a Keith number:
<syntaxhighlight lang="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
</syntaxhighlight>