In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777 ...
, a Keith number or repfigit number (short for repetitive
Fibonacci-like digit) is a
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
in a given
number base
In a positional numeral system, the radix or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal/denary system (the most common system in use today) the radix (base number) is t ...
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.
They are computationally very challenging to find, with only about 100 known.
Definition
Let
be a
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
, let
be the number of digits in the number in base
, and let
:
be the value of each digit of the number.
We define a
linear recurrence relation
In mathematics (including combinatorics, linear algebra, and dynamical systems), a linear recurrence with constant coefficients (also known as a linear recurrence relation or linear difference equation) sets equal to 0 a polynomial that is line ...
.
such that 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
A senary () numeral system
A numeral system (or system of numeration) is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using Numerical digit, digits or other symbols in a ...
, as
:
:
:
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.
According to Keith, in
base 10
The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...
, on average
Keith numbers are expected between successive powers of 10.
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, 251133297, ...
Other bases
In
base 2, there exists a method to construct all Keith numbers.
The Keith numbers in
base 12
The duodecimal system (also known as base 12, dozenal, or, rarely, uncial) is a positional notation numeral system using twelve as its base. The number twelve (that is, the number written as "12" in the decimal numerical system) is instead writ ...
, 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, ...
Keith clusters
A Keith cluster is a related set of Keith numbers such that one is a multiple of another. For example, in
base 10
The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...
,
,
, and
are all Keith clusters. These are possibly the only three examples of a Keith cluster in
base 10
The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...
.
Programming example
The example below implements the sequence defined above in
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
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 en(sequence) - 1< x:
n = 0
for i in range(0, digit_count):
n = n + sequence en(sequence) - digit_count + i sequence.append(n)
return (sequence en(sequence) - 1 x)
See also
*
Arithmetic dynamics Arithmetic dynamics is a field that amalgamates two areas of mathematics, dynamical systems and number theory. Classically, discrete dynamics refers to the study of the iteration of self-maps of the complex plane or real line. Arithmetic dynamics is ...
*
Fibonacci number
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
*
Linear recurrence relation
In mathematics (including combinatorics, linear algebra, and dynamical systems), a linear recurrence with constant coefficients (also known as a linear recurrence relation or linear difference equation) sets equal to 0 a polynomial that is line ...
References
{{Classes of natural numbers
Arithmetic dynamics
Base-dependent integer sequences
Fibonacci numbers
Recurrence relations