Determination of all Keith Numbers up to 10¹⁹

Mike Keith

ABSTRACT

All Keith numbers (a.k.a. "repfigits") are determined up to a limit of 10¹⁹, bettering the previous record of 10¹⁵. The problem of finding all Keith numbers is shown to be equivalent to solving a series of Diophantine equations with the variables restricted to taking on the values {0,...9}, and an efficient algorithm for solving these equations is described that is about 2000 times faster than the best previously-published algorithm.

Introduction

A Keith number is an n-digit integer N with the following property: If a Fibonacci-like sequence (in which each term in the sequence is the sum of the n previous terms) is formed, with the first n terms being the decimal digits of the number N, then N itself occurs as a term in the sequence. For example, 197 is a Keith number since it generates the sequence

1, 9, 7, 17, 33, 57, 107, 197, ...

A brief history of the discovery of Keith numbers is shown in Table 1.

Table 1. The search for Keith numbers,
including complexity of search algorithm used.

As with most hard computational problems, advances in the discovery of Keith numbers have been made possible by both (a) the continued availability of faster computers, and (b) the development of faster search algorithms. Since more advances have been made in the latter than in the former (roughly a factor of a billion improvement in the last 12 years), we now give a brief survey of computational algorithms.

Algorithmic Complexity

To find all Keith numbers with d digits, the obvious brute-force algorithm (used in [Keith87]) is to take each integer N and compute terms of the Fibonacci sequence it generates until some term is larger than N, and check if any of the terms equals N. For each N we have to compute about log₂(10^d) terms of the Fibonacci sequence (approximately, (10/3)d), and each term requires d additions, so the total number of operations required is as shown in Table 1.

In [Pickover90] it was pointed out that computation of each term in the Fibonacci sequence can be done in O(1) time instead of O(n) time, by computing

a_k = 2a_k-1 - a_k-n-1

The most important observation, however, is to realize that since the initial terms of the Fibonacci sequence are

d₁, d₂, d₃, ..., d_n,

(where d_i are the inidividual digits of N), the next term is d₁ + d₂ + d₃ +...+ d_n, and similarly every succeeding term is a linear combination of the d_i. For N to be a Keith number, it must be equal to some term of this sequence. This means that

di10d

=

ci di

(1)

where the RHS is the expression for some term of the Fibonacci sequence. But this is just a Diophantine equation in the d_i, with the additional restriction that the d_i can only take on the values {0,...9}. From a given term in the Fibonacci sequence we can determine quickly if it might yield a solution, by comparing the maximum and minimum possible values of the LHS and RHS of (1); usually, there are eight such terms in the whole Fibonacci sequence.

The problem of determing all Keith numbers with d digits thus reduces to solving eight Diophantine equations in d unknowns. No complexity reduction is acheived if a brute-force search is used to solve the Diophantine equations; however, [Sherriff94] describes an equation-splitting strategy that provies a significant speedup. First, subtract the LHS and RHS of (1) to get a homogenous Diophantine equation in the d_i:

aidi

=

0.

(2)

Now split off the last K terms of the equation, giving

(a₁d₁ + ... + a_N-Kd_N-K) = -(a_N-K+1d_N-K+1 + ... + a_Nd_N)

As an initial step, precompute all 10^K possible values of the RHS (as the d_i range over {0...9}) and store them in a table. Then, find all solutions using the following procedure:

for each (N-K)-tuple of values for a(1)...a(N-K)
  compute value of LHS (=L)
  if L appears in lookup table
    solution has been found

Determination of whether L appears in the lookup table can be done in log₂(10^K) steps, rather than 10^K, by sorting the values in the table and using a binary search. This reduces the overall complexity for solving the Diophantine equation from roughly 10^N to log₂(10^K)10^N-K, a significant savings. A larger value of K is always better, but this is limited in practice by the amount of memory required. K=6 or 7 are convenient values to use.

For the present search even this improved algorithm would have been too slow. It was improved by splitting the equation into three parts: (1) the first N-2K variables, (2) the next K variables, and (3) the last K. Two lookup tables are used - one for set (2) and one for set (3). Each of these is just like the table described above, containing 10^K sorted values. The search procedure now becomes:

for each (N-2K)-tuple of values for a(1)...a(N-2K)
  compute value of LHS (=L)
  if L can be formed as the sum of two values in Table1 and Table2
    solution has been found

In our implementation, determination of whether L can be formed by summing values in the two lookup tables is done by a two-dimensional binary search. This is sped up even more by recognizing that the target L values for two successive searches will be close, since the values of first N-2K variables will have only changed slightly (indeed, most of the time just one of them will have changed by 1). Thus, we begin each search in the same neighborhood of the array where the last search terminated. The success of this strategy is improved further (quite significantly, it turns out) by numbering the variables so that the a_i are sorted in increasing order.

Finally, we also improve the speed of the search over the first N-2K variables by using a branch-and-bound technique. For each variable, instead of assigning all possibilities from 0 to 9 as trial values, we only assign those which might yield equality through assignment of the remaining variables. These are determined quickly by using a precomputed lookup table that gives the maximum and minimum value achievable by assigning 0 to 9 to the last t variables, for each t.

Computation-time estimates indicated that we would be able to search up to around 10¹⁹ (i.e., 19-variable Diophantine equations) using this method. However, signed 64-bit integers can only represent magnitudes up to about 9.2 x 10¹⁸, so it was necessary to implement our own 96-bit arithmetic routines using 32-bit registers. We chose K=6, for two reasons: 10⁶ is close to 2²⁰, which makes the binary search convenient, and the size of the two lookup tables (2²⁰ x 12 bytes x 2 = 24M bytes) fits comfortably on a machine with 64M of memory.

Finding the new Keith numbers with 16, 17, 18, and 19 digits required about 500 hours of computation on a 350 MHz PC using an Intel Pentium® II processor.

Note that all of the complexities shown in Table 1 are O(10^d). Even though the "constant term" has been significantly reduced (in our case, to a mere 4 x 10^-7), the inherent complexity is still exponential. This is to be expected, because solving a Diophantine equation can be transformed into a Knapsack Problem, which is NP-complete. Thus, finding Keith numbers is also NP-complete.

The List

Here is the complete list of known Keith numbers, and also the complete list of numbers up to 10¹⁹. Besides extending the results in [Sherriff94] this also corrects three errors on page 195 of that paper, in which the numbers 86935, 925993, and 44121607 are given incorrectly.

The number of Keith numbers with d digits (for d=2, 3, ...) is

6, 2, 9, 7, 10, 2, 3, 2, 0, 2, 4, 2, 3, 3, 3, 5, 3, 5

for a total of 71 less than 10¹⁹.

Some Unsolved Problems

Besides the fundamental problem of discovering larger Keith numbers, here are a few of the still-outstanding problems concerning them.

1. Are there an infinite number of Keith numbers? Heuristic arguments suggest that the answer is "yes" - in fact, we expect to find roughly (9/10)log₂10 (about 3) Keith numbers between each power of 10. But there is still no proof, constructive or otherwise, of the infinitude of Keith numbers.
2. Is n=10 the only number of digits for which there are no Keith numbers?

References

[Keith87] M. Keith, "Repfigit Numbers", Journal of Recreational Mathematics, Vol. 19, No. 2, p. 41, 1987.

[Pickover90] C. Pickover, "All Known Replicating Fibonacci Digits Less Then One Billion", Journal of Recreational Mathematics, Vol. 22, No. 3, p. 176, 1990.

[Sherriff94] K. Shirriff, "Computing Replicating Fibonacci Digits", Journal of Recreational Mathematics, Vol. 26, No. 3, p. 191, 1994.

---

Back to Mike's home page