\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Counting Keith Numbers } \vskip 1cm \large { Martin Klazar \\ Department of Applied Mathematics and\\ Institute for Theoretical Computer Science (ITI)\\ Faculty of Mathematics and Physics \\ Charles University \\ Malostransk\'e n\'am. 25 \\ 11800 Praha \\ Czech Republic \\ \href{mailto:klazar@kam.mff.cuni.cz}{\tt klazar@kam.mff.cuni.cz}\\ \ \\ Florian Luca \\ Instituto de Matem{\'a}ticas\\ Universidad Nacional Autonoma de M{\'e}xico \\ C.P. 58089 \\ Morelia, Michoac{\'a}n \\ M\'exico \\ \href{mailto:fluca@matmor.unam.mx}{\tt fluca@matmor.unam.mx} } \end{center} \vskip .2 in \begin{abstract} A Keith number is a positive integer $N$ with the decimal representation $a_1a_2\cdots a_n$ such that $n\ge 2$ and $N$ appears in the sequence $(K_m)_{m\ge 1}$ given by the recurrence $K_1=a_1,\dots,K_n=a_n$ and $K_m=K_{m-1}+K_{m-2}+\cdots+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=\cdots=a_n$), and that the set of Keith numbers is of asymptotic density zero. \end{abstract} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] %\usepackage{amsmath,amssymb,amsbsy,amsfonts,amsthm,latexsym,amsopn,amstext,amsxtra,euscript,amscd} %\newtheorem{lem}{Lemma} %\newtheorem{lemma}[lem]{Lemma} %\newtheorem{prop}{Proposition} %\newtheorem{proposition}[prop]{Proposition} %\newtheorem{thm}{Theorem} %\newtheorem{theorem}[thm]{Theorem} %\newtheorem{cor}{Corollary} %\newtheorem{corollary}[cor]{Corollary} %\newtheorem{prob}{Problem} %\newtheorem{problem}[prob]{Problem} %\newtheorem{ques}{Question} %\newtheorem{question}[ques]{Question} %% DEFINITIONS \def\mand{\qquad\mbox{and}\qquad} \def\scr{\scriptstyle} \def\\{\cr} \def\({\left(} \def\){\right)} \def\[{\left[} \def\]{\right]} \def\<{\langle} \def\>{\rangle} \def\fl#1{\left\lfloor#1\right\rfloor} \def\rf#1{\left\lceil#1\right\rceil} \def\cA{{\mathcal A}} \def\cB{{\mathcal B}} \def\cC{{\mathcal C}} \def\cE{{\mathcal E}} \def\cF{{\mathcal F}} \def\cI{{\mathcal I}} \def\cL{{\mathcal L}} \def\cM{{\mathcal M}} \def\cN{{\mathcal N}} \def\cR{{\mathcal R}} \def\cS{{\mathcal S}} \def\cP{{\mathcal P}} \def\cQ{{\mathcal Q}} \def\cT{{\mathcal T}} \def\cX{{\mathcal X}} \def\N{{\mathbb N}} \def\Z{{\mathbb Z}} \def\eps{\varepsilon} \newcommand{\comm}[1]{\marginpar{\fbox{#1}}} \def\xxx{\vskip5pt\hrule\vskip5pt} \def\yyy{\vskip5pt\hrule\vskip2pt\hrule\vskip5pt} \section{Introduction} With the number $197$, let $(K_m)_{m\ge 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,\ldots $$ Note that $197$ itself is a member of this sequence. This phenomenon was first noticed by Mike Keith and such numbers are now called {\it Keith numbers}. More precisely, a number $N$ with decimal representation $a_1a_2\cdots a_n$ is a Keith number if $n\ge 2$ and $N$ appears in the sequence $K^N=(K^N_m)_{m\ge 1}$ whose $n$ initial terms are the digits of $N$ read from left to right and satisfying $K^N_m=K^N_{m-1}+K^N_{m-2}+\cdots+K^N_{m-n}$ for all $m>n$. These numbers appear in Keith's papers \cite{Ke1, Ke2} and they are the subject of entry $A007629$ in Neil Sloane's Encyclopedia of Integer Sequences \cite{Slo} (see also \cite{Pick1, Pick2, Pick3}). \medskip Let ${\cal K}$ be the set of all Keith numbers. It is not known if ${\cal K}$ is infinite or not. The sequence ${\cal K}$ begins $$ 14,~19,~28,~47,~61,~75,~197,~742,~1104,~1537,~2208, 2580,~3684,~4788,\dots $$ M. Keith and D. Lichtblau found all $94$ Keith numbers smaller than $10^{29}$ \cite{Ke2}. D. Lichtblau found the first {\em pandigital} Keith number (containing each of the digits 0 to 9 at least once): $27847652577905793413$. \medskip Recall that a rep-digit is a positive integer $N$ of the form $a(10^n-1)/9$ for some $a\in \{1,\ldots,9\}$ and $n\ge 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. \begin{theorem} \label{thm:krepu} There are only finitely many Keith numbers that are rep-digits and their set can be effectively determined. \end{theorem} We point out that some authors refer to the Keith numbers as {\it replicating Fibonacci digits} in analogy with the Fibonacci sequence $(F_n)_{n\ge 1}$ given by $F_1=1,~F_2=1$ and $F_{n+2}=F_{n+1}+F_n$ for all $n\ge 1$. F. Luca showed \cite{Lu2} that the largest rep-digit Fibonacci number is $55$. \medskip The proof of Theorem \ref{thm:krepu} uses Baker-type estimates for linear forms in logarithms. It will be clear from the proof that it applies to all {\it base $b$ Keith numbers} for any fixed integer $b\ge 3$, where these numbers are defined analogously starting with their base $b$ expansion (see the remark after the proof of Theorem \ref{thm:krepu}). \medskip For a positive integer $x$ we write ${\cal K}(x)={\cal K}\cap [1,x]$. As we mentioned before, ${\cal K}(10^{29})=94$. A heuristic argument \cite{Ke2} suggests that $\#{\cal K}(x)\gg \log x$, and, in particular, that ${\cal K}$ should be infinite. Going in the opposite way, we show that ${\cal K}$ is of asymptotic density zero. \begin{theorem} \label{thm:countKeith} The estimate $$ \#{\cal K}(x)\ll \frac{x}{\sqrt{\log x}} $$ holds for all positive integers $x\ge 2$. \end{theorem} The above estimate is very weak. It does not even imply that that sum of the reciprocals of the members of ${\cal K}$ is convergent. We leave to the reader the task of finding a better upper bound on $\#{\cal K}(x)$. Typographical changes (see the remark after the proof of Theorem \ref{thm:countKeith}) show that Theorem \ref{thm:countKeith} also is valid for the set of base $b$ Keith numbers if $b\ge 4$. Perhaps it can be extended also to the case $b=3$. For $b=2$, Kenneth Fan has an unpublished manuscript (mentioned by Keith \cite{Ke2}) 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. \medskip Throughout this paper, we use the Vinogradov symbols $\gg$ and $\ll$ as well as the Landau symbols $O$ and $o$ with their usual meaning. Recall that for functions $A$ and $B$ the inequalities $A\ll B$, $B\gg A$ and $A=O(B)$ are all equivalent to the fact that there exists a positive constant $c$ such that the inequality $|A|\le 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 ${\cal A}$, we use $\#{\cal A}$ and $|{\cal A}|$ to denote its cardinality. \section{Preliminary Results} For an integer $N>0$, recall the definition of the sequence $K^N=(K^N_m)_{m\ge 1}$ given in the Introduction. In $K^N$ we allow $N$ to be any string of the digits $0,1,\dots,9$, so $N$ may have initial zeros. So, for example, $K^{020}=(0,2,0,2,4,6,12,22,\dots)$. For $n\ge 1$ we define the sequence $L^n$ as $L^n=K^M$ where $M=11\cdots 1$ with $n$ digits $1$. In particular, $L^1=(1,1,1,\dots)$ and $L^2=(1,1,2,3,5,8,\dots)$, 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$. \begin{lemma}\label{simplelemma} Let $N$ be a string of the digits $0,1,\dots,9$ with length $n\ge 1$. If $N$ does not start with $0$, we understand it also as the decimal representation of a positive integer. \begin{description} \item[(a)] If $N$ has at least $k\ge 1$ nonzero entries, then $K^N_m\ge L^k_{k+m-n}$ holds for every $m\ge n+1$. \item[(b)] If $N$ has at least one nonzero entry, then $K^N_m\ge L^n_{m-n}$ holds for every $m\ge n+1$. We have $K^N_m\le 9L^n_m$ for every $m\ge 1$. \item[(c)] If $n\ge 3$ and $N=K^N_m$ for some $m\ge 1$ (so $N$ is a Keith number), then $2nn+k$ it holds by induction. \medskip (b). We have $K^N_m\ge 1=L^n_{m-n}$ for $m=n+1,n+2,\dots,2n$ and the inequality holds. For $m>2n$ it holds by induction. The second inequality follows easily by induction. \medskip (c). The lower bound $m>2n$ follows from the fact that $K^N$ is nondecreasing and that $$ K^N_{2n}\le 9L^n_{2n}=9\cdot2^{n-1}(n-1)+9<10^{n-1}\le N $$ for $n\ge 3$. To obtain the upper bound, note that for $m\ge n$ we have by induction that $L^n_m\ge L^2_{m-n+2}\ge\phi^{m-n}$ where $\phi=1.61803\cdots$ is the golden ratio. Thus, by part (b), $$ 10^n>N=K^N_m\ge L^n_{m-n}\ge\phi^{m-2n} $$ and $m<(2+\log 10/\log\phi)n<7n$. \medskip (d). We write $L^n_m$ in the form $L^n_m=(2^{m-n-1}-d(m))(n-1)+1$ and prove by induction on $m$ that for $m\ge n+1$, $$ 0\le d(m)0$ is a constant and $\alpha<2$ is the only positive root of the polynomial $x^n-x^{n-1}-\cdots-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^n_m$ is very precise and useful, as we shall demonstrate in the proofs of Theorems \ref{thm:krepu} and \ref{thm:countKeith}. \medskip In the proof of Theorem \ref{thm:krepu} 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 \cite[Corollary 2.3]{Mat}. \begin{lemma} \label{lem:linearform} Let $A_1,\dots,A_k$, $A_i>1$, and $n_1,\dots,n_k$ be integers, and let $N=\max\{|n_1|,\ldots,|n_k|,2\}$. There exist positive absolute constants $c_1$ and $c_2$ (which are effective), such that if $$ \Lambda=n_1\log A_1+n_2\log A_2+\cdots+n_k\log A_k\ne 0, $$ then $$ \log |\Lambda|>-c_1 c_2^k (\log A_1)\cdots (\log A_k)\log N. $$ \end{lemma} 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,\dots,k\}^n,\le_p) $$ where $\le_p$ is the product ordering $$ a=(a_1,a_2,\dots, a_n)\le_p b=(b_1,b_2,\dots, b_n)\iff a_i\le b_i\mbox{ for } i=1,2,\dots,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 \cite{aign_zieg, sperner_theory} asserts that the maximum size of an antichain in $P(2,n)$ equals the middle binomial coefficient $\binom{n}{\lfloor n/2\rfloor}$. In the next lemma we obtain an upper bound for any $k\ge 2$. \begin{lemma}\label{antichains} If $k\ge 2, n\ge 1$ and $X\subset P(k,n)$ is an antichain to $\le_p$, then $$ |X|<\frac{(k/2)\cdot k^n}{n^{1/2}}. $$ \end{lemma} \begin{proof} We proceed by induction on $k$. For $k=2$ this bound holds by Sperner's theorem because $$ \binom{n}{\lfloor n/2\rfloor}<\frac{2^n}{n^{1/2}} $$ for every $n\ge 1$. Let $k\ge 3$ and $X\subset P(k,n)$ be an antichain. For $A$ running through the subsets of $[n]=\{1,2,\dots,n\}$, we partition $X$ in the sets $X_A$ where $X_A$ consists of the $u\in X$ satisfying $u_i=k\iff i\in A$. If we delete from all $u\in 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 $\le_p$. Thus, by induction, for $|A|3$ similar constructions can be given. For $k=3$ and $n=3m\ge 3$ consider the set $X\subset P(3,n)$ consisting of all $u$ which have $i$ $1$s, $n-2i$ $2$s and $i$ $3$s, where $i=1,2,\dots,m=n/3$. It follows that $X$ is an antichain and that $$ |X|=\sum_{i=1}^m\binom{n}{i,i,n-2i}=\sum_{i=1}^m\frac{n!}{(i!)^2(n-2i)!}. $$ By the usual estimates of factorials, if $m-\sqrt{n}9(n-1)$ for every $n\ge 1$, the left side is always non-zero (the power of $5$ cannot be canceled). Writing it in the form $e^{\Lambda}-1$ and using that $e^{\Lambda}-1=O(\Lambda)$ (as $\Lambda\to 0$), we get $$ 0\ne\Lambda=(2n+1-m)\log 2+n\log 5-\log(9(n-1))\ll\frac{n}{2^n}. $$ Taking logarithms and applying Lemma \ref{lem:linearform}, we finally obtain $$ -d(\log n)^2<\log|\Lambda|0$ are effectively computable constants. This implies that $n$ is effectively bounded and completes the proof of Theorem~\ref{thm:krepu}. \qed \medskip \noindent {\bf Remark.} The same argument shows that for every integer $b\ge 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\in \{1,\ldots,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 \ref{lem:linearform}, 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\ge 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. \section{The proof of Theorem \ref{thm:countKeith}} \noindent For an integer $N>0$, we denote by $n$ the number of its digits: $10^{n-1}\le N<10^{n}$. We shall prove that there are $\ll 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 $\ge n/2$ zero digits: their number is bounded by $$ \sum_{i\ge n/2}\binom{n}{i}9^{n-i}\le 2^n9^{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. \medskip Let $N$ be a Keith number with $n\ge 3$ digits, at least half of them nonzero. So, $N=K^N_m$ for some index $m\ge 1$. By part (c) of Lemma~\ref{simplelemma}, $2nN=K^N_m\ge L^k_{k+m-n}. $$ Part (d) of Lemma~\ref{simplelemma} gives that for big $n$, $$ L^k_{k+m-n}>\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~\ref{simplelemma} and part (d) give, for big $n$, $$ 10^{n-1}\le N=K^N_m\le 9L^n_m<9\cdot 2^{m-n}n. $$ Combining the previous inequalities, we get $$ \frac{10^n}{90}<2^{m-n}n<12\cdot 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=(\kappa+o(1))n. $$ \medskip 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=\lfloor n/2\rfloor$ digits. So, we have at most $12\cdot 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 $\le_p$. Assuming this, Lemma~\ref{antichains} implies that $|B|<10^{n-k+1}/2\sqrt{n-k}$. Summing over all blocks, we get $$ |S|<12\cdot 10 ^k\cdot \frac{10^{n-k+1}}{2\sqrt{n-k}}\ll \frac{10^{n}}{\sqrt{n}}, $$ which proves Theorem 2. \medskip 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\cdots 0M\in 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^{N_2}_m-K^{N_1}_m=K^{M^*}_m. $$ Since $M^*$ has some nonzero entry, the first inequality in part (b) of Lemma~\ref{simplelemma} and part (d) give, for big $n$, $$ K^{M^*}_m\ge L^n_{m-n}>2^{m-2n-2}n. $$ Thus $$ 10^{n-k}=10^{n-\lfloor n/2\rfloor}>M>2^{m-2n-2}n. $$ Using the above asymptotic estimate of $m$ in terms of $n$, we arrive at the inequality \begin{eqnarray*} \exp(({\textstyle\frac{1}{2}}\log 10+o(1))n)&>& \exp((\kappa\log 2-2\log2+o(1))n)\\ &=&\exp((\log 5+o(1))n) \end{eqnarray*} that is contradictory for big $n$ because $10^{1/2}<5=10/2$. This finishes the proof of Theorem 2. \qed \medskip \noindent {\bf Remark.} The above proof generalizes, with small modifications, to all bases $b\ge 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 $>\alpha n$ zero digits, for some constant $0<\alpha<1$. In order that we delete negligibly many, compared to $b^n$, numbers, we must have $2\cdot (b-1)^{1-\alpha}