\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \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{amsmath} \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://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf A Family of Sequences \\ \vskip .1in Generating Smith Numbers } \vskip 1cm \large Amin Witno\\ Department of Basic Sciences\\ Philadelphia University\\ 19392 Jordan\\ \href{mailto:awitno@gmail.com}{\tt awitno@gmail.com} \end{center} \vskip .2 in \begin{abstract} Infinitely many Smith numbers can be constructed using sequences which involve repunits. We provide an alternate method of construction by introducing a generalization of repunits, resulting in new Smith numbers whose decimal digits are composed of zeros and nines. \end{abstract} \section{Introduction} We work with natural numbers in their decimal representation. Let $S(N)$ denote the ``digital sum'' (the sum of the base-$10$ digits) of the number $N$ and let $S_p(N)$ denote the sum of all the digital sums of the prime factors of $N$, counting multiplicity. For instance, $S(2013)=2+0+1+3=6$ and, since $2013=3\times 11\times 61$, we have $S_p(2013)=3+1+1+6+1=12$. The quantity $S_p(N)$ does not seem to have a name in the literature, so let us just call $S_p(N)$ the \emph{p-digit sum of} $N$. The natural number $N$ is called a Smith number when $N$ is composite and $S(N)=S_p(N)$. For example, since $22=2\times 11$, we have both $S(22)=4$ and $S_p(22)=4$. Hence, 22 is a Smith number---thus named by Wilansky \cite{wil} in 1982. Several different ways of constructing Smith numbers are already known. (See our 2010 article \cite{wit}, for instance, which contains a brief historical account on the subject as well as a list of references. The first method of construction that actually produces infinitely many Smith numbers was given in 1987 by McDaniel \cite{mcd}, and later another by Costello and Lewis \cite{c-l}. The key idea that makes these methods successful is based on a pair of simple identities which first appeared in an article by Oltikar and Wayland \cite{o-w}, applying for all natural numbers $N$: \begin{enumerate} \item $S(10N)=S(N)$, \item $S_p(10N)=S_p(N)+7$. \end{enumerate} With these two identities in mind, suppose that we have found a number $N$ such that $S(N)-S_p(N)$ is a nonnegative multiple of 7, say $S(N)-S_p(N)=7c$. Then, we will have $S(N\times 10^c)=S(N)$ and $S_p(N\times 10^c)=S_p(N)+7c$. In other words, $S(N\times 10^c)=S_p(N\times 10^c)$ and hence, $N\times 10^c$ is a Smith number. Therefore, if we can find a sequence which contains infinitely many numbers $N$ such that $S(N)-S_p(N)$ is a nonnegative multiple of 7, then we will have infinitely many Smith numbers of the form $N\times 10^c$, for a suitable value of $c$ that varies with $N$. Since the quantity $S(N)-S_p(N)$ will occur quite frequently in our discussion, let us give this expression a convenient notation. \begin{definition} With the domain of all numbers $N\geq 2$, we define the function $\Delta(N)$ by $$ \Delta(N)=S(N)-S_p(N). $$ \end{definition} Using this definition, we want to find infinitely many $N$ where $\Delta(N)$ is nonnegative and a multiple of 7. It seems proper for us to reintroduce McDaniel's construction of such numbers $N$ first, before we proceed with our own version. McDaniel's sequence is given in the form $9R_n t_n$, where $R_n=(10^n-1)/9$---also known as the $n$-th repunit---and where $t_n$ is to be selected from the set $M=\{2,3,4,5,7,8,15\}$. These seven elements of $M$ have been cleverly chosen so that they have distinct p-digit sums modulo 7. A previously known fact concerning repunits \cite[Theorem 2]{mcd} is that $S(9R_n t)=9n$ for all $n\geq 1$ and for any natural number $t<10^n$. In particular, $S(9R_n t)=9n$ for any $t\in M$ with $n\geq 2$ and, by inspection, with $n=1$ as well. Based on this fact, the number $t_n$ in the sequence $9R_n t_n$ is defined to be the unique element of $M$ for which $S_p(t_n)\equiv 9n-S_p(9R_n)$ (mod 7), for then \begin{align*} \Delta(9R_n t_n)& =S(9R_n t_n)-S_p(9R_n t_n)\\ & =9n-S_p(9R_n)-S_p(t_n)\\ & \equiv 0\pmod 7. \end{align*} And in order to see that $\Delta(9R_n t_n)\geq 0$ for every $n\geq 1$, we state the next theorem, also by McDaniel \cite[Theorem 1]{mcd}, right after the following definition. \begin{definition} For any number $N\geq 2$, the function $\Omega(N)$ equals the number of prime factors of $N$, counting multiplicity. \end{definition} \begin{theorem}\label{thm:mcd} Let $D(N)$ denote the number of digits in $N$. Then $S_p(N)<9D(N)-0.54\Omega(N)$. \end{theorem} Applying the theorem, plus the fact that $S_p(t)\leq 8$ for all $t\in M$ and the fact that $\Omega(9R_n)\geq 3$, we get $$ S_p(9R_n t_n)=S_p(9R_n)+S_p(t_n)<9n-0.54\times 3+8\leq 9n+6. $$ This last inequality implies that $\Delta(9R_n t_n)\geq -6$ and therefore, since $\Delta(9R_n t_n)$ is constructed to be a multiple of 7, we have $\Delta(9R_n t_n)\geq 0$ as desired. Finally then, for each $n\geq 1$, the Smith number that can be created is $9R_n t_n\times 10^c$, with the value of $c$ for which $7c=\Delta(9R_n t_n)$. In a similar way, Costello and Lewis constructed Smith numbers using another sequence in the form $9R_n 11^{x_n}$ for some computed value of $x_n$ between 0 and 6 that will make $\Delta(9R_n 11^{x_n})$ a nonnegative multiple of 7. Although techniquely new, the sequence $9R_n 11^{x_n}$ is essentially the same as that of McDaniel, with only the set $M$ now replaced by $\{11^x\mid 0\leq x\leq 6\}$, but which plays the same role as does $M$, i.e., to contain 7 elements with distinct p-digit sums modulo 7. In this article, we shall demonstrate how to construct Smith numbers using new sequences which still resemble that of McDaniel. However, this time we will modify the repunits $R_n$ by allowing zero digits in them in a certain way, and then adjust the set $M$ of the seven multipliers accordingly. \section {New Constructions} \begin{definition} For every pair $(k,n)$ of natural numbers, we define the number $P_{k,n}$ by $$ P_{k,n}=\sum_{i=0}^{n-1}\;10^{ki}. $$ \end{definition} For example, $P_{3,5}=1,001,001,001,001$. Note that, in general, we have $S(P_{k,n})=n$ for any pair $(k,n)$ and that, in particular, $P_{1,n}=R_n$. For a fixed $k\geq 2$, we shall build a sequence in the form $9P_{k,n}t_{k,n}$, where $t_{k,n}$ is to be determined in such a way that $\Delta(9P_{k,n}t_{k,n})$ will be a nonnegative multiple of 7 for infinitely many values of $n$. We will achieve this goal through a series of results, involving the numbers $P_{k,n}$, in what follows. \begin{theorem}\label{thm:P_kn} Let $k$ and $n$ be two given natural numbers. If $n$ is a multiple of $d$, then we have the identity $P_{k,d}\times P_{kd,n/d}=P_{k,n}$. Thus, if $d$ divides $n$, then $P_{k,d}$ divides $P_{k,n}$. \end{theorem} \begin{proof} We set $x=10^k$ in the following series of identities. \begin{align*} P_{k,d}\times P_{kd,n/d}& =\Bigg(\sum_{i=0}^{d-1}\;x^i\Bigg)\;\Bigg(\sum_{j=0}^{n/d-1}\;x^{dj}\Bigg)\\ & =(1+x+x^2+\cdots+x^{d-1})\;(1+x^d+x^{2d}+\cdots+x^{n-d})\\ & =\sum_{h=0}^{n-1}\;x^h=P_{k,n}. \end{align*} \vskip -.5cm \end{proof} \begin{theorem}\label{thm:P_kn2} For any values of $k\geq 1$ and $n\geq 2$, we have $\Omega(P_{k,n})\geq\Omega(n)$. \end{theorem} \begin{proof} Let $p_1,p_2,\ldots,p_r$ be prime numbers, not assumed distinct, such that $n=\prod_{i=1}^{r}\,p_i$. Let us set $n_j=\prod_{i=j}^{r}\,p_i$, where $1\leq j\leq r$. In particular, $n_1=n$. By Theorem \ref{thm:P_kn}, we state that $P_{k,n_j}$ is a factor of $P_{k,n_{j-1}}$ for all $j$ in the range $2\leq j\leq r$. It follows that $P_{k,n_1}$ must have at least $r$ prime factors, i.e., $\Omega(P_{k,n})\geq r=\Omega(n)$. \end{proof} \begin{theorem}\label{thm:P_kn3} Fix a natural number $k\geq 2$. Suppose that $t$ is the sum of $k$ powers of 10, written $t=\sum_{j=1}^{k}\,10^{e_j}$, such that the set $\{e_j\mid 1\leq j\leq k\}$ serves as a complete residue system modulo $k$. Then $S(9P_{k,n}t)=9kn$ for every $n\geq 1$. \end{theorem} \begin{proof} Observe that for $n\geq 1$, \begin{align*} P_{k,n}\times t& =\left(\sum_{i=0}^{n-1}\;10^{ki}\right)\;\left(\sum_{j=1}^{k}\;10^{e_j}\right)\\ & =\sum_{j=1}^{k}\;\sum_{i=0}^{n-1}\;10^{ki+e_j}. \end{align*} So we see that $P_{k,n}t$ is the sum of $kn$ powers of 10, necessarily all of which are distinct since the exponents $e_j$ are distinct modulo $k$. This means that the digits in the number $P_{k,n}t$ are composed of only zeros and ones---with exactly $kn$ ones. We then have $S(9P_{k,n}t)=9kn$ as claimed. \end{proof} \begin{remark}\label{rem:R_k} Incidentally, Theorem \ref{thm:P_kn3} remains valid with $k=1$, giving the result $S(9R_n t)=9n$, where $t$ is just any power of 10. Secondly, in general, the number $t$ given in the theorem is always divisible by $R_k$. To see why, we use the fact that $10^k\equiv 1$ (mod $R_k$) to obtain $$ t\equiv\sum_{j=1}^{k}\,10^{e_j\bmod k}=R_k\equiv 0\pmod{R_k}. $$ \end{remark} \begin{theorem}\label{thm:main} For a fixed $k\geq 2$, suppose that $M_k$ is a set of 7 natural numbers $t$ with the following two conditions. \begin{enumerate} \item Every element $t\in M_k$ can be expressed as $t=\sum_{j=1}^{k}10^{e_j}$, where $\{e_j\mid 1\leq j\leq k\}$ is a complete residue system modulo $k$. \item The set $\{S_p(t)\mid t\in M_k\}$ is a complete residue system modulo 7. \end{enumerate} Then, for each $n\geq 1$, there exists a unique $t_{k,n}\in M_k$ such that $\Delta(9P_{k,n}t_{k,n})$ is a multiple of 7. Furthermore, there exist infinitely many values of $n\geq 1$ for which $\Delta(9P_{k,n}t)\geq 0$ for all $t\in M_k$. \end{theorem} \begin{proof} Let $t\in M_k$. We have $S(9P_{k,n}t)=9kn$ according to Theorem \ref{thm:P_kn3}, so $$ \Delta(9P_{k,n}t)=9kn-S_p(9P_{k,n})-S_p(t). $$ Hence, for a fixed $n\geq 1$, there is exactly one element $t_{k,n}\in M_k$ for which $\Delta(9P_{k,n}t_{k,n})$ is a multiple of 7, i.e., the element $t_{k,n}$ with $S_p(t_{k,n})\equiv 9kn-S_p(9P_{k,n})$ (mod 7). Next, it is not hard to see that $D(9P_{k,n})=D(P_{k,n})=k(n-1)+1$, recalling that the function $D(N)$ counts the number of digits in $N$. We then use Theorem \ref{thm:mcd} to obtain \begin{align*} S_p(9P_{k,n}t)& =S_p(9P_{k,n})+S_p(t)\\ & <9(kn-k+1)-0.54\Omega(P_{k,n})+S_p(t)\\ & =S(9P_{k,n}t)-9k+9-0.54\Omega(P_{k,n})+S_p(t). \end{align*} With the assumption that $k\geq 2$, we have that $$ \Delta(9P_{k,n}t)>9+0.54\Omega(P_{k,n})-S_p(t). $$ Therefore, we will have $\Delta(9P_{k,n}t)\geq 0$ for all $t\in M_k$ given that, say, $\Omega(P_{k,n})\geq 2S_p(t')$, for some $t'\in M_k$ with $S_p(t')\geq S_p(t)$ for all $t\in M_k$. The claim is now clear since Theorem \ref{thm:P_kn2} implies that $\Omega(P_{k,n})$ can be made arbitrarily large for infinitely many values of $n$, in particular when $n$ has sufficiently many prime divisors. \end{proof} Thus according to Theorem \ref{thm:main}, we have infinitely many $n$ where $\Delta(9P_{k,n}t_{k,n})=7c$ with $c\geq 0$, each of which is associated with the Smith number $9P_{k,n}t_{k,n}\times 10^c$---provided that a set $M_k$ such as described in the theorem has been found. For $k=2$, to begin with, we propose the following set as a valid $M_2$ example. $$ M_2=\{11, 1001, 100001, 10^{15}+1, 10^{21}+1, 10^{23}+1, 10^{35}+1\}. $$ To help see that the hypothesis of Theorem \ref{thm:main} is satisfied, we provide in Table \ref{tab:M2} the prime factorization for each $t\in M_2$, in order to evaluate $S_p(t)$. \begin{table}[!h] \begin{center} \caption{The elements $t\in M_2$ and their p-digit sums.}\label{tab:M2} \begin{tabular}{llcc} \hline $t$& Factorization of $t$ into primes& $S_p(t)$& $S_p(t)\bmod 7$\\ \hline 11& 11& 2& 2\\ 1001& $7\times 11\times 13$& 13& 6\\ 100001& $11\times 9091$& 21& 0\\ $10^{15}+1$& $7\times 11\times 13\times 211\times 241\times$& 53& 4\\ & $2161\times 9091$\\ $10^{21}+1$& $7\times 7\times 11\times 13\times 127\times 2689\times$& 117& 5\\ & $459691\times 909091$\\ $10^{23}+1$& $11\times 47\times 139\times 2531\times$& 122& 3\\ & 549797184491917\\ $10^{35}+1$& $11\times 9091\times 909091\times 4147571\times$& 155&1\\ & 265212793249617641\\ \hline \end{tabular} \end{center} \end{table} Moreover, to illustrate the construction of the Smith numbers, let us consider $P_{2,7}$, which factors into three primes: $$ P_{2,7}=1010101010101=239\times 4649\times 909091. $$ Here we have $S(9P_{2,7}t_{2,7})=9\times 2\times 7=126$, $S_p(P_{2,7})=65$, and $$ \Delta(9P_{2,7}t_{2,7})=126-(6+65+S_p(t_{2,7}))=55-S_p(t_{2,7}). $$ We are led to $t_{2,7}=1001$, where $S_p(1001)=13\equiv 55$ (mod 7). In the end we have $\Delta(9P_{2,7}\times 1001)=55-13=7\times 6$, generating the Smith number $$ 9\times 1010101010101\times 1001\times 10^6=9,099,999,999,999,909,000,000. $$ Further computational results show that $M_k$ can be produced for at least seven more values of $k$: \begin{align*} M_3= & \{111, 10101, 100011, 110001, 10100001, 100000011, 110000000001\},\\ M_4= & \{1111, 101101, 1001011, 1101001, 10000111, 11100001, 10000000001101\},\\ M_5= & \{11111, 1011101, 10011011, 11011001, 100010111, 111010001, 100000011101\},\\ M_6= & \{111111, 10111101, 100111011, 110111001, 1000110111, 1110110001, 100100011011\},\\ M_7= & \{1111111, 101111101, 1001111011, 1101111001, 10001110111, 11101110001,\\ & \quad 1001001011011\},\\ M_8= & \{11111111, 1011111101, 10011111011, 11011111001, 100011110111, 111011110001,\\ & \quad 10010011011011\},\\ M_9= & \{111111111, 10111111101, 100111111011, 110111111001, 1000111110111,\\ & \quad 1110111110001, 100100111011011\}. \end{align*} We leave it to the reader to verify that each set $M_k$ given above, where $3\leq k\leq 9$, indeed meets the hypothesis of Theorem \ref{thm:main} and therefore can be used to generate Smith numbers in conjunction with the sequence $P_{k,n}$. An apparent future research problem, as we conclude, is to investigate whether or not a suitable $M_k$ exists for every $k>9$, or perhaps for infinitely many values of $k$, without resorting to brute force computation. \section{Acknowledgments} The author is truly grateful to the anonymous referee for proofreading this article, starting from its earliest version, and for giving an extensive list of corrections and suggestions, each one of which is sincerely appreciated. \begin{thebibliography}{9} \bibitem{c-l} P. Costello and K. Lewis, Lots of Smiths, {\it Math. Mag.} \textbf{75} (2002), 223--226. \bibitem{mcd} W. L. McDaniel, The existence of infinitely many $k$-Smith numbers, {\it Fibonacci Quart.} \textbf{25} (1987), 76--80. \bibitem{o-w} S. Oltikar and K. Wayland, Construction of Smith numbers, {\it Math. Mag.} \textbf{56} (1983), 36--37. \bibitem{wil} A. Wilansky, Smith numbers, {\it Two-Year College Math. J.} \textbf{13} (1982), 21. \bibitem{wit} A. Witno, Another simple construction of Smith numbers, {\it Missouri J. Math. Sci.} \textbf{22} (2010), 97--101. Available at \url{http://projecteuclid.org/euclid.mjms/1312233139}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11A63. \noindent \emph{Keywords: } Smith number, repunit. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A006753} and \seqnum{A002275}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received September 29 2012; revised versions received December 21 2012; March 21 2013. Published in {\it Journal of Integer Sequences}, March 25 2013. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .