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 '''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 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 = 1 | 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 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, 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>{{Cite OEIS|sequencenumber=A007629|name=Repfigit (REPetitive FIbonacci-like diGIT) numbers (or Keith numbers) }}</ref>

==Other bases== 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 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 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>

==References== {{reflist}}

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