To determine whether an n-digit number N is a Keith number, create a Fibonacci-like sequence that starts with the n decimal digits of N, putting the most significant digit first. Then continue the sequence, where each subsequent term is the sum of the previous n terms. By definition, N is a Keith number if N appears in the sequence thus constructed.
As an example, consider the 3-digit number N = 197. The sequence goes like this:
- 1, 9, 7, 17, 33, 57, 107, 197, 361, ...
Because 197 appears in the sequence, 197 is seen to be indeed a Keith number.
A Keith number is a positive integer N that appears as a term in a linear recurrence relation with initial terms based on its own decimal digits. Given an n-digit number
a sequence is formed with initial terms and with a general term produced as the sum of the previous n terms. If the number N appears in the sequence , then N is said to be a Keith number. One-digit numbers possess the Keith property trivially, and are usually excluded.
Finding Keith numbers
Whether or not there are infinitely many Keith numbers is currently a matter of speculation. Keith numbers are rare and hard to find. They can be found by exhaustive search and, unfortunately, no more efficient algorithm is known. According to Keith, on average Keith numbers are expected between successive powers of 10. 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.
A Keith cluster is a related set of Keith numbers such that one is a multiple of another. For example, (14, 28), (1104, 2208), and (31331, 62662, 93993). These are possibly the only three examples of a Keith cluster.
- Keith, Mike (1987). "Repfigit Numbers". Journal of Recreational Mathematics 19.
- Earls, Jason; Lichtblau, Daniel; Weisstein, Eric W. "Keith Number". MathWorld.
- Keith, Mike. "Keith Numbers".
- "Sloane's A007629 : Repfigit (REPetitive FIbonacci-like diGIT) numbers (or Keith numbers)", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
- Copeland, Ed. "14 197 and other Keith Numbers". Numberphile. Brady Haran.