\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage{enumerate} \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://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf On Arithmetic Progressions of Integers \\ \vskip .1in with a Distinct Sum of Digits} \vskip 1cm \large Carlo Sanna \\ Italy\\ \href{mailto:carlo.sanna.dev@gmail.com}{\tt carlo.sanna.dev@gmail.com} \\ \end{center} \vskip .2in \begin{abstract} Let $b \geq 2$ be a fixed integer. Let $s_b(n)$ denote the sum of digits of the nonnegative integer $n$ in the base-$b$ representation. Further let $q$ be a positive integer. In this paper we study the length $k$ of arithmetic progressions $n, {n + q}, \ldots, {n + q(k-1)}$ such that $s_b(n), {s_b(n + q)}, \ldots, s_b(n + q(k-1))$ are (pairwise) distinct. More specifically, let $L_{b,q}$ denote the supremum of $k$ as $n$ varies in the set of nonnegative integers $\mathbb{N}$. We show that $L_{b,q}$ is bounded from above and hence finite. Then it makes sense to define $\mu_{b,q}$ as the smallest $n \in \mathbb{N}$ such that one can take $k = L_{b,q}$. We provide upper and lower bounds for $\mu_{b,q}$. Furthermore, we derive explicit formulas for $L_{b,1}$ and $\mu_{b,1}$. Lastly, we give a constructive proof that $L_{b,q}$ is unbounded with respect to $q$. \end{abstract} \section{Introduction} Let $b \geq 2$ be a fixed integer and let $s_b(n)$ denote the sum of digits of the nonnegative integer $n$ in the base-$b$ representation. Further let $q$ a positive integer, we are interested in the length $k$ of arithmetic progressions $n, {n + q}, \ldots, {n + q(k-1)}$ such that the integers $s_b(n), {s_b(n + q)}, \ldots, {s_b(n + q(k-1))}$ are (pairwise) distinct. There are known results on the asymptotic behavior of the sum of digits function \cite{ref_Bush,ref_Fang}, and about its distribution along arithmetic progressions \cite{ref_Drmota,ref_Gelfond}. But, to our knowledge, this particular problem has not been studied before. More specifically, let $L_{b,q}$ denote the supremum of $k$ as $n$ varies in the set of nonnegative integers $\mathbb{N}$. We show that $L_{b,q}$ is bounded from above and hence finite. As a consequence, it makes sense to define $\mu_{b,q}$ as the smallest $n \in \mathbb{N}$ such that one can take $k = L_{b,q}$. Then, we provide upper and lower bounds for $\mu_{b,q}$. Everything allows for an effective computation of $L_{b,q}$ and $\mu_{b,q}$ by checking a finite number of candidates, though this is feasible in a short amount of time only for small values of $b$ and $q$. Furthermore, we derive explicit formulas for $L_{b,1}$ and $\mu_{b,1}$. Lastly, we give a constructive proof that $L_{b,q}$ is unbounded with respect to $q$, in the sense that $\sup_{q \in \mathbb N^+} L_{b,q} = +\infty$. \section{Bounds for $L_{b,q}$ and $\mu_{b,q}$} \begin{theorem}\label{first_upper_bound} Let $m$ be the least positive integer such that \begin{equation} m(b-1) + 1 \leq \left\lfloor\frac{b^m}{q}\right\rfloor . \end{equation} Then $L_{b,q} \leq 2\!\left\lfloor b^m / q \right\rfloor$. \end{theorem} \begin{proof} Let $n \in \mathbb{N}$, $k \in \mathbb{N}^+$ and $A := \{n + qi : i=0,1,\ldots,k-1\}$ such that $s_b(n)$, $s_b(n+q)$, $\ldots$, $s_b(n+q(k-1))$ are distinct. For any $t \in \mathbb{N}$ we define $A_t := A \cap [tb^m, (t+1)b^m-1]$. For convenience, take $M := \left\lfloor b^m / q\right\rfloor$. Then for all nonnegative integers $t < u$ the following statements are true: \begin{enumerate}[(i).] \item $|A_t| \leq M$. \item $A_t, A_u \neq \varnothing \;\Rightarrow\; \forall v \in \mathbb{N}, t < v < u \quad |A_v| = M$. \item $|A_t| = M, \; t \not\equiv -1 \pmod b \;\Rightarrow\; \forall u \in \mathbb{N}, u > t \quad A_u = \varnothing$. \item $|A_t| = M, \; t \not\equiv 0 \pmod b \;\Rightarrow\; \forall u \in \mathbb{N}, u < t \quad A_u = \varnothing$. \end{enumerate} (i). For all $a \in A_t$ we have $s_b(a) = s_b(t) + s_b(a \bmod b^m)$ and therefore \begin{equation} s_b(A_t) := \{ s_b(a) : a \in A_t \} \subseteq \{s_b(t),s_b(t)+1,\ldots,s_b(t)+m(b-1)\} , \end{equation} so by the hypotheses $|A_t| = |s_b(A_t)| \leq m(b-1) + 1 \leq M$. (ii). Since $A_t$, $A_u$ are nonempty we have $n < vb^m$ and $(v+1)b^m - 1 < n + q(k-1)$. Then \begin{align} |A_v| &= \big|\{qi : i = 0, \ldots, k - 1\} \cap \left[vb^m - n, (v+1)b^m - n - 1\right]\big| \nonumber \\ &= \big|q\mathbb{N} \cap \left[vb^m - n, (v+1)b^m - n - 1\right[\big| \geq \left\lfloor\frac{b^m}{q}\right\rfloor = M , \end{align} because $\big|q\mathbb{N} \cap [x,y]\big|\geq \lfloor (y - x + 1) / q \rfloor$ for any integers $y \geq x \geq 0$. From point (i) it follows that $|A_v| = M$. (iii). We have $s_b(t + 1) = s_b(t) + 1$. Suppose by contradiction that $A_{t+1}$ is nonempty, so there exists $a := \min(A_{t+1})$. Now $s_b(a) = s_b(t) + 1 + s_b(a \bmod b^m)$ and, since $|A_t| = M$ implies $s_b(A_t) = \{s_b(t),s_b(t)+1,\ldots,s_b(t)+m(b-1)\}$, then necessarily $s_b(a \bmod b^m) = m(b-1)$, so that $a = (t+2)b^m-1$. In fact, $s_b(a \bmod b^m) \leq m(b-1)$ and if we suppose $s_b(a \bmod b^m) < m(b-1)$ then $s_b(a) \in s_b(A_t)$, in contradiction to our standing hypotheses. But $q \leq \frac1{M}b^m \leq b^{m-1}$, so $a - q \geq (t + 1)b^m$ and $a - q \in A_{t+1}$, a contradiction. In conclusion $A_{t+1} = \varnothing$ and, since $q < b^m$, this implies $A_u = \varnothing$. (iv). Note that $t \geq 1$, we have $s_b(t - 1) = s_b(t) - 1$. Suppose that $A_{t-1}$ is nonempty, so there exists $a := \max(A_{t-1})$. Then $s_b(a) = s_b(t) - 1 + s_b(a \bmod b^m)$ and, since $|A_t| = M$ implies $s_b(A_t) = \{s_b(t),s_b(t)+1,\ldots,s_b(t)+m(b-1)\}$, then it must be $s_b(a \bmod b^m) = 0$ that is $a = (t-1)b^m$. But $a + q \leq tb^m - 1$ so $a + q \in A_{t-1}$, a contradiction. Thus $A_{t-1} = \varnothing$ and, since $q < b^m$, it follows that $A_u = \varnothing$. The sets $\{A_t\}_{t=0}^\infty$ form a partition of $A$, hence $A = \bigcup_{t \in \mathbb{N}} A_t$. On the other hand, for the statements proved, we have that at most two of the sets $\{A_t\}_{t=0}^\infty$ are nonempty and their cardinality is less than or equal to $M$. In conclusion ${k = |A| \leq 2M}$. \end{proof} \begin{corollary}\label{case_q_equal_1} $L_{b,1} = 2b$, $\mu_{2,1} = 14$ and $\mu_{b,1} = b^3 - b$ if $b \geq 3$. \end{corollary} \begin{proof} From Theorem \ref{first_upper_bound} we know that $L_{b,1} \leq 2b$. It is easy to verify that $L_{2,1} = 4$ and $\mu_{2,1} = 14$ (OEIS \seqnum{A000120}). If $b \geq 3$ then $L_{b,1} = 2b$ and $\mu_{b,1} \leq b^3 - b$ because \begin{equation} s_b(b^3 - b + i) = \begin{cases} 2(b-1) + i, & \text{ if }\quad i=0,1,\ldots,b-1; \\ i - b + 1, & \text{ if }\quad i = b,b+1,\ldots,2b-1. \end{cases} \end{equation} Now let $n < b^3 - b$ be a nonnegative integer. Write $n = d_2 b^2 + d_1 b + d_0$ with $d_0,d_1,d_2 \in \{0,1,\ldots,b-1\}$. If $d_1 \neq b - 1$ then let $m$ be the least integer greater than or equal to $n$ and not divisible by $b$. We have $m \leq n + 1$ and $s_b(m) = s_b(m+b-1)$. If $d_1 = b - 1$ and $d_0 = 0$ then $d_2 \leq b-2$, since $n < b^3- b$, and so $s_b(n) = s_b (n + 2b - 2)$. If $d_1 = b - 1$ and $d_0 \neq 0$ then let $h := (d_2 + 1)b^2$. We have $h \leq n + b - 1$ and $s_b(h + 1) = s_b(h + b)$. In any case we have found two integers $u$, $v$ such that $n \leq u < v \leq n + 2b - 1$ and $s_b(u) = s_b(v)$. Therefore $\mu_{b,1} \geq b^3 - b$ and actually $\mu_{b,1} = b^3 - b$. \end{proof} \begin{theorem} $L_{b,bq} = L_{b,q}$ and $\mu_{b,bq} = b\;\;\!\!\! \mu_{b,q}$. \end{theorem} \begin{proof} For all $n,i \in \mathbb{N}$ and $d \in \{0,1,\ldots,b-1\}$ we have $s_b(bn + d + bqi) = s_b(n + qi) + d$. Then for any $k \in \mathbb{N}$ we have that ${s_b(bn + d)}, {s_b(bn + d + bq)}, \ldots, {s_b(bn + d + (k-1)bq)}$ are distinct if and only if ${s_b(bn)}, {s_b(bn + bq)}, \ldots, {s_b(bn + (k-1)bq)}$ are distinct, which in turn holds if and only if ${s_b(n)}, {s_b(n + q)}, \ldots, {s_b(n + (k-1)q)}$ are distinct. In conclusion ${L_{b,bq} = L_{b,q}}$ and $\mu_{b,bq} = b\;\;\!\!\! \mu_{b,q}$. \end{proof} \begin{theorem}\label{minimum_lower_bound} $\mu_{b,q} > b^{\frac{L_{b,q} - b}{b - 1}} - q(L_{b,q} - 1)$. \end{theorem} \begin{proof} Let $r := \left\lfloor\log_b(\mu_{b,q} + q(L_{b,q} - 1))\right\rfloor + 1$. Since $s_b(\mu_{b,q}), s_b(\mu_{b,q} + q), \ldots s_b(\mu_{b,q} + q(k-1))$ are distinct and less than or equal to $r(b-1)$, then \begin{equation}\label{ineq1} L_{b,q} \leq r(b-1) + 1 < (b-1)\log_b(\mu_{b,q} + q(L_{b,q} - 1)) + b . \end{equation} Solving (\ref{ineq1}) for $\mu_{b,q}$ we get $\mu_{b,q} > b^{\frac{L_{b,q} - b}{b - 1}} - q(L_{b,q} - 1)$. \end{proof} \begin{theorem}\label{minimum_upper_bound} $\mu_{b,q} \leq b^3[q(L_{b,q} - 1)]^2 - 1$. \end{theorem} \begin{proof} Take $r := \left\lfloor \log_b(q(L_{b,q} - 1))\right\rfloor + 1$, $\mu := (\mu_{b,q} \bmod b^r)$, $m := \left\lfloor \mu_{b,q} / b^r\right\rfloor$, so that $\mu_{b,q} = mb^r + \mu$, and let $i \in \{0,1,\ldots,L_{b,q}-1\}$. If $\mu + qi < b^r$ then \begin{equation} s_b(\mu_{b,q} + qi) = s_b(m) + s_b(\mu + qi) , \end{equation} else if $\mu + qi \geq b^r$ then \begin{equation} s_b(\mu_{b,q} + qi) = s_b(m + 1) + s_b(\mu + qi - b^r) , \end{equation} for the fact that $\mu + qi \leq 2b^r - 2$. Define $n := (b^{r+1} - 1)b^r + \mu$, if $\mu + qi < b^r$ then \begin{equation} s_b(n + qi) = s_b(b^{r+1} - 1) + s_b(\mu + qi) = (r + 1)(b - 1) + s_b(\mu + qi) > r(b-1) . \end{equation} On the other hand, if $\mu + qi \geq b^r$ then \begin{equation} s_b(n + qi) = s_b(b^{r+1}) + s_b(\mu + qi - b^r) = 1 + s_b(\mu + qi - b^r) \leq r(b - 1) , \end{equation} because $\mu + qi - b^r \leq b^r - 2$ and so $s_b(\mu + qi - b^r) \leq r(b - 1) - 1$. In conclusion $s_b(n), {s_b(n+q)}, \ldots, s_b(n + q(L_{b,q} -1))$ are distinct and \begin{equation} \mu_{b,q} \leq n \leq b^{2r+1} - 1 \leq b^3 [q(L_{b,q}-1)]^2 - 1 , \end{equation} this completes our proof. \end{proof} \section{Arbitrarily large values of $L_{b,q}$} For the next theorem we need a lemma about the sum of digits of multiples of $b^r - 1$, $r \in \mathbb{N}^+$. Similar results has been considered by Stolarsky \cite[Lemma 2.2]{ref_Stolarsky} in the case $b=2$, and by Balog and Dartyge \cite[Lemma 1]{ref_Balog} for a generic base $b$. \begin{lemma}\label{const_digit_sum} If $r \in \mathbb{N}^+$ then $s_b((b^r - 1)i) = r(b-1)$ for all $i=1,2,\ldots,b^r - 1$. \end{lemma} \begin{proof} Let $t$ be the greatest nonnegative integer such that $b^t \mid i$. If $i_0 := b^{-t}\,i$ then there exist $d_0,d_1,\ldots,d_{r-1} \in \{0,1,\ldots,b-1\}$ with $d_0 \neq 0$ such that $i_0 = \sum_{j=0}^{r-1} d_j b^j$ is the base-$b$ representation of $i_0$. We have \begin{align} (b^r-1)i_0 &= \sum_{j=r}^{2r-1} d_{j-r} b^j - \sum_{j=0}^{r-1} d_j b^j \nonumber \\ &= \sum_{j=r+1}^{2r-1} d_{j-r} b^j + (d_0 - 1) b^r + b^r - \sum_{j=0}^{r-1} d_j b^j \nonumber \\ &= \sum_{j=r+1}^{2r-1} d_{j-r} b^j + (d_0 - 1) b^r + \sum_{j=1}^{r-1} (b - 1 - d_j) b^j + (b - d_0) . \end{align} Then it is straightforward that \begin{equation} s_b((b^r-1)i_0) = \sum_{j=r+1}^{2r-1} d_{j-r} + (d_0 - 1) + \sum_{j=1}^{r-1} (b - 1 - d_j) + (b - d_0) = r(b-1) . \end{equation} The claim follows from $s_b((b^r-1)i) = s_b((b^r-1)i_0)$. \end{proof} \begin{theorem} $\sup_{q \in \mathbb{N}^+} L_{b,q} = +\infty$. \end{theorem} \begin{proof} Let $n \in \mathbb{N}$ and $q,k \in \mathbb{N}^+$ such that $s_b(n),s_b(n+q), \ldots, s_b(n+q(k-1))$ are distinct. If $t, r$ are the least positive integers such that $n + qk < b^t$ and $(b-1)b^{r-1} \geq k$ then we define \begin{align} n^\prime &= \big((b^t - 1)b^{2r}+ b^{2r-1} + (b^r - 1)((b-1)b^{r-1} - k + 1)\big)b^t + n \nonumber \\ q^\prime &= (b^r - 1)b^t + q . \end{align} For any $i=0,1,\ldots,k$ we have \begin{equation} n^\prime + q^\prime i = \big((b^t - 1)b^{2r}+ b^{2r-1} + (b^r - 1)((b-1)b^{r-1} + i - k + 1)\big)b^t + n + qi , \end{equation} and then \begin{equation} s_b(n^\prime + q^\prime i) = s_b\big((b^t - 1)b^{2r} + b^{2r-1} + (b^r - 1)((b-1)b^{r-1} + i - k + 1)\big) + s_b(n + qi) . \end{equation} If $i \leq k - 1$ then $(b^r - 1)((b-1)b^{r-1} + i - k + 1) < (b-1)b^{2r-1}$ and \begin{equation} s_b(n^\prime + q^\prime i) = t(b-1) + 1 + s_b\big((b^r - 1)((b-1)b^{r-1} + i - k + 1)\big) + s_b(n + qi) , \end{equation} so Lemma \ref{const_digit_sum} implies that \begin{equation} s_b(n^\prime + q^\prime i) = (t + r)(b-1) + 1 + s_b(n + qi) > (t + r)(b-1) . \end{equation} On the other hand, if $i = k$ then \begin{align} s_b(n^\prime + q^\prime k) &= s_b\big(b^{2r+t} + b^{r-1} - 1\big) + s_b(n + qk) = 1 + (r-1)(b-1) + s_b(n + qk) \nonumber \\ &\leq 1 + (t + r - 1)(b-1) \leq (t + r)(b-1) . \end{align} Therefore $s_b(n^\prime), s_b(n^\prime + q), \ldots, s_b(n^\prime + qk)$ are distinct, it follows that $L_{b,q^\prime} > L_{b,q}$ and hence $\sup_{q \in \mathbb{N}^+} L_{b,q} = +\infty$. \end{proof} \section{Further developments} Thanks to Theorem \ref{first_upper_bound} we know that $L_{b,q}$ is not too large when $q$ is small compared to $b$, e.g., if $q \leq \frac1{2}b$ then $L_{b,q} \leq 2b^2$. Actually, it is likely that for small $q$ there exist explicit formulas for $L_{b,q}$ and $\mu_{b,q}$ analogous to those of Corollary \ref{case_q_equal_1}. However, when $q$ is much larger than $b$ the question becomes more difficult. Theorem \ref{first_upper_bound} and \ref{minimum_upper_bound} allowed us, with the aid of a personal computer, to calculate some values of $\mu_{b,q}$ and $L_{b,q}$. \begin{center} \renewcommand{\arraystretch}{1.2} \begin{tabular}{|c|*{9}{c|}} \hline $\mu_{b,q} , L_{b,q}$ & $q=1$ & $q=2$ & $q=3$ & $q=4$ & $q=5$ & $q=6$ & $q=7$ & $q=8$ & $q=9$ \\ \hline $b = 2$ & $14, 4$ & $28, 4$ & $58, 4$ & $56, 4$ & $242, 6$ & $116, 4$ & $109, 5$ & $112, 4$ & $994, 6$ \\ \hline $b = 3$ & $24, 6$ & $24, 3$ & $72, 6$ & $234, 5$ & $705, 9$ & $72, 3$ & $697, 10$ & $18, 3$ & $216, 6$ \\ \hline $b = 4$ & $60, 8$ & $56, 8$ & $60, 3$ & $240, 8$ & $1004, 8$ & $244, 4$ & $977, 13$ & $224, 8$ & $239, 4$ \\ \hline \end{tabular} \end{center} \begin{center} Table 1: Values of $\mu_{b,q}$ and $L_{b,q}$ for $b=2,3,4$ and $q=1,2,\ldots,9$. \end{center} Through these series of numerical experiments we have reason to believe that the upper bound given by Theorem \ref{first_upper_bound} is in some sense ``astronomical'' and surely can be improved. Similarly, also the upper and lower bounds for $\mu_{b,q}$ can be improved. Many other questions remain unsolved. For instance, let $\kappa_{b,q}$ be the function sending the nonnegative integer $n$ to the maximum $k \in \mathbb{N}$ such that $s_b(n), {s_b(n + q)}, \ldots, {s_b(n + q(k - 1))}$ are distinct. We proved that the function $\kappa_{b,q}$ is bounded. Is $\kappa_{b,q}$ definitely periodic? Does it present a fractal behavior? What is its Fourier expansion? What is its mean, variance, etc.? On the other side, for which $n \in \mathbb{N}$ is $\kappa_{b,q}(n)$ particularly small? These and other questions will be the subject of future investigations. \section{Acknowledgements} I am grateful to Salvatore Tringali (LJLL, Universit\'e Pierre et Marie Curie) for his careful proofreading and, more generally, his valuable support in the field of Mathematics. I am also thankful to the anonymous referee for his constructive comments. \vspace{10pt} \begin{thebibliography}{10} \bibitem{ref_Balog} A. Balog and C. Dartyge, On the sum of the digits of multiples, {\em Moscow J. Comb. Number Th.} {\bf 2} (2012), 3--15. \bibitem{ref_Bush} L. E. Bush, An asymptotic formula for the average sum of the digits of integers, {\em Amer. Math. Monthly} {\bf 47} (1940), 154--156. \bibitem{ref_Drmota} M. Drmota, C. Mauduit, and J. Rivat, The sum of digits function of polynomial sequences, {\em J. Lond. Math. Soc.} {\bf 84} (2011), 81--102. \bibitem{ref_Fang} Y. Fang, A theorem on the k-adic representation of positive integers, {\em Proc. Amer. Math. Soc.} {\bf 130} (2002), 1619--1622. \bibitem{ref_Gelfond} A. O. Gelfond, Sur les nombres qui ont des propri\'et\'e additives et multiplicative donn\'ees, {\em Acta Arith.} {\bf 13} (1967/1968), 259--265. \bibitem{ref_Stolarsky} K. B. Stolarsky, Integers whose multiples have anomalous digital frequencies, {\em Acta Arith.} {\bf 38} (1980), 117--128. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11A63; Secondary 11A25, 11B25. \noindent \emph{Keywords: } Elementary number theory, radix representation, sum of digits, arithmetic progressions. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A000120}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received August 5 2012; revised version received September 23 2012. Published in {\it Journal of Integer Sequences}, October 2 2012. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .