Keith number

This article is about the mathematics concept. For the political concept, see Countdown with Keith Olbermann.

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

This article is issued from Wikipedia - version of the Tuesday, March 15, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.