1
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .