Counting Keith Numbers

Martin Klazar Department of Applied Mathematics and Institute for Theoretical Computer Science (ITI) Faculty of Mathematics and Physics Charles University Malostranské nám. 25 11800 Praha Czech Republic

                klazar@kam.mff.cuni.cz

Florian Luca Instituto de Matemáticas Universidad Nacional Autonoma de México C.P. 58089 Morelia, Michoacán México

                 fluca@matmor.unam.mx

Abstract

A Keith number is a positive integer N with the decimal representation a_{1}a_{2} ⋯ a_{n} such that n ≥ 2 and N appears in the sequence (K_{m})_{m≥1} given by the recurrence K_{1} = a_{1}, …, K_{n} = a_{n} and K_{m} = K_{m−1} + K_{m−2} + ⋯ + K_{m−n} for m > n. We prove that there are only finitely many Keith numbers using only one decimal digit (i.e., a_{1} = a_{2} = ⋯ = a_{n}), and that the set of Keith numbers is of asymptotic density zero.

1 Introduction

With the number 197, let (K_{m})_{m≥1} be the sequence whose first three terms K_{1} = 1, K_{2} = 9 and K_{3} = 7 are the digits of 197 and that satisfies the recurrence K_{m} = K_{m−1}+K_{m−2}+K_{m−3} for all m > 3. Its initial terms are

1, 9, 7, 17, 33, 57, 107, 197, 361, 665, …

Note that 197 itself is a member of this sequence. This phenomenon was first noticed by Mike Keith and such numbers are now called Keith numbers. More precisely, a number N with decimal representation a_{1}a_{2} ⋯ a_{n} is a Keith number if n ≥ 2 and N appears in the sequence K^{N} = (K_{m}^{N})_{m≥1} whose n initial terms are the digits of N read from left to right and satisfying K_{m}^{N} = K_{m−1}^{N} + K_{m−2}^{N} + ⋯ + K_{m−n}^{N} for all m > n. These numbers appear in Keith’s papers [3, 4] and they are the subject of entry A007629 in Neil Sloane’s Encyclopedia of Integer Sequences [11] (see also [7, 8, 9]).

Let K be the set of all Keith numbers. It is not known if K is infinite or not. The sequence K begins

14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, …

M. Keith and D. Lichtblau found all 94 Keith numbers smaller than 10^{29} [4]. D. Lichtblau found the first pandigital Keith number (containing each of the digits 0 to 9 at least once): 27847652577905793413.

Recall that a rep-digit is a positive integer N of the form a(10^{n} − 1)/9 for some a ∈ {1, …, 9} and n ≥ 1; i.e., a number which is a string of the same digit a when written in base 10. Our first result shows that there are only finitely many Keith numbers which are rep-digits.

Theorem 1.1. There are only finitely many Keith numbers that are rep-digits and their set can be effectively determined.

We point out that some authors refer to the Keith numbers as replicating Fibonacci digits in analogy with the Fibonacci sequence (F_{n})_{n≥1} given by F_{1} = 1, F_{2} = 1 and F_{n+2} = F_{n+1} + F_{n} for all n ≥ 1. F. Luca showed [5] that the largest rep-digit Fibonacci number is 55.

The proof of Theorem 1.1 uses Baker-type estimates for linear forms in logarithms. It will be clear from the proof that it applies to all base b Keith numbers for any fixed integer b ≥ 3, where these numbers are defined analogously starting with their base b expansion (see the remark after the proof of Theorem 1.1).

For a positive integer x we write K(x) = K∩[1, x]. As we mentioned before, K(10^{29}) = 94. A heuristic argument [4] suggests that #K(x) ≫ log x, and, in particular, that K should be infinite. Going in the opposite way, we show that K is of asymptotic density zero.

Theorem 1.2. The estimate

#K(x) ≪ \frac{x}{\sqrt{log x}}

holds for all positive integers x ≥ 2.

The above estimate is very weak. It does not even imply that that sum of the reciprocals of the members of K is convergent. We leave to the reader the task of finding a better upper bound on #K(x). Typographical changes (see the remark after the proof of Theorem 1.2) show that Theorem 1.2 also is valid for the set of base b Keith numbers if b ≥ 4. Perhaps it can be extended also to the case b = 3. For b = 2, Kenneth Fan has an unpublished manuscript (mentioned by Keith [4]) showing how to construct all Keith numbers and that, in particular, there are infinitely many of them. For example, any power of 2 is a binary Keith number.

Throughout this paper, we use the Vinogradov symbols ≫ and ≪ as well as the Landau symbols O and o with their usual meaning. Recall that for functions A and B the inequalities A ≪ B, B ≫ A and A = O(B) are all equivalent to the fact that there exists a positive constant c such that the inequality |A| ≤ cB holds. The constants in the inequalities implied by these symbols may occasionally depend on other parameters. For a real number x we use log x for the natural logarithm of x. For a set A, we use #A and |A| to denote its cardinality.

2 Preliminary Results

For an integer N > 0, recall the definition of the sequence K^{N} = (K_{m}^{N})_{m≥1} given in the Introduction. In K^{N} we allow N to be any string of the digits 0, 1, …, 9, so N may have initial zeros. So, for example, K^{020} = (0, 2, 0, 2, 4, 6, 12, 22, …). For n ≥ 1 we define the sequence L^{n} as L^{n} = K^{M} where M = 11 ⋯ 1 with n digits 1. In particular, L^{1} = (1, 1, 1, …) and L^{2} = (1, 1, 2, 3, 5, 8, …), the Fibonacci numbers. In the following lemma, which will be used in the proofs of both Theorems 1 and 2, we establish some properties of the sequences K^{N} and L^{n}.

Lemma 2.1. Let N be a string of the digits 0, 1, …, 9 with length n ≥ 1. If N does not start with 0, we understand it also as the decimal representation of a positive integer.

(a) If N has at least k ≥ 1 nonzero entries, then K_{m}^{N} ≥ L_{k+m−n}^{k} holds for every m ≥ n + 1.

(b) If N has at least one nonzero entry, then K_{m}^{N} ≥ L_{m−n}^{n} holds for every m ≥ n + 1. We have K_{m}^{N} ≤ 9L_{m}^{n} for every m ≥ 1.

(c) If n ≥ 3 and N = K_{m}^{N} for some m ≥ 1 (so N is a Keith number), then 2n < m < 7n.

(d) For fixed n ≥ 2 and growing m ≥ n + 1,

L_{m}^{n} = 2^{m−n−1}(n − 1)(1 + O(m/2^{n})) + 1

where the constant in O is absolute.

Proof. (a). By the recurrences defining K^{N} and L^{k}, the inequality clearly holds for the first k indices m = n + 1, n + 2, …, n + k. For m > n + k it holds by induction.

(b). We have K_{m}^{N} ≥ 1 = L_{m−n}^{n} for m = n + 1, n + 2, …, 2n and the inequality holds. For m > 2n it holds by induction. The second inequality follows easily by induction.

(c). The lower bound m > 2n follows from the fact that K^{N} is nondecreasing and that

K_{2n}^{N} ≤ 9L_{2n}^{n} = 9 · 2^{n−1}(n − 1) + 9 < 10^{n−1} ≤ N

for n ≥ 3. To obtain the upper bound, note that for m ≥ n we have by induction that L_{m}^{n} ≥ L_{m−n+2}^{2} ≥ ϕ^{m−n} where ϕ = 1.61803 ⋯ is the golden ratio. Thus, by part (b),

10^{n} > N = K_{m}^{N} ≥ L_{m−n}^{n} ≥ ϕ^{m−2n}

and m < (2 + log 10/ log ϕ)n < 7n.

(d). We write L_{m}^{n} in the form L_{m}^{n} = (2^{m−n−1} − d(m))(n − 1) + 1 and prove by induction on m that for m ≥ n + 1,

0 ≤ d(m) < m2^{m−2n}.

This will prove the claim.

It is easy to see by the recurrence that L_{n+1}^{n}, L_{n+2}^{n}, …, L_{2n+1}^{n} are equal, respectively, to 2^{0}(n − 1) + 1, 2^{1}(n − 1) + 1, …, 2^{n}(n − 1) + 1. So d(m) = 0 for n + 1 ≤ m ≤ 2n + 1 and the claim holds. For m ≥ 2n + 1,

L_{m}^{n} = L_{m−1}^{n} + L_{m−2}^{n} + ⋯ + L_{m−n}^{n}
= ∑_{k=1}^{n} ((2^{m−n−1−k} − d(m − k))(n − 1) + 1)

= (2^{m−n−1} − 2^{m−2n−1} + 1 − ∑_{k=1}^{n} d(m − k))(n − 1) + 1

and the induction hypothesis gives

0 ≤ d(m) = 2^{m−2n−1} − 1 + ∑_{k=1}^{n} d(m − k)

< 2^{m−2n−1} + (m − 1) ∑_{k=1}^{n} 2^{m−2n−k}
< m2^{m−2n}.

In part (d), if m is roughly of size 2^{n} or larger then the error term swallows the main term and the asymptotic estimate is useless. Indeed, the actual asymptotic behavior of L_{m}^{n} when m → ∞ is cα^{m} where c > 0 is a constant and α < 2 is the only positive root of the polynomial x^{n} − x^{n−1} − ⋯ − x − 1. But for m small relative to 2^{n}, say m = O(n) (ensured for Keith numbers by part (c)), this “incorrect” asymptotic estimate of L_{m}^{n} is very precise and useful, as we shall demonstrate in the proofs of Theorems 1.1 and 1.2.

In the proof of Theorem 1.1 we will apply also a lower bound for a linear form in logarithms. The following bound can be deduced from a result due to Matveev [6, Corollary 2.3].

Lemma 2.2. Let A_{1}, …, A_{k}, A_{i} > 1, and n_{1}, …, n_{k} be integers, and let N = max{|n_{1}|, …, |n_{k}|, 2}. There exist positive absolute constants c_{1} and c_{2} (which are effective), such that if

Λ = n_{1} log A_{1} + n_{2} log A_{2} + ⋯ + n_{k} log A_{k} ≠ 0,

then

log |Λ| > −c_{1}c_{2}^{k}(log A_{1}) ⋯ (log A_{k}) log N.

For the proof of Theorem 2 we will need an upper bound on sizes of antichains (sets of mutually incomparable elements) in the poset (partially ordered set)

P (k, n) = ({1, 2, …, k}^{n}, ≤_{p})

where ≤_{p} is the product ordering

a = (a_{1}, a_{2}, …, a_{n}) ≤_{p} b = (b_{1}, b_{2}, …, b_{n}) ⟺ a_{i} ≤ b_{i} for i = 1, 2, …, n.

We have |P (k, n)| = k^{n} and for k = 2 the poset P (2, n) is the Boolean poset of subsets of an n-element set ordered by inclusion. The classical theorem of Sperner [1, 2] asserts that the maximum size of an antichain in P (2, n) equals the middle binomial coefficient \binom{n}{⌊n/2⌋}. In the next lemma we obtain an upper bound for any k ≥ 2.

Lemma 2.3. If k ≥ 2, n ≥ 1 and X ⊂ P (k, n) is an antichain to ≤_{p}, then

|X| < \frac{(k/2) · k^{n}}{n^{1/2}} .

Proof. We proceed by induction on k. For k = 2 this bound holds by Sperner’s theorem because

\binom{n}{⌊n/2⌋} < \frac{2^{n}}{n^{1/2}}

for every n ≥ 1. Let k ≥ 3 and X ⊂ P (k, n) be an antichain. For A running through the subsets of [n] = {1, 2, …, n}, we partition X in the sets X_{A} where X_{A} consists of the u ∈ X satisfying u_{i} = k ⟺ i ∈ A. If we delete from all u ∈ X_{A} all appearances of k, we obtain (after appropriate relabelling of coordinates) a set of |X_{A}| distinct (n − |A|)-tuples from P (k − 1, n − |A|) that must be an antichain to ≤_{p}. Thus, by induction, for |A| < n we have

|X_{A}| < \frac{((k − 1)/2) · (k − 1)^{n−|A|}}{(n − |A|)^{1/2}}

and |X_{[n]}| ≤ 1. Summing over all As and using the inequality \sqrt{n/m} ≤ (n + 1)/(m + 1)

(which holds for 1 ≤ m ≤ n) and standard properties of binomial coefficients, we get

|X| = ∑_{A⊂[n]} |X_{A}|

< 1 + ∑_{i=0}^{n−1} \binom{n}{i}\frac{((k − 1)/2) · (k − 1)^{n−i}}{(n − i)^{1/2}}

= \frac{1}{\sqrt{n}} (\sqrt{n} + \frac{1}{2} ∑_{i=0}^{n−1} \binom{n}{i}\sqrt{n/(n − i)} · (k − 1)^{n−i+1})

≤ \frac{1}{\sqrt{n}} (\sqrt{n} + \frac{1}{2} ∑_{i=0}^{n−1} \binom{n + 1}{n − i + 1}(k − 1)^{n−i+1})

< \frac{k^{n+1}}{2\sqrt{n}}.

We conclude this section with three remarks as to the last lemma.

1. Various generalizations and strengthenings of Sperner’s theorem were intensively studied, see, e.g., the book of Engel and Gronau [2]. Therefore, we do not expect much originality in our bound.

2. It is clear that for k = 2 the exponent 1/2 of n in the bound of Lemma 2.3 cannot be increased. The same is true for any k ≥ 3. We briefly sketch a construction of a large antichain when k = 3; for k > 3 similar constructions can be given. For k = 3 and n = 3m ≥ 3 consider the set X ⊂ P (3, n) consisting of all u which have i 1s, n − 2i 2s and i 3s, where i = 1, 2, …, m = n/3. It follows that X is an antichain and that

|X| = ∑_{i=1}^{m} \binom{n}{i, i, n − 2i} = ∑_{i=1}^{m} \frac{n!}{(i!)^{2}(n − 2i)!}.

By the usual estimates of factorials, if m − \sqrt{n} < i ≤ m then

\binom{n}{i, i, n − 2i} ≫ \binom{n}{m, m, m} ≫ \frac{3^{n}}{n} .

Hence X is an antichain in P (3, n) with size

|X| ≫ \sqrt{n} · \frac{3^{n}}{n} = \frac{3^{n}}{\sqrt{n}}.

3. For composite k we can decrease the factor k/2 in the bound of Lemma 2.3. Suppose that k = lm where l ≥ m ≥ 2 are integers and let X ⊂ P (k, n) be an antichain. We associate with every u ∈ X the pair of n-tuples (v^{u}, w^{u}) ∈ P (m, n) × P (l, n) defined by v_{i}^{u} = u_{i} − m⌈u_{i}/m⌉ + m and w_{i}^{u} = ⌈u_{i}/m⌉, 1 ≤ i ≤ n. Note that the pair (v^{u}, w^{u}) uniquely determines u and that if w^{u} = w^{u′} then v^{u} and v^{u′} are incomparable by ≤_{p}. Thus, by Lemma 2.3, for fixed w ∈ P (l, n) there are less than (m/2)m^{n}/\sqrt{n} elements u ∈ X with w^{u} = w. The number of ws is at most |P (l, n)| = l^{n}. Hence

|X| < \frac{(m/2) · m^{n}}{n^{1/2}} · l^{n} = \frac{(m/2) · k^{n}}{n^{1/2}} .

In particular, if k is a power of 2 then |X| < k^{n}/\sqrt{n} for every antichain X ⊂ P (k, n).

3 The proof of Theorem 1.1

Let N = a(10^{n} − 1)/9 = aa ⋯ a, 1 ≤ a ≤ 9, be a rep-digit. Since K^{N} = aL^{n}, N is a Keith number if and only if the rep-unit M = (10^{n} − 1)/9 = 11 ⋯ 1 is a Keith number. Suppose that M is a Keith number: for some m we have

M = \frac{10^{n} − 1}{9} = L_{m}^{n} = 2^{m−n−1}(n − 1) (1 + O (\frac{m}{2^{n}} )) ,

where the asymptotic relation was proved in part (d) of Lemma 2.1. We rewrite this relation as

\frac{2^{2n+1−m}5^{n}}{9(n − 1)} − 1 = \frac{1}{9(n − 1)2^{m−n−1}} + O (\frac{m}{2^{n}} ) .

Since 2n < m < 7n by part (c) of Lemma 2.1, we get

\frac{2^{2n+1−m}5^{n}}{9(n − 1)} − 1 = O (\frac{n}{2^{n}} ) .

Because 5^{n} > 9(n−1) for every n ≥ 1, the left side is always non-zero (the power of 5 cannot be canceled). Writing it in the form e^{Λ} − 1 and using that e^{Λ} − 1 = O(Λ) (as Λ → 0), we get

0 ≠ Λ = (2n + 1 − m) log 2 + n log 5 − log(9(n − 1)) ≪ \frac{n}{2^{n}} .

Taking logarithms and applying Lemma 2.2, we finally obtain

−d(log n)^{2} < log |Λ| < c(log n − n log 2)

where c, d > 0 are effectively computable constants. This implies that n is effectively bounded and completes the proof of Theorem 1.1.

Remark. The same argument shows that for every integer b ≥ 3 there are only effectively finitely many base b rep-digits, i.e., positive integers of the form a(b^{n} − 1)/(b − 1) with a ∈ {1, …, b − 1}, which are base b Keith numbers. Indeed, we argue as for b = 10 and derive the equation

\frac{b^{n}}{(b − 1)(n − 1)2^{m−n−1}} − 1 = O(n/2^{n}).

In order to apply Lemma 2.2, we need to justify that the left side is not zero. If b is not a power of 2, it has an odd prime divisor p, and p^{n} cannot be cancelled, for big enough n, by (b − 1)(n − 1). If b ≥ 3 is a power of 2, then b − 1 is odd and has an odd prime divisor, which cannot be cancelled by the rest of the expression.

4 The proof of Theorem 1.2

For an integer N > 0, we denote by n the number of its digits: 10^{n−1} ≤ N < 10^{n}. We shall prove that there are ≪ 10^{n}/\sqrt{n} Keith numbers with n digits; it is easy to see that this implies Theorem 2. There are only few numbers with n digits and ≥ n/2 zero digits: their number is bounded by

∑_{i≥n/2} \binom{n}{i}9^{n−i} ≤ 2^{n}9^{n/2} = 6^{n} < (10^{n})^{0.8}.

Hence it suffices to count only the Keith numbers with n digits, of which at least half are nonzero.

Let N be a Keith number with n ≥ 3 digits, at least half of them nonzero. So, N = K_{m}^{N} for some index m ≥ 1. By part (c) of Lemma 2.1, 2n < m < 7n and we may use the asymptotic estimate in part (d). Setting k = ⌊n/2⌋ and using the inequality in part (a) of Lemma 2.1, we get

10^{n} > N = K_{m}^{N} ≥ L_{k+m−n}^{k}.

Part (d) of Lemma 2.1 gives that for big n,

L_{k+m−n}^{k} > \frac{2^{m−n−1}(k − 1)}{2} > \frac{2^{m−n}n}{12}.

On the other hand, the second inequality in part (b) of Lemma 2.1 and part (d) give, for big n,

10^{n−1} ≤ N = K_{m}^{N} ≤ 9L_{m}^{n} < 9 · 2^{m−n}n.

Combining the previous inequalities, we get

\frac{10^{n}}{90} < 2^{m−n}n < 12 · 10^{n}.

This implies that, for n > n_{0}, the index m attains at most 12 distinct values and

m = (1 + log 10/ log 2 + o(1))n = (κ + o(1))n.

Now we partition the set S of considered Keith numbers (with n digits, at least half of them nonzero) in blocks of numbers N having the same value of the index m and the same string of the first (most significant) k = ⌊n/2⌋ digits. So, we have at most 12 · 10^{k} blocks. We show in a moment that the numbers in one block B, when regarded as (n − k)- tuples from P (10, n − k), form an antichain to ≤_{p}. Assuming this, Lemma 2.3 implies that |B| < 10^{n−k+1}/2\sqrt{n − k}. Summing over all blocks, we get

|S| < 12 · 10^{k} · \frac{10^{n−k+1}}{2\sqrt{n − k}} ≪ \frac{10^{n}}{\sqrt{n}},

which proves Theorem 2.

To show that B is an antichain, we suppose for the contradiction that N_{1} and N_{2} are two Keith numbers from B with N_{1} <_{p} N_{2}. Let M = N_{2} − N_{1} and M^{∗} = 00 ⋯ 0M ∈ P (10, n) (we complete M to a string of length n by adding initial zeros). It follows that M has at most n − k digits and M < 10^{n−k}. On the other hand, by the linearity of recurrence and by N_{1} <_{p} N_{2}, we have

M = N_{2} − N_{1} = K_{m}^{N_{2}} − K_{m}^{N_{1}} = K_{m}^{M^{∗}}.

Since M^{∗} has some nonzero entry, the first inequality in part (b) of Lemma 2.1 and part (d) give, for big n,

K_{m}^{M^{∗}} ≥ L_{m−n}^{n} > 2^{m−2n−2}n.

Thus

10^{n−k} = 10^{n−⌊n/2⌋} > M > 2^{m−2n−2}n.

Using the above asymptotic estimate of m in terms of n, we arrive at the inequality

exp((\frac{1}{2} log 10 + o(1))n) > exp((κ log 2 − 2 log 2 + o(1))n)
= exp((log 5 + o(1))n)

that is contradictory for big n because 10^{1/2} < 5 = 10/2. This finishes the proof of Theorem 2.

Remark. The above proof generalizes, with small modifications, to all bases b ≥ 4. We replace base 10 by b, modify the proof accordingly, and have to satisfy two conditions. First, in the beginning of the proof we delete from the numbers with n base b digits those with > αn zero digits, for some constant 0 < α < 1. In order that we delete negligibly many, compared to b^{n}, numbers, we must have 2·(b−1)^{1−α} < b. Second, for the final contradiction we need that b^{α} < b/2. For b ≥ 5, both conditions are satisfied with α = 1/2, as in case b = 10. For b = 4 they are satisfied with α = 0.49, say. However, for b = 3 they cannot be satisfied by any α. Thus, the case b = 3 seems to require more substantial changes.

5 Acknowledgements

The first author acknowledges gratefully the institutional support to ITI by the grant 1M0021620808 of the Czech Ministry of Education. The second author was working on this paper during a visit to CRM in Montreal during Spring 2006. The hospitality and support of this institution is gratefully acknowledged. During the preparation of this paper, he was also supported in part by Grants SEP-CONACyT 46755, PAPIIT IN104005 and a Guggenheim Fellowship.

References

[1] M. Aigner and G. M. Ziegler, Proofs from The Book. Third edition, Springer, 2004.

[2] K. Engel, and H.-D. O. F. Gronau, Sperner Theory in Partially Ordered Sets, B. G. Teubner, 1985.

[3] M. Keith, Rep-digit numbers, J. of Recreational Mathematics 19 (1987), 41.

[4] M. Keith, Keith Numbers, manuscript electronically published at

http://users.aol.com/s6sj7gt/mikekeit.htm

[5] F. Luca, Fibonacci and Lucas numbers with only one distinct digit, Port. Math. (N. S.) 57 (2000), 243–254.

[6] E. M. Matveev, An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II, Izv. Ross. Akad. Nauk Ser. Math. 64 (2000), 125–180; English translation in Izv. Math. 64 (2000), 1217–1269.

[7] C. Pickover, All known replicating Fibonacci digits less than one billion, J. of Recreational Mathematics 22 (1990), 176.

[8] C. Pickover, Computers and the Imagination, St. Martin’s Press, 1991; page 229.

[9] C. Pickover, Wonders of Numbers. Adventures in Mathematics, Mind and Meaning, Oxford University Press, 2001; pages 174–175.

[10] K. Sherriff, Computing replicating Fibonacci digits, J. of Recreational Mathematics, 26 (1994), 191.

[11] N. Sloane, The Encyclopedia of Integer Sequences, electronically published at

http://www.research.att.com/∼njas/sequences/

2000 Mathematics Subject Classification: Primary 11B39; Secondary 11A63. Keywords: Keith number, density, generalized Fibonacci recurrence.

(Concerned with sequence \underline{A007629}.)

Received September 21 2006; revised version received January 16 2007. Published in Journal of Integer Sequences, January 17 2007.

Return to Journal of Integer Sequences home page.