3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Nov 26, 2021 at 20:26
  • $\begingroup$ Yes correct, I'm asking for the minimum. $\endgroup$
    – ThomasL
    Nov 26, 2021 at 20:46

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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