<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}

\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{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage[all]{xy}
\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 Large and small gaps between consecutive Niven numbers}
\vskip 1cm
\large
Jean-Marie De Koninck\footnote{Research supported in part by a grant from NSERC.}
and Nicolas Doyon  \\
D\'epartement de math\'ematiques et de statistique \\
Universit\'e Laval \\
Qu\'ebec G1K 7P4 \\
Canada \\
\href{mailto:jmdk@mat.ulaval.ca}{jmdk@mat.ulaval.ca}\\
\href{mailto:doyon@dms.umontreal.ca}{doyon@dms.umontreal.ca}
\end{center}

\vskip .4in

\begin{abstract}
A positive integer is said to be a Niven number if it is divisible by the 
sum of its decimal digits. We investigate the occurrence of large and small 
gaps between consecutive Niven numbers.
\end{abstract}
\vskip .2in


\section{Introduction}

A positive integer $n$ is said to be a {\it Niven number} (or a Harshad
number) if it is divisible by the sum of its (decimal) digits. For
instance, 153 is a Niven number since 9 divides 153, while 154 is not.
Niven numbers have been extensively studied; see for instance Cai
\cite{kn:cai}, Cooper and Kennedy \cite{kn:ck}, Grundman \cite{kn:g} or
Vardi \cite{kn:vardi}.

Let $N(x)$ denote the number of Niven numbers $\le x$.
Recently, De Koninck and Doyon proved \cite{kn:dkd}, using elementary methods, 
that given any $\varepsilon&gt;0$, 
$$
x^{1-\varepsilon} \ll N(x) \ll \frac{x\log \log x}{\log x}. 
$$
Later, using complex variables as well as probabilistic number theory,
De Koninck, Doyon and K\'atai \cite{kn:kdk} showed that 
\begin{equation}
N(x) = (c+o(1)) \frac x{\log x}, \label{eq:conj}
\end{equation}
where $c$ is given by 
\begin{equation}
c= \frac{14}{27} \log 10 \approx 1.1939. \label{eq:valeurc}
\end{equation} 

In this paper, we investigate the occurrence of large gaps between
consecutive Niven numbers. Secondly, denoting by $T(x)$ the number of
Niven numbers $n\le x$ such that $n+1$ is also a Niven number, we prove
that $$T(x)\ll \frac{x\log \log x}{(\log x)^2}.$$ We conclude by stating
a conjecture.  \vskip 20pt

\section{Main results}

Given a positive integer $\ell$, let $n_\ell$ be the smallest positive
integer $n$ such that the interval $[n,n+\ell-1]$ does not contain any
Niven numbers.  \vskip 5pt

\noindent
{\bf Theorem 1.} {\sl If $\ell$ is sufficiently large, then 
$$n_\ell &lt;  (100(\ell+2))^{\ell+3}.$$ }
\vskip 5pt

\noindent
{\bf Theorem 2.} {\sl As $x\to \infty$,
$$T(x) \ll \frac{x\log \log x}{(\log x)^2}.$$
}
\vskip 20pt



\section{The search for large gaps between consecutive Niven numbers}

It follows from the fact that the set of Niven numbers is of zero
density that there exist arbitrarily long intervals free of Niven
numbers.

Denote by $n=n(k)$ the smallest Niven number such that $n+k$ is also a
Niven number while each one of $n+1,n+2,\ldots,n+k-1$ is not. The
following table provides the value of $n(k)$ when $k$ is a multiple of
10 up to 120.  \vskip 5pt



\begin{center}
\begin{tabular}{|l|l|}\hline
$k$ &amp; $n(k)$ \\ \hline \hline
10 &amp; 90  \\
20 &amp; 7560  \\
30 &amp; 28680  \\
40 &amp; 119772  \\
50 &amp; 154876  \\
60 &amp; 297864  \\ \hline
\end{tabular}\hspace{2cm}\begin{tabular}{|l|l|}\hline
$k$ &amp; $n(k)$ \\ \hline \hline
70 &amp; 968760  \\
80 &amp; 7989168  \\
90 &amp; 2879865  \\
100 &amp; 87699842  \\
110 &amp; 497975920  \\
120 &amp; 179888904  \\ \hline
\end{tabular}
\end{center}
\vskip 5pt





We shall now show how one can construct arbitrary large intervals free
of Niven numbers, say intervals of length $\ell$, and thereby establish
the proof of Theorem 1.

First, given a positive integer $m$, set 
\begin{equation}
t=t(m)=\left\lfloor \frac{\log(18m)}{\log 10} \right\rfloor+1, \label{eq:t}
\end{equation}
where $\lfloor y \rfloor$ stands for the largest integer $\le y$, 
and let $m$ be the smallest positive integer satisfying
\begin{equation}
\frac{9m-9t-1}{9t+2} &gt; \ell. \label{eq:condi2}
\end{equation}
Then consider integers $n$ which can be written as the concatenation of
the numbers $10^m-1$ and $d$, where $d$ is a $t$ digit number yet to be
determined, that is the $m+t$ digit number
\begin{equation}
n= \langle \underbrace{99\cdots 9}_{m},d \rangle =(10^m-1)\cdot 10^t +d.\label{eq:defn}
\end{equation}


Then let $b\cdot 9m$ be the smallest multiple of $9m$ located in the interval 
$$I=[\underbrace{99\cdots 9}_{m}\underbrace{00\cdots 0}_{t}\ ,\
\underbrace{99\cdots 9}_{m+t}].$$
Note that at least two such multiples of $9m$ belong to $I$ since the
length of $I$ is $10^t$, which itself is larger than $18m$ because of
(\ref{eq:t}).

We now count the number of Niven numbers belonging to the interval
$$J:=[b\cdot 9m, (b+1)\cdot 9m[\subset I.$$
For any positive integer $n$
of the form  (\ref{eq:defn}), it is clear that $n\in I$ and thus that
$s(n)$ can take at most $9t+1$ values ranging from $9m$ to $9m+9t$. It
follows that for any fixed value of $s(n)$, there is at most one
multiple of $s(n)$ in the interval $J$, and therefore that there exist
at most $9t+1$ Niven numbers in $J$.

We have thus created an interval $J$ of length $9m$ containing at most
$9t+1$ Niven numbers, and therefore, by a pigeon-hole argument,
containing a subinterval free of Niven numbers and of length at least
$\displaystyle{ \frac{9m-9t-1}{9t+2} }$, which is larger than $\ell$ by
condition (\ref{eq:condi2}), thus completing our task of constructing
arbitrarily large intervals free of Niven numbers.

For example, if we require gaps of width $\ell=100$, 200 and 300
respectively, free of Niven numbers, here is a table showing the
corresponding values of $m$ and $t$, as well as the length of the
interval $J$ which needs to be investigated to find the proper gap.
\vskip 5pt

\begin{center}
\begin{tabular}{|c|c|c|c|}\hline
$\ell$ &amp; $m$ &amp; $t$ &amp; length of $J$ \\ \hline \hline
100 &amp; 416  &amp; 4  &amp; 3744   \\
200 &amp; 1028 &amp; 5 &amp; 9252 \\
300 &amp; 1539 &amp; 5 &amp; 13851 \\ \hline
\end{tabular}
\end{center}
\vskip 5pt

\noindent
The good news about this algorithm is that by scanning relatively small
intervals (of length $O(\ell \log \ell)$), we are guaranteed arbitrary
large gaps. The bad news is that gaps this large are more likely to
occur much sooner, as is shown, for instance, in the first table of
this section in the case $\ell=100$. Nevertheless, our algorithm
provides a non trivial bound on $n_\ell$, which is precisely the object
of Theorem 1 which now becomes easy to proves. Indeed, if $\ell$ is
large enough, we have in view of (\ref{eq:condi2})
$$\frac{9m-9t}{9t} &lt; \ell +1,$$
so that
$$m&lt; \frac mt &lt; \ell +2.$$
Therefore, using (\ref{eq:t}) and (\ref{eq:defn}), we have
\begin{eqnarray*}
n_\ell &amp; &lt; &amp; 10^{m+t} = 10^{ \frac{m+t}t \cdot t} = 10^{\left(\frac mt + 1 \right) \cdot t} 
&lt; 10^{(\ell+3) \cdot t}  
&lt;  10^{(\ell+3) ( \frac{\log m}{\log 10} + 2)} &lt;
10^{(\ell+3) ( \frac{\log (\ell+2)}{\log 10} + 2)} \\
&amp; = &amp; e^{\log(\ell+2)^{\ell+3}} \cdot 10^{2(\ell+3)} 
 =  (\ell+2)^{\ell+3} \cdot 10^{2(\ell+3)} = \left( 100(\ell+2) \right)^{\ell+3},
\end{eqnarray*}
which proves Theorem 1. 
\vskip 20pt

\section{Small gaps between consecutive Niven numbers}

It follows from (\ref{eq:conj}) that the sum of the reciprocals of the
Niven numbers diverges, and in fact that $$\sum_{n\le x \atop
n\ \mbox{\tiny Niven number}} \frac 1n = (c+o(1)) \log \log x,$$ where
$c$ is given by (\ref{eq:valeurc}).  \vskip 5pt

We shall call {\it twin Niven numbers} those pairs $(n,n+1)$, such as
(20,21) and (152,153), both members of which are Niven numbers. We can
show that the sum of the reciprocals of twin Niven numbers converges.
In fact, we can establish that if $T$ stands for the set of twin Niven
numbers $(n,n+1)$ and
$$T(x):=\#\{n\le x: (n,n+1)\in T\},$$
then
$$
T(x)= O \left( \frac{x \log \log x}{(\log x)^2}  \right), $$
which is precisely the statement of Theorem 2 and which implies that
\begin{equation}
\sum_{n \atop (n,n+1) \in T} \frac 1n &lt; +\infty. \label{eq:tt}
\end{equation}
Indeed, using Theorem 2, one can write that
$$\sum_{n\le x \atop (n,n+1)\in T} \frac 1n 
= \sum_{n \atop (n,n+1)\in T} \frac 1n 
- \sum_{n&gt;x \atop (n,n+1)\in T} \frac 1n 
= c_2 + O \left( \frac{\log\log x}{\log x}  \right),$$
where 
$$c_2 = 1 + \frac 12 + \frac 13 + \cdots + \frac 19 + \frac 1{20} +
\frac 1{80} + \frac 1{110} + \frac 1{111} + \frac 1{132} + \frac 1{152}
+ \frac 1{200} + \frac 1{209} + \frac 1{224} + \frac 1{399} + \cdots
\approx 3.07,$$
which in particular implies (\ref{eq:tt}).  \vskip 10pt

Before we prove Theorem 2, note that it is easy to show that $T$ is an
infinite set. This can be established by observing that 2 divides
$2\cdot 10^k$ and 3 divides $2\cdot 10^k+1$ for each positive integer
$k$.

On the other hand, using a computer, one can obtain the following table:
\vskip 10pt

\begin{center}
\begin{tabular}{|l|l|}\hline
$x$ &amp; $T(x)$ \\ \hline
10 &amp;  9 \\
100 &amp; 11 \\
1000 &amp; 32 \\ \hline  
\end{tabular} \hspace{1cm} 
\begin{tabular}{|l|l|}\hline
$x$ &amp; $T(x)$ \\ \hline
$10^4$ &amp; 145 \\
$10^5$ &amp;  904 \\
$10^6$ &amp; 6\,191 \\ \hline
\end{tabular} \hspace{1cm} 
\begin{tabular}{|l|l|}\hline
$x$ &amp; $T(x)$ \\ \hline
$10^7$ &amp; 44\,742 \\
$10^8$ &amp; 332\,037 \\
$10^9$ &amp; 2\,551\,917\\ \hline  
\end{tabular}
\end{center}
\vskip 10pt

We now move to prove (\ref{eq:tt}).

Let $(n,n+1)\in T$ and assume that $n$ is a $K$-digit number, with $K\ge 2$. Write $n$ as 
\begin{equation}
n=a\cdot 10^{R+B}+b\cdot 10^{R}+10^R-1, \label{eq:n}
\end{equation}
where $a$ is a $K-B-R$ digit number and $b$ is  a
$B$ digit number not ending with a 9. Here $B$ and $R$ are non negative
integers; later, we shall set $B$ as a function of $K$.
Now, observe that $s(n)=s(a)+s(b)+9R$ and that $s(n+1)=s(a)+s(b)+1$. Since $(n,n+1)\in T$, we have
$$
s(n)|a\cdot 10^{R+B}+b\cdot 10^{R}+10^R-1\quad  \mbox{ and }\quad
s(n+1)|a\cdot 10^{R+B}+b\cdot 10^{R}+10^R.$$
We therefore have
$$\left\{\begin{array}{l}
b\cdot 10^R\equiv -a\cdot 10^{R+B}-10^R+1 \pmod{s(n)},\\
b\cdot 10^R\equiv -a\cdot 10^{R+B}-10^R \pmod{s(n+1)}.\end{array}\right.
$$
Since $s(n)$ and $s(n+1)$ are relatively prime, we can use the Chinese
Remainder Theorem to state that there exists one (and only one) non
negative integer $m&lt;s(n)s(n+1)$, where $m=m(a,R,B,s(n),s(n+1))$,  such
that
\begin{equation}
b\cdot 10^R \equiv m \pmod{s(n)s(n+1)}. \label{eq:trc}
\end{equation}
Observing that $(n,10^R)=1$ and $s(n)|n$, we have that $(s(n),10^R)=1$.
Hence it follows from (\ref{eq:trc}) that there exists one (and only one)
non negative integer $\displaystyle{m'&lt;\frac{s(n)s(n+1)}{(s(n+1),10^R)}}$, where $m'=m'(a,R,B,s(n),s(n+1))$,
satisfying the congruence
\begin{equation}
b \equiv m' \pmod{\frac{s(n)s(n+1)}{(s(n+1),10^R)}}. \label{eq:trc2}
\end{equation}

Assume for now that the integers $K$, $R$, $a$, $B$ and $s(b)$ are all fixed.
Since $s(n)=s(a)+s(b)+9R$ and $s(n+1)=s(a)+s(b)+1$, the number of $b$'s satisfying (\ref{eq:trc2}) is less than
$$\frac{10^B\ (s(n+1),10^R)}{s(n)s(n+1)}+1.$$
Now, as the value of $s(b)$ varies from 0 to $9B-1$, the number 
$\Gamma=\Gamma(K,R,a,B)$  of suitable $b$'s (
that is, those satisfying (\ref{eq:trc2}), for $K$, $R$, $a$ and $B$ fixed, satisfies
$$\Gamma \le \sum_{0\le s(b)\le 9B-1} \left(
\frac{10^B (s(b)+s(a)+1,10^R)}{(s(a)+9R)(s(a)+1)} +1 \right). $$
We then have, letting $k=s(b)$, 
$$\Gamma \le 
\sum_{d|10^R}\sum_{0\le k \le 9B-1 \atop (k+s(a)+1,10^R)=d }
 \left(\frac{10^B\cdot d}{(s(a)+9R)(s(a)+1)}+ 1 \right).
$$
It follows that
\begin{eqnarray*}
\Gamma &amp; \le &amp; \sum_{d|10^R}\left(\frac{9B}{d}+1\right)\left(\frac{10^B\cdot d}{(s(a)+9R)(s(a)+1)}+1\right) \\
&amp; \le &amp; 
\frac{(R+1)^2\cdot 9B\cdot 10^B}{(s(a)+9R)(s(a)+1)}+\frac 52 \frac{10^R\cdot 10^B}{(s(a)+9R)(s(a)+1)} + (9B+1)(R+1)^2.
\end{eqnarray*}
Set $B:=\lfloor \log K \rfloor$.
If $R&gt; 2\log K$, the number of $n$'s satisfying (\ref{eq:n}) is $O(10^K/K^2)$.
Therefore we may also assume that $R\le 2\log K$.
If $s(a)\le K/2$, one can show that the number of $n$'s satisfying (\ref{eq:n}) is $O(10^{K \eta})$ 
for some positive $\eta&lt;1$. Hence we can make the assumption that $s(a)&gt;K/2$.  
We then get that, if $B\ge 1$, 
$$
\Gamma \le \frac{5\cdot 10^B((R+1)^2\cdot 9B+2 \cdot 10^R)}{K^2}. 
$$
From these observations, it follows that
\begin{eqnarray*}
T(10^K) &amp; \le &amp; \sum_{R\le 2\log K} \frac{10^K}{10^{R+B}} \frac{5\cdot 10^B}{K^2} ((R+1)^2\cdot 9B  +  2 \cdot 10^R)\\
&amp; = &amp; 5\frac{10^K}{K^2}\sum_{R\le 2\log K} \left(9B\frac{(R+1)^2}{10^R}+2\right)\\
&amp; \ll &amp; \frac{10^K \log K}{K^2} .
\end{eqnarray*}
Thus, given an arbitrary large $x$, if we choose $\displaystyle{K=\left\lfloor \frac{\log x}{\log 10} \right\rfloor}$, 
Theorem 2 follows immediately.
\vskip 20pt

\section{Final remarks}

Most likely, one can remove the $\log \log x$ on the right hand side of (\ref{eq:tt}), but we could not prove this. 

On the other hand, it has been shown by Grundman \cite{kn:g} that,
given an integer $\ell$, $2\le \ell\le 20$, one could find an infinite
number of Niven numbers $n$ such that $n+1,n+2,\ldots,n+\ell-1$ are
also Niven numbers (and that there does not exist 21 consecutive
numbers which are all Niven numbers). For each integer $\ell\in
[2,20]$, if we denote by $T_{\ell}(x)$ the number of Niven numbers
$n\le x$ such that $n+1,n+2,\ldots,n+\ell-1$ are also Niven numbers, we
conjecture that
$$T_\ell(x) \ll \frac x{\log^\ell x}.$$
\vskip 10pt

\section{Acknowledgements}

The authors would like to thank the referee for
several helpful comments which greatly improved the quality of this
paper.


\begin{thebibliography}{9}
\bibitem{kn:cai} T. Cai, On 2-Niven numbers and 3-Niven numbers, {\it Fibonacci Quart.} {\bf 34} (1996), 118--120.

\bibitem{kn:ck} C. N. Cooper and R. E. Kennedy, On consecutive Niven numbers, {\it Fibonacci Quart.}
{\bf 21} (1993), 146-151.

\bibitem{kn:dkd} J. M. De Koninck and N. Doyon
On the number of Niven numbers up to $x$, 
{\it Fibonacci Quart.}, to appear. 

\bibitem{kn:kdk} J. M. De Koninck, N. Doyon, and I. K\'atai, On the counting function for the Niven numbers,
{\it Acta Arithmetica} {\bf 106} (2003), 265--275.

\bibitem{kn:g} H. G. Grundman, Sequences of consecutive Niven numbers,
{\it Fibonacci Quart.} {\bf 32} (1994), 174--175.

\bibitem{kn:vardi} I. Vardi, Niven numbers, \S2.3 in {\sl Computational Recreations in Mathematics},
Addison-Wesley, 1991, pp.\ 19 and 28--31.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary: 11A63, 11A25.\\

\noindent \emph{Keywords: Niven numbers. }


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A005349}.)
\bigskip
\hrule
\bigskip


\vspace*{+.1in}
\noindent
Received October 21, 2002;
revised version received June 20, 2003.
Published in {\it Journal of Integer Sequences},
July 9, 2003.
\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in




\end{document}
</pre></body></html>