# How many consecutive integers to ensure one has digit sum divisible by 19?

How many consecutive positive integers are at least required, such that there is always a number in such a sequence whose sum of digits is divisible by 19?

• Just to be clear: are you asking for the minimum $N$ such that ANY sequence of $N$ consecutive positive integers contains a number whose digit sum is divisible by 19? Nov 26, 2021 at 20:26
• Yes correct, I'm asking for the minimum. Nov 26, 2021 at 20:46

The minimum $$N$$, such that ANY sequence of $$N$$ consecutive positive integers contains a number whose digit sum is divisible by 19, is:

199.

Proof:

1. Firstly, we can easily find a lower bound on $$N$$:

Among all the integers from $$1$$ up to $$198$$, there is no number with digit sum divisible by 19, because to get a sum of 19 we need at least two 9s and a 1 among the digits. So $$N\geq199$$.

2. Following on from the above statement, notice that

any string of consecutive integers from $$100k$$ to $$100k+99$$ contains numbers with all possible digit sums modulo 19: where $$D(\cdot)$$ means digit sum, we have $$D(100k)=D(k),D(100k+1)=D(k)+1,\cdots,D(100k+9)=D(k)+9,D(100k+19)=D(k)+10,D(100k+29)=D(k)+11,\cdots,D(100k+89)=D(k)+17,D(100k+99)=D(k)+18.$$

3. And it is clear that

any string of 199 consecutive positive integers must contain a string from $$100k$$ to $$100k+99$$ for some $$k$$, whether it be the last 100, the first 100, or somewhere in between.