Keith number
In recreational mathematics, a Keith number or repfigit number (short for repetitive Fibonacci-like digit) is a natural number in a given
Definition
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
and for
If there exists an such that , then is said to be a Keith number.
For example, 88 is a Keith number in
and the entire sequence
and .
Finding Keith numbers
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
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, 251133297, ...[4]
Other bases
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
A Keith cluster is a related set of Keith numbers such that one is a multiple of another. For example, in
Programming example
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
- Arithmetic dynamics
- Fibonacci number
- Linear recurrence relation
References
- ^ Keith, Mike (1987). "Repfigit Numbers". Journal of Recreational Mathematics. 19 (2): 41–42.
- ^ Earls, Jason; Lichtblau, Daniel; Weisstein, Eric W. "Keith Number". MathWorld.
- ^ a b Keith, Mike. "Keith Numbers".
- ^ 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.
- ^ Copeland, Ed. "14 197 and other Keith Numbers". Numberphile. Brady Haran. Archived from the original on 2017-05-22. Retrieved 2013-04-09.