Keith number

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

External links[edit]