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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.