It is well known that there can be at most 20 consecutive integers (in base 10) that are divisible by their digital sum, so called Harshad or Niven numbers. 


How long can a run of consecutive integers be in which each number is not relatively prime to its digital sum?



Runs of consecutive numbers that are not relatively prime to their digital sum
As long as you wish. Let $s(n)$ denote the sum of decimal digits of $n$.


**Lemma.** For any positive integer $k$ there exist distinct prime numbers
$p\_1<p\_2<\ldots<p\_k$ such that $p\_1>5$ and $10^{P}-1$ is coprime to $P:=p\_1p\_2\ldots p\_k$.


**Proof.** Induction in $k$. For $k=1$ choose $p\_1=7$. If $k$ primes $p\_1,\ldots,p\_k$ are found, choose $p\_{k+1}>p\_k$ such that $p\_{k+1}$ does not divide $10^{p\_1\ldots p\_k}-1$. Assume that $10^{p\_1\ldots p\_{k+1}}-1$ is divisible by some $p\_i$, $1\leqslant i\leqslant k+1$. Then $p\_i$ must divide $10^{gcd(p\_1\ldots p\_{k+1},p\_i-1)}-1$ which in turn divides $10^{p\_1\ldots p\_{i-1}}-1$. But this does not happen neither for $i=k+1$ (by the choice of $p\_{k+1}$), nor for $i\leqslant k$ (by induction proposition). A contradiction.


Now choose such $k$ primes and try to find a positive integer $N$ such that both $s(N)+s(i)$ and $N+i$ are divisible by $p\_i$ for $i=1,2,\ldots,k$. If we find such $N$, the numbers $N\cdot 10^K+i$ and $s(N\cdot 10^K+i)$ are not coprime for $i=1,2,\ldots,k$, where $K=k\cdot \varphi(P)$. By Chinese Remainder theorem such $N$ exists if the system of congruences $N\equiv \alpha \pmod P,\, s(N)\equiv \beta \pmod P$ is solvable for any residues $\alpha,\beta$. Choose any $N$ for which $s(N)\equiv \beta \pmod P$ and replace it to $N+10^{N\varphi(P)}(10^P-1)/9$. The remainder of $s(N)$ modulo $P$ does not change, and the remainder of $N$ modulo $P$ is increased by $(10^P-1)/9$. Since this number is coprime to $P$, after finitely many step we get the necessary remainder of $N$ modulo $P$.


