Keith number

Last updated March 22, 2024

In recreational mathematics, a Keith number or repfigit number (short for repetitive Fibonacci-like digit) is a natural number $n$ in a given number base $b$ with $k$ digits such that when a sequence is created such that the first $k$ terms are the $k$ digits of $n$ and each subsequent term is the sum of the previous $k$ terms, $n$ 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

Let $n$ be a natural number, let $k=\lfloor \log _{b}{n}\rfloor +1$ be the number of digits of $n$ in base $b$ , and let

d_{i}={\frac {n{\bmod {b}}^{i+1}-n{\bmod {b}}^{i}}{b^{i}}}

be the value of each digit of $n$ .

We define the sequence $S(i)$ by a linear recurrence relation. For $0\leq i<k$ ,

S(i)=d_{k-i-1}

and for $i\geq k$

S(i)=\sum _{j=0}^{k}S(i-k+j)

If there exists an $i$ such that $S(i)=n$ , then $n$ is said to be a Keith number.

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

S(0)=d_{3-0-1}=d_{2}={\frac {88{\bmod {6}}^{2+1}-88{\bmod {6}}^{2}}{6^{2}}}={\frac {88{\bmod {2}}16-88{\bmod {3}}6}{36}}={\frac {88-16}{36}}={\frac {72}{36}}=2

S(1)=d_{3-1-1}=d_{1}={\frac {88{\bmod {6}}^{1+1}-88{\bmod {6}}^{1}}{6^{1}}}={\frac {88{\bmod {3}}6-88{\bmod {6}}}{6}}={\frac {16-4}{6}}={\frac {12}{6}}=2

S(2)=d_{3-2-1}=d_{0}={\frac {88{\bmod {6}}^{0+1}-88{\bmod {6}}^{0}}{6^{0}}}={\frac {88{\bmod {6}}-88{\bmod {1}}}{1}}={\frac {4-0}{1}}={\frac {4}{1}}=4

and the entire sequence

S(i)=\{2,2,4,8,14,26,48,88,162,\ldots \}

and $S(7)=88$ .

Finding Keith numbers

Whether or not there are infinitely many Keith numbers in a particular base $b$ 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 $\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, 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 base 10, $\{14,28\}$ , $\{1104,2208\}$ , and $\{31331,62662,93993\}$ are all Keith clusters. These are possibly the only three examples of a Keith cluster in base 10.^[5]

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:

defis_repfigit(x:int,b:int)->bool:"""Determine if a number in a particular base is a Keith number."""ifx==0:returnTruesequence=[]y=xwhiley>0:sequence.append(y%b)y=y//bdigit_count=len(sequence)sequence.reverse()whilesequence[len(sequence)-1]<x:n=0foriinrange(0,digit_count):n=n+sequence[len(sequence)-digit_count+i]sequence.append(n)returnsequence[len(sequence)-1]==x

Related Research Articles

In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted $F n$ . The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes from 1 and 2. Starting from 0 and 1, the sequence begins

In mathematics, the Euler numbers are a sequence E_n of integers defined by the Taylor series expansion

In mathematics a polydivisible number is a number in a given number base with digits abcde... that has the following properties:

Its first digit a is not 0.
The number formed by its first two digits ab is a multiple of 2.
The number formed by its first three digits abc is a multiple of 3.
The number formed by its first four digits abcd is a multiple of 4.
etc.

Casting out nines is any of three arithmetical procedures:

In mathematics, a harshad number in a given number base is an integer that is divisible by the sum of its digits when written in that base. Harshad numbers in base $n$ are also known as $n$ -harshad numbers. Harshad numbers were defined by D. R. Kaprekar, a mathematician from India. The word "harshad" comes from the Sanskrit harṣa (joy) + da (give), meaning joy-giver. The term "Niven number" arose from a paper delivered by Ivan M. Niven at a conference on number theory in 1977.

In number theory, a self number or Devlali number in a given number base $is a natural number that cannot be written as the sum of any other natural number and the individual digits of . 20 is a self number, because no such combination can be found. 21 is not, because it can be written as 15 + 1 + 5 using n = 15. These numbers were first described in 1949 by the Indian mathematician D. R. Kaprekar.$

In number theory, a practical number or panarithmic number is a positive integer $such that all smaller positive integers can be represented as sums of distinct divisors of . For example, 12 is a practical number because all the numbers from 1 to 11 can be expressed as sums of its divisors 1, 2, 3, 4, and 6: as well as these divisors themselves, we have 5 = 3 + 2, 7 = 6 + 1, 8 = 6 + 2, 9 = 6 + 3, 10 = 6 + 3 + 1, and 11 = 6 + 3 + 2.$

In mathematics, the digit sum of a natural number in a given number base is the sum of all its digits. For example, the digit sum of the decimal number $would be$

A Fibonacci prime is a Fibonacci number that is prime, a type of integer sequence prime.

In number theory, a Dudeney number in a given number base $is a natural number equal to the perfect cube of another natural number such that the digit sum of the first natural number is equal to the second. The name derives from Henry Dudeney, who noted the existence of these numbers in one of his puzzles, Root Extraction, where a professor in retirement at Colney Hatch postulates this as a general method for root extraction.$

In number theory, a narcissistic number in a given number base $is a number that is the sum of its own digits each raised to the power of the number of digits.$

A sum-product number in a given number base $is a natural number that is equal to the product of the sum of its digits and the product of its digits.$

In mathematics, the greedy algorithm for Egyptian fractions is a greedy algorithm, first described by Fibonacci, for transforming rational numbers into Egyptian fractions. An Egyptian fraction is a representation of an irreducible fraction as a sum of distinct unit fractions, such as 5/6 = 1/2 + 1/3. As the name indicates, these representations have been used as long ago as ancient Egypt, but the first published systematic method for constructing such expansions was described in 1202 in the Liber Abaci of Leonardo of Pisa (Fibonacci). It is called a greedy algorithm because at each step the algorithm chooses greedily the largest possible unit fraction that can be used in any representation of the remaining fraction.

In mathematics, the Fibonacci numbers form a sequence defined recursively by:

The digital root of a natural number in a given radix is the value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached. For example, in base 10, the digital root of the number 12345 is 6 because the sum of the digits in the number is 1 + 2 + 3 + 4 + 5 = 15, then the addition process is repeated again for the resulting number 15, so that the sum of 1 + 5 equals 6, which is the digital root of that number. In base 10, this is equivalent to taking the remainder upon division by 9, which allows it to be used as a divisibility rule.

In number theory, the multiplicative digital root of a natural number $in a given number base is found by multiplying the digits of together, then repeating this operation until only a single-digit remains, which is called the multiplicative digital root of . The multiplicative digital root for the first few positive integers are:$

In number theory, a factorion in a given number base $is a natural number that equals the sum of the factorials of its digits. The name factorion was coined by the author Clifford A. Pickover.$

A repeating decimal or recurring decimal is a decimal representation of a number whose digits are eventually periodic ; if this sequence consists only of zeros, the decimal is said to be terminating, and is not considered as repeating. It can be shown that a number is rational if and only if its decimal representation is repeating or terminating. For example, the decimal representation of 1/3 becomes periodic just after the decimal point, repeating the single digit "3" forever, i.e. 0.333.... A more complicated example is 3227/555, whose decimal becomes periodic at the second digit following the decimal point and then repeats the sequence "144" forever, i.e. 5.8144144144.... Another example of this is 593/53, which becomes periodic after the decimal point, repeating the 13-digit pattern "1886792452830" forever, i.e. 11.18867924528301886792452830....

In number theory and mathematical logic, a Meertens number in a given number base $is a natural number that is its own Gödel number. It was named after Lambert Meertens by Richard S. Bird as a present during the celebration of his 25 years at the CWI, Amsterdam.$

In number theory, a perfect digital invariant (PDI) is a number in a given number base ( $) that is the sum of its own digits each raised to a given power ().$

References

↑ Keith, Mike (1987). "Repfigit Numbers". Journal of Recreational Mathematics . 19 (2): 41–42.
↑ Earls, Jason; Lichtblau, Daniel; Weisstein, Eric W. "Keith Number". MathWorld.
1 2 Keith, Mike. "Keith Numbers".
↑ Sloane, N. J. A. (ed.). "SequenceA007629(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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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.

[keith_web-3] 1 2 Keith, Mike. "Keith Numbers".

[OEIS-4] Sloane, N. J. A. (ed.). "SequenceA007629(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.

[1]

[2]

[3]

[4]

[5]