Inrecreational mathematics, aKeith number orrepfigit number (short forrepetitiveFibonacci-like digit) is anatural number${\displaystyle n}$ in a givennumber base${\displaystyle b}$ with${\displaystyle k}$ digits such that when a sequence is created such that the first${\displaystyle k}$ terms are the${\displaystyle k}$ digits of${\displaystyle n}$ and each subsequent term is the sum of the previous${\displaystyle k}$ terms,${\displaystyle n}$ is part of the sequence. Keith numbers were introduced byMike Keith in 1987.^[1]They are computationally very challenging to find, with only about 100 known.

Let${\displaystyle n}$ be a natural number, let${\displaystyle k=\lfloor {\log }_{b}n\rfloor +1}$ be the number of digits of${\displaystyle n}$ in base${\displaystyle b}$, and let

${\displaystyle d_i=\frac{n{modb}^{i+1}-n{modb}^i}{b^i}}$

be the value of each digit of${\displaystyle n}$.

We define the sequence${\displaystyle S(i)}$ by alinear recurrence relation. For,

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

and for${\displaystyle i\ge k}$

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

If there exists an${\displaystyle i}$ such that${\displaystyle S(i)=n}$, then${\displaystyle n}$ is said to be aKeith number.

For example, 88 is a Keith number inbase 6, as

${\displaystyle S(0)=d_{3-0-1}=d_2=\frac{88{mod6}^{2+1}-88{mod6}^2}{6^2}=\frac{88mod216-88mod36}{36}=\frac{88-16}{36}=\frac{72}{36}=2}$

${\displaystyle S(1)=d_{3-1-1}=d_1=\frac{88{mod6}^{1+1}-88{mod6}^1}{6^1}=\frac{88mod36-88mod6}{6}=\frac{16-4}{6}=\frac{12}{6}=2}$

${\displaystyle S(2)=d_{3-2-1}=d_0=\frac{88{mod6}^{0+1}-88{mod6}^0}{6^0}=\frac{88mod6-88mod1}{1}=\frac{4-0}{1}=\frac{4}{1}=4}$

and the entire sequence

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

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

Whether or not there are infinitely many Keith numbers in a particular base${\displaystyle b}$ 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.^[2]According to Keith, inbase 10, on average${\displaystyle \frac{9}{10}{\log }_{2}10\approx 2.99}$ Keith numbers are expected between successivepowers of 10.^[3] Known results seem to support this.

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]

Inbase 2, there exists a method to construct all Keith numbers.^[3]

The Keith numbers inbase 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.

A Keith cluster is a related set of Keith numbers such that one is a multiple of another. For example, inbase 10,${\displaystyle \{14,28\}}$,${\displaystyle \{1104,2208\}}$, and${\displaystyle \{31331,62662,93993\}}$ are all Keith clusters. These are possibly the only three examples of a Keith cluster inbase 10.^[5]

The example below implements the sequence defined above inPython to determine if a number in a particular base is a Keith number:

defis_repfigit(x:int,b:int)->bool:"""Determine if a number in a particular base is a Keith number."""ifx==0:returnTruesequence=[]y=xwhiley>0:sequence.append(y%b)y=y//bdigit_count=len(sequence)sequence.reverse()whilesequence[len(sequence)-1]<x:n=0foriinrange(0,digit_count):n=n+sequence[len(sequence)-digit_count+i]sequence.append(n)returnsequence[len(sequence)-1]==x

• Arithmetic dynamics
• Fibonacci number
• Linear recurrence relation

• Arithmetic dynamics
• Base-dependent integer sequences
• Fibonacci numbers
• Recurrence relations

• Articles with short description
• Short description is different from Wikidata