Keith number

(Redirected from Keith prime)

In recreational mathematics, a Keith number or repfigit number (short for repetitive Fibonacci-like digit) is a natural number in a given number base with digits such that when a sequence is created such that the first terms are the digits of and each subsequent term is the sum of the previous terms, is part of the sequence. Keith numbers were introduced by Mike Keith in 1987.[1] They are computationally very challenging to find, with only about 100 known.

Definition

edit

Let   be a natural number, let   be the number of digits of   in base  , and let

 

be the value of each digit of  .

We define the sequence   by a linear recurrence relation. For  ,

 

and for  

 

If there exists an   such that  , then   is said to be a Keith number.

For example, 88 is a Keith number in base 6, as

 
 
 

and the entire sequence

 

and  .

Finding Keith numbers

edit

Whether or not there are infinitely many Keith numbers in a particular base   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, in base 10, on average   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, 251133297, ...[4]

Other bases

edit

In base 2, there exists a method to construct all Keith numbers.[3]

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

Keith clusters

edit

A Keith cluster is a related set of Keith numbers such that one is a multiple of another. For example, in base 10,  ,  , and   are all Keith clusters. These are possibly the only three examples of a Keith cluster in base 10.[5]

Programming example

edit

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

def is_repfigit(x: int, b: int) -> bool:
    """Determine if a number in a particular base is a Keith number."""
    if x == 0:
        return True

    sequence = []
    y = x

    while y > 0:
        sequence.append(y % b)
        y = y // b

    digit_count = len(sequence)
    sequence.reverse()

    while sequence[len(sequence) - 1] < x:
        n = 0
        for i in range(0, digit_count):
            n = n + sequence[len(sequence) - digit_count + i]
        sequence.append(n)

    return sequence[len(sequence) - 1] == x

See also

edit

References

edit
  1. ^ Keith, Mike (1987). "Repfigit Numbers". Journal of Recreational Mathematics. 19 (2): 41–42.
  2. ^ Earls, Jason; Lichtblau, Daniel; Weisstein, Eric W. "Keith Number". MathWorld.
  3. ^ a b Keith, Mike. "Keith Numbers".
  4. ^ Sloane, N. J. A. (ed.). "Sequence 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. Archived from the original on 2017-05-22. Retrieved 2013-04-09.