Integers Not Divisible by Digit Sum

We consider only the 3-digit numbers which are divisible by 9. The digit sum of these numbers must be either 9 or 18 (it cannot be 0, and only 999 has digit sum of 27).

We call a number 'nice' if it is divisible by its digit sum.

Let A be the list of all 3-digit integers that are divisible by 9. A = {108,117,...,999}. We see that all even numbers in A are 'nice', as they are divisible by 18, and their digit sum can only be 9 or 18.

We claim that the maximum gap between two 'nice' numbers in A is 18. Indeed, if 2 consecutive 'nice' elements in A are separated by more than 18, the elements between them are all not 'nice'. This means there are 2 consecutive non-'nice' elements, both of which are odd (they cannot be even since all the even numbers in A are nice). This is impossible because 2 consecutive elements in A are separated by 9.

Hence we have shown that the maximum gap between two 'nice' numbers is 18. There will be 17 integers between these 2 numbers. Maximum possible value of N = 17 (This can happen, for example, between 559 to 575)

Lemma: If the digit sum of a number is divisible by 9, then the number itself is divisible by 9, and vice versa.

Proof: Since this question only tackles 3-digit numbers, let's assume the number takes the general form of $\overline{abc}$ , where $1\leq a \leq 9$ and $0 \leq b,c\leq 9$

Now $\overline{abc} = 100a + 10b + c$

It is clear that $100a + 10b + c = a + b + c + 9(11a + b)$

Therefore, $100a+10b+c \equiv a+b+c \pmod{9}$ .

It follows that the digit sum of a 3 digit number is divisble by 9 whenever the number itself is divisible by 9, and vice versa.

Now we shall prove the upper bound on N.

Barring the obvious case of 999, all other 3-digit multiples of 9 have digit sums 9 or 18.

All 3-digit multiples of 18 will be divisible by their corresponding digit sums (which are either 9 or 18) by the lemma. Thus, the largest theoretical value of N is 17, corresponding to the 17 numbers between 2 consecutive 3-digit multiples of 18.

Simple checking will confirm that for the 17 consecutive numbers between 739 and 755 (inclusive), the condition holds.

First, we look at 2 digit numbers. We realize after working out that the sum of digits of tens i.e. 10, 20, 30, 40 ... are multiples of themselves. Therefore, we will be looking within the range of ones to nines. (Max range of 9) We also see that for 12, 42, 72, they are multiples of them selves, so 11-19, 41-49, 71-79 are not accepted. We also see that 21 and 81 are also not accepted. We are left with 51-59 and 91-99. 54 is divisible by its digit sum so 51-59 is not accepted. From 91-99, we can deduce that for the 3 digit numbers, the largest range would be in the 9xx range and that the range would be less than 18 since if the digit sum is 18, the number would be a multiple of 18 since its an even number and a multiple of 9. Therefore, we look into the tens place. 910, 960, 990 are not accepted. 972 would break the chain from 960 to 990. Hence, we look at 973 to 990 since 973 to 989 gives us 17 numbers.

We know that every 3-digit number which is divisible by 18 is naturally divisible by 9. For that, the sum of three digits must be divisible by 9 and with the 3-digit number, it can be 9 or 18.( We don't count 27 because the 3-digit number which has the sum of digits is 27 is only 999, not be divisible by 18). Therefore, every three-digit number divisible by 18 is also divisible by the sum of its digits and the largest possible value of N is 17. The 17 valid number: 559, 560, 561, 562, 563, 564, 565, 566, 567, 568, 569, 570, 571, 572, 573. 574, 575.

since n is a three digit number,let n=100a+10b+c, where a,b,c are the digits of the number at hundreds,tens and units place of the number respectively. now 100a+b+c=10(a+b+c)+9(10a-c) since the number n=100a+10b+c is divisible by a+b+c hence 9(10a-c) must be divisible by a+b+c if we put c=0,i.e n=100,110,.......,990 then for maximum consecutive integers N, range of n should be maximum and values of n must not be divisible by (a+b) [since c=0] we get n belongs to (551,599) or (911,959) for n belonging to (551,599) ,a=5,b lies between 5 and 9 and c lies between 0 and 9. 9(10a-c)=multiple of a+b+c therefore 9(50-c)=multiple of (5+b+c) =multiple of(10+c,14+c) checking for values of c from 0 to 9 we get the acceptable interval of n to be (559,575) similarly proceeding for the interval (911-959),we get a smaller acceptable interval for n hence the range of n for maximum N is n belongs to (559,575) N=(575-559)+1=17 which is the required answer.

If we have 18 consecutive numbers, then there must be 2 of them which are multiples of 9. The digit sum of these 2 numbers will be a multiple of 9, which is 9, 18 or 27. The only possibility of 27 is $999$ , and $999 = 27 \times 37$ , and $990$ is a multiple of 18. Hence, we know that one of these numbers must be a multiple of 18, and hence a multiple of the digit sum.

Thus, $N\leq 17$ . Checking the numbers 973 to 989, this gives 17 integers each of which is not a multiple of its digit sum.

$\begin{array}{llllllllll} N & 973 & 974 & 975 & 976 & 977 & 978 & 979 & 980 & \\ S(N) & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 17 & \\ N & 981 & 982 & 983 & 984 & 985 & 986 & 987 & 988 & 989 \\ S(N) & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 \\ \end{array}$

Because every three-digit number divisible by 18 is also divisible by the sum of its digits.

Proof : Every number that is divisible by 18 is divisible by 9 so the sum of its digits is also divisible by 9. In case of three digit numbers, the sum of digits of such numbers can only be 9 or 18.

I used C programming for this. The numbers are 559, 560, 561, 562, 563, 564, 565, 566, 567, 568, 569, 570, 571, 572, 573. 574, 575