\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} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{defin}[theorem]{Definition} \newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}} \newtheorem{examp}[theorem]{Example} \newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}} \newtheorem{rema}[theorem]{Remark} \newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}} \begin{center} \vskip 1cm{\LARGE\bf Smallest Examples of Strings of Consecutive \\ \vskip .1in Happy Numbers } \vskip 1cm \large Robert Styer \\ Department of Mathematical Sciences \\ Villanova University\\ Villanova, PA 19085 \\ USA \\ \href{mailto:robert.styer@villanova.edu}{\tt robert.styer@villanova.edu} \\ \end{center} \vskip .2in \begin{abstract} A happy number $N$ is defined by the condition $S^n(N)= 1$ for some number $n$ of iterations of the function $S$, where $S(N)$ is the sum of the squares of the digits of $N$. Up to $10^{20}$, the longest known string of consecutive happy numbers was length five. We find the smallest string of consecutive happy numbers of length 6, 7, 8, \dots, 13. For instance, the smallest string of six consecutive happy numbers begins with $N = 7899999999999959999999996$. We also find the smallest sequence of 3-consecutive cubic happy numbers of lengths 4, 5, 6, 7, 8, and 9. \end{abstract} \section{Introduction} Many recreational math problems deal with various combinations of digits. Let $N = \sum_{j=0}^n a_j 10^j$ with $0 \le a_j \le 9$ be the decimal expansion of N. Define $S(N) = \sum_{j=0}^n a_j^2$, and define $S^k$ to be the $k$-fold iterate of $S$. Honsberger~\cite{hon} (see also Beardon~\cite{be} and Grundman and Teeple~\cite{gt1}) gives a simple proof that, for every positive integer $N$, there is a positive integer $k$ such that either $S^k(N) = 1$, a fixed point, or $S^k(N) = 4$, which is part of the 8-cycle $\{16, 37, 58, 89, 145, 42, 20, 4\}$. We say a number is happy if the iterates are eventually equal to the fixed point 1. The first happy number bigger than 1 is 7, and indeed, it seems that about 1 out of 7 numbers is happy~\cite{guy}. The smallest pair of consecutive numbers is $31$ and $32$, and the smallest with 3, 4 or 5 consecutive happy numbers were known; for example, $44488$, $44489$, $44490$, $44491$, $44492$ is the smallest string of five consecutive happy numbers. Guy~\cite{guy} asked how many consecutive happy numbers one can have, and noted that Jud McCranie calculated that up to $10^{20}$ the longest consecutive string is only of length five. El-Sedy and Siksek~\cite{es} published the first proof that there can be arbitrarily long strings of consecutive happy numbers (although H. Lenstra knew a proof earlier; Teeple generalized his unpublished proof in her undergraduate honors thesis~\cite{tee}.) See also Grundman and Teeple~\cite{gt2,gt3}, and Pan~\cite{pan}. Their techniques do not come remotely close to finding the least examples, however, and we propose to find the smallest instance of six or more consecutive happy numbers. J.\ A.\ Littlewood said \lq\lq A technique is a trick used more than once.'' In their paper on happy numbers, El-Sedy and Siksek~\cite{es} end their paper by using a trick to calculate a huge number $l=\sum_{r=1}^{233192} 9 \cdot 10^{4+r} + 20958$ with certain properties that are critical to their proof. We can transform their trick into a technique that could be used to calculate a much smaller value for a number $l$ with their desired properties; the minimal example is $l = 4699999990999999999969$. With this technique, we calculate the smallest $N$ beginning a sequence of 6 to 13 consecutive happy numbers. We use a period as the concatenation operator, and list the number of nine digits in parentheses. For example, $N = 58.(11 {\rm \ nines}).6.(144 {\rm \ nines}).5$ means $$N = 58 \cdot 10^{157} + 10^{146}(10^{11}-1) + 6 \cdot 10^{145} + 10 (10^{144}-1) + 5$$ that is, a 159 digit number given by the digits 58 followed by eleven digits 9, then the digit 6, then one hundred forty-four digits 9, and ending with the digit 5. In this table, $n$ is the length of the sequence of consecutive happy numbers, $digits$ is the number of digits in each member of the sequence, and $N$ is the first number of the sequence of $n$ consecutive happy numbers. \begin{center} \begin{tabular}{|r|r|c|} \hline $n$ & $digits$ & $N$ \\ \hline 2 & 2 & 31 \\ \hline 3 & 4 & 1880 \\ \hline 4 & 4 & 7839 \\ \hline 5 & 5 & 44488 \\ \hline 6 & 25 & 7899999999999959999999996 \\ \hline 7 & 25 & 7899999999999959999999996 \\ \hline 8 & 159 & 58.(11 {\rm \ nines}).6.(144 {\rm \ nines}).5 \\ \hline 9 & 215 & 26.(137 {\rm \ nines}).7.(74 {\rm \ nines}).5 \\ \hline 10 & 651 & 38.(560 {\rm \ nines}).0.(87 {\rm \ nines}).5 \\ \hline 11 & 1571 & 27.(280 {\rm \ nines}).0.(1287 {\rm \ nines}).4 \\ \hline 12 & 158162 & 388.(158021 {\rm \ nines}).8.(136 {\rm \ nines}).4 \\ \hline 13 & 603699 &288.(218491 {\rm \ nines}).3.(385203 {\rm \ nines}).3 \\ \hline \end{tabular} \end{center} \section{Six Consecutive Happy Numbers} In this section we prove the following proposition for six consecutive happy numbers. \begin{proposition} $N_0 = 7899999999999959999999996$ is the smallest number that begins a sequence of six consecutive happy numbers. \end{proposition} It is easy to verify that each of these is a happy number: \bigskip \begin{tabular}{c} 7899999999999959999999996 \\ 7899999999999959999999997 \\ 7899999999999959999999998 \\ 7899999999999959999999999 \\ 7899999999999960000000000 \\ 7899999999999960000000001 \\ \end{tabular} \bigskip Note that these are 25 digit numbers, so if there were a smaller $N$ beginning a sequence of six consecutive happy numbers, it must have $S(N) < 2025=25 \cdot 9^2$. El-Sedy and Siksek~\cite{es} note the following: \begin{lemma} If $N_1$ and $N_2$ are natural numbers with $N_2< 10^k$ then $S(N_1*10^k + N_2) = S(N_1) + S(N_2)$. \end{lemma} % L 1 Let $N \le 7899999999999959999999996$ begin a string of six consecutive happy numbers. Let $N = N_1.d_0$ where $d_0$ is the final digit of $N$, and $N_1$ is formed from the rest of the digits. We organize our proof of the proposition by looking at the various possibilities for $d_0$. Let $M_1 = S(N_1)$. Then $S(N) = M_1 + S(d_0)$ and, as noted above, we may assume $M_1<2025$. \begin{lemma} Let $N \le 7899999999999959999999996$ and $N = N_1.d_0$. If $d_0=0$, one can have at most three successive happy numbers, $N$, $N+1$, $N+2$. \end{lemma} %L 2 % \begin{proof} Proof: Suppose the last digit of $N$ is $d_0=0$. Note that $S(N) = S(N_1)= M_1$, $S(N+1)=S(N_1) + 1^2 = M_1 + 1^2$, $S(N+2)=S(N_1) + 2^2 = M_1 + 2^2$, and $S(N+3)=S(N_1) + 3^2 = M_1 + 3^2$. We simply calculate that $M_1$, $M_1+1^2$, $M_1+2^2$ and $M_1+3^2$ are not simultaneously happy for any $M_1<2025$. (For the relevant Maple programs, see~\cite{st}.) % \end{proof} \begin{lemma} Let $N \le 7899999999999959999999996$ and $N = N_1.d_0$. Suppose $d_0 = 1$, $2$, $3$, $4$ or $5$. Then there are at most four consecutive happy numbers beginning at $N$. \end{lemma} % L 3 %\begin{proof} Proof: We check if $M_1+d_0^2$, $M_1+(d_0+1)^2$, $M_1+(d_0+2)^2$, $M_1+(d_0+3)^2$ and $M_1+(d_0+4)^2$ are simultaneously happy for any value of $M_1 \le 2025$; our calculations show there are at most four consecutive happy numbers for $N$ with $d_0=1$, 2, 3, 4 or 5. %\end{proof} \begin{lemma} Let $N \le 7899999999999959999999996$ and $N = N_1.d_0$. Suppose $d_0 = 8$ or $9$. Then there are at most five consecutive happy numbers beginning at $N$. \end{lemma} % L 4 %\begin{proof} Proof: Suppose $N$ has final digit $d_0 = 8$. Then $N+2$ would have final digit 0, so by Lemma 2, the sequence can extend to at most $N+4$. Similarly, if $d_0 = 9$ then $N+1$ has final digit 0 and by Lemma 2 the sequence extends to at most $N+3$. In neither case can we have six consecutive happy numbers. This proves the lemma. %\end{proof} \begin{lemma} Let $N \le 7899999999999959999999996$ and $N = N_1.d_0$. Suppose $d_0 = 7$. Then there are at most five consecutive happy numbers beginning at $N$. \end{lemma} % L 5 %\begin{proof} Proof: Suppose $N$ ends in the digit $d_0=7$. Using a Maple program, we checked for three consecutive happy numbers, that is, we checked if $M_1 + 7^2$, $M_1+8^2$, and $M_1+9^2$ are all happy for some $M_1<2025$. There are three cases: $M_1 = 568$, 574 and 1839. We now show that $M_1 = 568$ cannot yield three happy numbers \lq\lq after the carry.'' Note that $N+3 = (N_1 + 1).0$. Set $N_1 = N_2.d.9 \dots 9$ where digit $d \le 8$, and by convention $N_2=0$ if $N_2$ is empty, and $N_2=0$ and $d=0$ if both are empty. Let $k$ be the number of digits of 9 ending $N_1$. Then $S(N_1) = S(N_2) +d^2+ 9^2 k$, so $S(N_2) = S(N_1) - d^2 - 9^2 k$. Also, $N_1+1 = N_2.(d+1).0 \dots 0$ with $k$ zeros at the end, so $S(N_1+1) = S(N_2) + (d+1)^2$. Thus, $S(N_1+1) = S(N_1) + (d+1)^2 - d^2 - 9^2 k = S(N_1) + (2d+1) - 9^2 k$. Since $M_1 = S(N_1) = S(N_2)+d^2+ 9^2 k = 568$, we have $9^2 k \le 568$ so $k \le 7$. We now look for values $(k,d)$, with $0 \le k \le 7$ and $0 \le d \le 8$, for which these three are happy: \begin{tabular}{l} $S(N+3) = M_1+2d+1-81k+0^2$, \\ $S(N+4) = M_1+2d+1-81k+1^2$, \\ $S(N+5) = M_1+2d+1-81k+2^2$. \\ \end{tabular} \noindent A simple computer search shows that this never happens. Similarly, when $M_1=574$ there are no pairs $(k,d)$ giving three consecutive happy numbers \lq\lq after the carry.'' When $M_1 = 1839$, however, we have one solution, namely $k=9$, $d=5$, and $S(N_2) = 1085$. Using the methods described in the next section, we find that the minimal value for $N_2$ with $S(N_2) = 1085$ is $N_2 = 78999999999999$. Thus, $N = N2.d.9 \dots 9.7 = 7899999999999959999999997$ which of course is one more than the minimal case we find in the next lemma. %\end{proof} \begin{lemma} Let $N \le 7899999999999959999999996$ and $N = N_1.d_0$. Suppose $d_0 = 6$. Then there are at most five consecutive happy numbers beginning at $N$, unless $$N = 7899999999999959999999996$$ which begins a sequence of six consecutive happy numbers. \end{lemma} % L 6 %begin{proof} Proof: Suppose $N$ ends in the digit $d_0=6$. We check for four consecutive happy numbers, that is, we check whether $M_1 + 6^2$, $M_1+7^2$, $M_1 + 8^2$ and $M_1+9^2$ are happy for any $M_1<2025$. We find one case: $M_1= 1839$. As before, set $N_1 = N_2.d.9 \dots 9$ where digit $d \le 8$, and by convention $N_2=0$ if $N_2$ is empty and $N_2=0$ and $d=0$ if both are empty. Let $k$ be the number of digits of 9 ending $N_1$. Then as before, $S(N_1+1) = S(N_1) + (2d+1) - 9^2 k$. Since $M_1 = S(N_1) = S(N_2)+d^2+ 9^2 k = 1839$, we have $9^2 k \le 1839$ so $k \le 22$. We now look for values $(k,d)$, with $0 \le k \le 22$ and $0 \le d \le 8$, for which these two are happy: \begin{tabular}{l} $S(N+4) = M_1+2d+1-81k+0^2$, \\ $S(N+5) = M_1+2d+1-81k+1^2$. \\ \end{tabular} Our search yields five pairs, $(k,d)$, each corresponding to a string of six consecutive happy numbers. We list these pairs along with the corresponding values of $S(N-2)$ in the table, below. For each value $S(N_2)$, we list the least value of $N_2$ possible, computed using the methods of the next section, then list the resulting value of $N$. \bigskip \begin{center} \begin{tabular}{|r|c|r|r|r|} \hline $k$ & $d$ & $S(N_2)$ & least $N_2$ for $S(N_2)$ & $N$ \\ \hline 1 & 6 & 1722 & 27799999999999999999999 & 27799999999999999999999696 \\ \hline 5 & 6 & 1398 & 2779999999999999999 & 27799999999999999996999996 \\ \hline 9 & 5 & 1085 & 78999999999999 & 7899999999999959999999996 \\ \hline 15 & 6 & 588 & 277999999 & 27799999969999999999999996 \\ \hline 19 & 0 & 300 & 57899 & 57899099999999999999999996 \\ \hline \end{tabular} \end{center} \bigskip We see that the smallest $N$ corresponds to $k=9$ and $d=5$. Thus, we have proven that the smallest $N$ beginning a sequence of six happy numbers is $7899999999999959999999996$. %\end{proof} \begin{corollary} $N_0 = 7899999999999959999999996$ is the smallest number that begins a sequence of seven consecutive happy numbers. \end{corollary} % \begin{proof} Proof: It is easy to verify that $7899999999999960000000002$ is a happy number. Amazingly, the same value of $N$ that begins the least sequence of six consecutive happy numbers also begins the least sequence of seven consecutive happy numbers. % \end{proof} Similar arguments prove that the values of $N$ given in the table in Section 1 are indeed the smallest beginning sequences of 8, 9, 10, 11, 12, and 13 consecutive happy numbers. Maple worksheets on the author's homepage~\cite{st} contain the calculations. The optimal example for 14 consecutive happy numbers seems to be the 34567901197532 digit number $ 7.(2098518518492 {\rm \ nines}).8.(32469382679037 {\rm \ nines}).3$ which is clearly too large to checked by these techniques. \section{Minimal $N$ with $S(N) = n$} Given a positive integer $n$, we want to determine the least $N$ such that $S(N) = n$. Define $L(n) = \min \{ N | S(N) = n \}$. Clearly, if $n_1 \ne n_2$ then $L(n_1) \ne L(n_2)$. Also, $L(n)$ has no zero digits and its digits are in nondecreasing order. We now show how to calculate $L(n)$. \begin{lemma} The largest $n_0$ for which $L(n_0)$ has no digit of 9 is $n_0 = 448$. \end{lemma} % L 7 %\begin{proof} Proof: We already noted that $L(n)$ has no digit 0. We claim that $L(n)$ cannot contain more than one digit 5, no more than two digits 3, no more than three digits 1 or 2 or 4 or 6 or 7, nor more than seven digits 8. This follows from the observations that $S(1111) = S(2)$, $S(2222) = S(4)$, $S(333) = S(115)$, $S(4444) = S(8)$, $S(55) = S(17)$, $S(6666)=S(488)$, $S(7777) = S(2888)$ and $S(88888888) = S(15999999)$. Thus, if $L(n)$ does not contain the digit 9, it cannot exceed $$1112223344456667778888888.$$ Note that $S(1112223344456667778888888) = 809$ so if $n>809$ then $L(n)$ has at least one digit 9. We now find all values of $L(n)$ for $n \le 809$. Clearly, $L(1)=1$, $L(2)=11$, $L(3) = 111$ and $L(4) = 2$. If $d_0$ is the last digit of $L(n)$ and $n>d_0^2$, then $L(n-d_0^2)$ must be $(L(n)-d_0)/10$ (i.e., remove the last digit of $L(n)$). Of course, we do not know what the last digit is, so we look at $L(n-d^2)\cdot 10 + d$ for each potential last digit $d$. If we know $L(k)$ for all $k 448$, the last digit of $L(n)$ must be a nine, so $L(n) = L(n-9^2) \cdot 10 + 9$. We proceed by induction on $q$. If $q=1$, then $L(n) = L(n- 9^2) \cdot 10 + 9 = L(n_0)+(10^1 -1)$. Assuming the inductive hypothesis, $L(n - 9^2) = L(n_0) \cdot 10^{q-1} + ( 10^{q-1} - 1)$, and so $L(n) = L(n-9^2) \cdot 10 + 9 = L(n_0) \cdot 10^{q-1+1} + (10^{q-1} -1) \cdot 10 +9 = L(n_0) \cdot 10^q + (10^q -1)$. In other words, $L(n)$ is simply $q$ digits of 9 concatenated to the end of $L(n_0)$. This ends our proof. %\end{proof} In Section 4, we will need the cubic happy number analogies to Lemmas 7 and 8. Define $L_3(n) = \min \{ N | S_{3,10}(N) = n\}$ where $S_{3,10} ( \sum_{i=0}^n a_i 10^i) = \sum_{i=0}^n a_i^3$. We can show that the cubic case analog to the quadratic extremal case $N = 1112223344456667778888888$ above is $$N = 11111112222223333444445555666777777888888888$$ which has $S(N) = 8297$. Arguments analogous to those in Lemmas 7 and 8 show the following: \begin{lemma} The largest $n_0$ for which $L_3(n_0)$ has no digit of 9 is $n_0 = 4609$. For $n \ge 5832$, let $q = \lfloor{n \over 9^3}\rfloor - 7$ and $n_0 = n- 9^3 q$. Then $L_3(n) = L_3(n_0)\cdot 10^{q} + (10^{q} -1)$. \end{lemma} % L 9 As an aside, we provide a table of the largest $n$ for which $L(n)$ does not contain certain digits, and the corresponding table for $L_3(n)$. \bigskip \begin{center} \begin{tabular}{|c|r|r|} \hline largest allowable digit in $L(n)$ & $n_{max}$ & $L(n_{max})$ \\ \hline 1 & 3 & 111 \\ \hline 2 & 12 &222 \\ \hline 3 & 23 & 1233 \\ \hline 4 & 48 & 444 \\ \hline 5 & 48 & 444 \\ \hline 6 & 112 & 2666 \\ \hline 7 & 151 & 2777 \\ \hline 8 & 448 & 8888888 \\ \hline \end{tabular} \end{center} \bigskip \begin{center} \begin{tabular}{|c|r|r|} \hline largest allowable digit in $L_3(n)$ & $n_{max}$ & $L_3(n_{max})$ \\ \hline 1 & 7 & 1111111 \\ \hline 2 & 50 & 11222222 \\ \hline 3 & 124 & 223333 \\ \hline 4 & 329 & 1244444 \\ \hline 5 & 572 & 245555 \\ \hline 6 & 932 & 555566 \\ \hline 7 & 2183 & 5777777 \\ \hline 8 & 4609 & 1888888888 \\ \hline \end{tabular} \end{center} \bigskip Note that it is possible that $n_2>n_1$ and $L(n_2)