I know that every third number is divisible by $3$ and hence, sum of its digits is divisible by $3$. Same holds for $9$ also. But how do we generalise it? We know that the divisibility condition for higher powers of $3$ is not about the sum of digits. How can we find $n$ such that in a group of $n$ consecutive positive integers, there is a number such that the sum of its digits is divisible by $27$ (or $81,$ say)? Does it exist? Please prove or disprove.
Answer
New answer instead of editing the - already accepted - answer because the argument is significantly different (and much simpler).
Let $Q(x)$ denote the digit sum of $x$.
Let $r\ge 1$. Then $n=10^r-1=\underbrace{99\ldots 9}_r$ is the smallest $n$ such that among any $n$ consecutive positive integers, at least one has digit sum a multiple of $9r$.
That no smaller $n$ works, is immediately clear because in $1,2,3,\ldots, 10^r-2$, all digit sums are $>0$ and $<9r$.
Remains to show that in any sequence of $n$ consecutive integers, a digit sum divisible by $9r$ occurs.
This is well-known for $r=1$. For $r>1$, consider $n$ consecutive positive integers
$$a,a+1,\ldots, a+n. $$
Among the first $9\cdot 10^{r-1}=n-(10^{r-1}-1)$ terms, one is a multiple of $9\cdot 10^{r-1}$. Say, $9\cdot 10^{r-1}\mid a+k=:b$ with $0\le k<9\cdot 10^{r-1}$. Then $Q(b)$ is a multiple of $9$, and as the lower $r-1$ digits of $b$ are zero, we have $Q(b+i)=Q(b)+Q(i)$ for $0\le i<10^{r-1}$ and hence
$$Q( b+10^j-1)=Q(b)+9j,\qquad 0\le j\le r-1.$$ (Note that $k+10^{r-1}-1<10^r-1$, so these terms are really all in our given sequence). It follows that $9r$ divides one of these $Q(b+10^j-1)$.
No comments:
Post a Comment