Editing Keith number

{{Short description|Type of number introduced by Mike Keith}}
{{about|the mathematics concept|the political concept|Countdown with Keith Olbermann}}
In [[recreational mathematics]], a '''Keith number''' or '''repfigit number''' (short for '''rep'''etitive [[Fibonacci sequence|'''F'''ibonacci-like]] d'''igit''') 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 (mathematician)|Mike Keith]] in 1987.<ref>{{cite journal | author-link = Mike Keith (mathematician) | first = Mike | last = Keith | title = Repfigit Numbers | journal = [[Journal of Recreational Mathematics]] | volume = 19 |issue = 2 | year = 1987 |pages = 41–42}}</ref>
They are computationally very challenging to find, with only about 125 known.

== Definition ==
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 numbers===
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>{{cite web | last1 = Earls | first1 = Jason | last2 = Lichtblau | first2 = Daniel | last3 = Weisstein | first3 = Eric W. | author-link = Eric W. Weisstein| title = Keith Number | publisher = [[MathWorld]] | url = http://mathworld.wolfram.com/KeithNumber.html }}</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 [[power of 10|powers of 10]].<ref name="keith_web">{{cite web | author-link = Mike Keith (mathematician) | first = Mike | last = Keith | title = Keith Numbers | url = http://www.cadaeic.net/keithnum.htm }}</ref> Known results seem to support this.

==Examples==
[[14 (number)|14]], [[19 (number)|19]], [[28 (number)|28]], [[47 (number)|47]], [[61 (number)|61]], [[75 (number)|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>{{Cite OEIS|sequencenumber=A007629|name=Repfigit (REPetitive FIbonacci-like diGIT) numbers (or Keith numbers) }}</ref>

==Other bases==
In [[binary number|base 2]], there exists a method to construct all Keith numbers.<ref name="keith_web" /> 

The Keith numbers in [[duodecimal|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 clusters==
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>{{cite web|last=Copeland|first=Ed|title=14 197 and other Keith Numbers|url=http://www.numberphile.com/videos/197_keith.html|work=Numberphile|publisher=[[Brady Haran]]|access-date=2013-04-09|archive-url=https://web.archive.org/web/20170522032347/http://www.numberphile.com/videos/197_keith.html|archive-date=2017-05-22|url-status=dead}}</ref>

==Programming example==
The example below implements the sequence defined above in [[Python (programming language)|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>

==See also==
* [[Arithmetic dynamics#Other areas in which number theory and dynamics interact|Arithmetic dynamics]]
* [[Fibonacci number]]
* [[Linear recurrence relation]]

==References==
{{reflist}}

{{Classes of natural numbers}}

[[Category:Arithmetic dynamics]]
[[Category:Base-dependent integer sequences]]
[[Category:Fibonacci numbers]]
[[Category:Recurrence relations]]