Keith number

In recreational mathematics, a Keith number or repfigit number (short for repetitive Fibonacci-like digit) is a number in the following integer sequence:

14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, ....(sequence A007629 in OEIS)

Keith numbers were introduced by Mike Keith in 1987.^[1] They are computationally very challenging to find, with only about 100 known.

Introduction

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.

Definition

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

$N=\sum_{i=0}^{n-1} 10^i {d_i},$

a sequence $S_N$ is formed with initial terms $d_{n-1}, d_{n-2},\ldots, d_1, d_0$ and with a general term produced as the sum of the previous n terms. If the number N appears in the sequence $S_N$, 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.^[2] According to Keith, on average $\textstyle\frac{9}{10}\log_2{10}\approx 2.99$ Keith numbers are expected between successive powers of 10.^[3] 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,^[4] 251133297.

Keith clusters

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.^[5]

References

1. Keith, Mike (1987). "Repfigit Numbers". Journal of Recreational Mathematics 19.
2. Earls, Jason; Lichtblau, Daniel; Weisstein, Eric W. "Keith Number". MathWorld.
3. Keith, Mike. "Keith Numbers".
4. "Sloane's A007629 : Repfigit (REPetitive FIbonacci-like diGIT) numbers (or Keith numbers)", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
5. Copeland, Ed. "14 197 and other Keith Numbers". Numberphile. Brady Haran.