# Among $k$ consecutive numbers one has sum of digits divisible by $11$

Find the least positive integer $k$ with the property that given any $k$ consecutive positive integers, there is at least one whose sum of digits is divisible by $11$.

I can show for $k\leq 57$. Among any $29$ consecutive positive integers with the same hundreds' digit and higher digits, at least one has sum of digits divisible by $11$. This can be checked by casework. Since our consecutive positive integers may span two different hundreds' digits, we have $k\leq 29+28=57$.

On the other hand, among the numbers $1,2,\ldots,28$ none has sum of digits divisible by $11$, so $k\geq 29$.

• Hint: $\overline{abcd}=a\cdot10^3+b\cdot10^2+c\cdot10^1+d$, and $10=11-1$. – Lucian Jun 27 '15 at 10:04
• @Lucian How is this useful to solve the question? – Did Jun 28 '15 at 9:20
• Link. – Lucian Nov 11 '15 at 13:31

This is what happens for the numbers in the range $[1,100]$:

  1  2  3  4  5  6  7  8  9  1
2  3  4  5  6  7  8  9 10  2
3  4  5  6  7  8  9 10  0  3
4  5  6  7  8  9 10  0  1  4
5  6  7  8  9 10  0  1  2  5
6  7  8  9 10  0  1  2  3  6
7  8  9 10  0  1  2  3  4  7
8  9 10  0  1  2  3  4  5  8
9 10  0  1  2  3  4  5  6  9
10  0  1  2  3  4  5  6  7  1


and this what happens in the range $[101,200]$ (just a $+1$ with respect to the previous table)

  2  3  4  5  6  7  8  9 10  2
3  4  5  6  7  8  9 10  0  3
4  5  6  7  8  9 10  0  1  4
5  6  7  8  9 10  0  1  2  5
6  7  8  9 10  0  1  2  3  6
7  8  9 10  0  1  2  3  4  7
8  9 10  0  1  2  3  4  5  8
9 10  0  1  2  3  4  5  6  9
10  0  1  2  3  4  5  6  7 10
0  1  2  3  4  5  6  7  8  2


Then in the range $[201,300]$:

  3  4  5  6  7  8  9 10  0  3
4  5  6  7  8  9 10  0  1  4
5  6  7  8  9 10  0  1  2  5
6  7  8  9 10  0  1  2  3  6
7  8  9 10  0  1  2  3  4  7
8  9 10  0  1  2  3  4  5  8
9 10  0  1  2  3  4  5  6  9
10  0  1  2  3  4  5  6  7 10
0  1  2  3  4  5  6  7  8  0
1  2  3  4  5  6  7  8  9  3


Then in the range $[301,400]$:

  4  5  6  7  8  9 10  0  1  4
5  6  7  8  9 10  0  1  2  5
6  7  8  9 10  0  1  2  3  6
7  8  9 10  0  1  2  3  4  7
8  9 10  0  1  2  3  4  5  8
9 10  0  1  2  3  4  5  6  9
10  0  1  2  3  4  5  6  7 10
0  1  2  3  4  5  6  7  8  0
1  2  3  4  5  6  7  8  9  1
2  3  4  5  6  7  8  9 10  4


$\ldots$ and so on, till the range $[1001,1100]$.

We do not need any more table. When crossing $100n$, we always switch between two of the previous tables. So we just need to count how many consecutive non-zeroes are there, at the top and the bottom of every table, then add a little of handwork. We may check that if we cross a number of the form $100 n$, we cannot have more than $20+18$ consecutive integers with the digit sum $\not\equiv 0\pmod{11}$. Than happens, for instance, in the range $[999981,1000018]$.

Anyway:

Among $\color{red}{39}$ consecutive positive integers, there is always an integer with the digit sum $\equiv 0\pmod{11}$.

• Why isn't that $20+28$? There are $28$ non-zero digit sums at the start of the first table. And the first table follows the fourth table in the range $[5599999999981,5600000000028]$. – TonyK Jun 28 '15 at 11:12
• @TonyK: the issue is that $56*10^k$ has a digit sum that is a multiple of $11$. – Jack D'Aurizio Jun 28 '15 at 11:45
• Oh yes, so it does. I will leave my comment up, in case anybody else makes the same mistake as me. – TonyK Jun 28 '15 at 11:51
• "Anyway" is not a valid argument. The number $39$ comes out of thin air. – Christian Blatter Jun 28 '15 at 17:49
• @ChristianBlatter: no, the number $39$ comes from analyzing, case-by-case, what happens when a particular table if followed by another one. Should I really do that case-by-case? – Jack D'Aurizio Jun 28 '15 at 18:01

Denote by $r(n)$ the remainder modulo $11$ of the decimal digit sum of $n$. A number $n$ is good, if $r(n)=0$.

Claim: The difference $n'-n$ between two consecutive good numbers $n$, $n'$ is at most $39$, and this bound cannot be improved.

Proof:

The numbers $n:=999\,980$ and $n':=1\,000\,019$ are consecutive good numbers with $n'-n=39$.

Now for the essential part: Denote by $p(n)\geq0$ the number of trailing nines in the decimal representation of $n$. Example: $p(4199)=2$. Then we have the recursion $$r(n+1)=r(n)+1+2p(n)\qquad({\rm mod}\ 11)\ ,\tag{1}$$ because in the transition $n\rightsquigarrow n+1$ the $p(n)$ trailing nines are replaced by zeros, and the immediately preceding digit is increased by $1$.

Assume now that $n$ is a good number. Write $$n=n_0+j$$ with $n_0$ divisible by $10$ and $0\leq j\leq 9$. Put $$n_k:=n_0+10k\qquad(k\geq1)\ .$$ If $r(n_1)\ne1$, i.e., $r(n_1)\in\{0,2,3,4,5,6,7,8,9,10\}$, then there is a good number $n'$ in the decade beginning with $n_1$, and $n'-n\leq19$.

If $r(n_1)=1$, but $r(n_2)\ne1$, then there is a good number $n'$ in the decade beginning with $n_2$, and $n'-n\leq29$.

It remains to consider the case $r(n_1)=r(n_2)=1$. The recursion $(1)$ then implies $$10+2p(n_2-1)=0\qquad({\rm mod}\ 11)\ ,$$ or $p(n_2-1)=6\ ({\rm mod}\ 11)$. In particular $p(n_2-1)\geq2$, and this enforces $p(n_3-1)=1$. Using $(1)$ again we can conclude that $r(n_3)=2$, whence $n':=n_3+9$ is good, with $n'-n\leq39$.