# Divisible by seventeen

Determine the smallest integer $n \geq 0$ for which

• the decimal digit sum of n is a multiple of 17
• the decimal digit sum of $n+1$ is a multiple of 17.

No computers! The puzzle has a nice direct solution.

• i understand the first requirement of this puzzle but i dont understand n+1 thing... :\ Feb 15 '16 at 11:07
• @manshu you have to find a number and its successor (e.g. 120 and 121 or maybe 255 and 256) and both numbers must each fulfil the condition "the sum of digits is a multiple of 17" Feb 15 '16 at 14:04
• @Falco ah..thanks. I thought it was "(decimal digit of sum of n) + 1 is a multiple of 17", which was quite impossible. Feb 15 '16 at 14:39

We know that the digit sum of $n$ is a multiple of $17$, let us write that as ($d_1$ being the least significant digit): $$d_m + d_{m-1} + ... + d_2 + d_1 = x * 17$$ If $d_1$ would be smaller than $9$ then the digit sum of $n+1$ would be $$x * 17 + 1$$ which is obviously not divisible by $17$, so $d_1$ must be $9$. If $d_2$ would be smaller than $9$, then the digit sum of $n + 1$ wold be $$x * 17 - 9 + 1 = x * 17 - 8$$ which is not divisible by $17$ again, so $d_2$ is must be $9$ well. If $d_3$ would be smaller than $9$, then the digit sum of $n + 1$ would be $$x * 17 - 9 - 9 + 1 = x*17 - 17$$ which is divisible by $17$. This means we look for the smallest number with digit sum divisible by $17$ with the last 2 digits equal $9$ and the third last digit lower than $9$. This is obviously: $$8899$$.

• This method would generalize to a version of the puzzle where instead of multiples of 17, you wanted multiples of $9m - 1$ for integer $m$ (8, 17, 26, 35, ...) I don't think the puzzle would have solutions for multiples of any numbers that were equal to 8 (mod 9). Feb 15 '16 at 22:14
• @MichaelSeifert Actually all numbers equal to 8 (mod 9) and their divisors will have a solution. The numbers which definitely won't have a solution are multiples of 9, because 9m-1 will be never divisible by 9. Feb 16 '16 at 6:58
• Good point. In fact, I think any number that's relatively prime to 9 (i.e., not a multiple of 3) will be a divisor of 9m - 1 for some m. Feb 16 '16 at 13:16

The integer in question must end with a bunch of 9s to leave the "ones to carry" to the previous digit. Hence it can be written as $abc..A9...9$ with $n$ 9s at the end and $A$ as the last digit less than 9. When we add 1 to this, it equals $abc..[A+1]0...0$, making the difference between both numbers' digit sums $9n-1$. 2 is the smallest value of $n$ allowing that expression to be divided by 17, so $n$ can be everything written as $17k+2$. Before bothering with over-17-digit numbers or something, we can simply settle for $n=2$ and fill in the few blanks we have. 9*2=18=17+1, so we at least need a bunch of digits with the sum 16, which can be the sum of 8+8 (7+9 is not allowed).

So the smallest solution is:

8899.

This is how I arrived at the solution, less formal more intuitive.

The solution is:

8899

Both numbers are only 1 apart, but need to have a digit sum which is the same or 17 (or 34,51...) apart. If you take 100 and 101 the digit sums are 1 and 2, only 1 apart, the same for 8 and 9 - in fact the only way I can get another difference than 1 in the digit sums, is when the digits swap from

xxx9 to xxx0 - e.g. 9 -> 10 (digit sums 9 and 1)

But a difference of 8 is not enough so try another 9

99 -> 100 (digit sums 18 and 1)

They are 17 apart, so this can work - the second number is just 16 short of being a multiple of 17, so I have to add digits with a sum of 16, like 8+8. This gives the result of

8899 -> 8900 (digit sums 34 and 17)

And this is also the smallest solution, since I can form a digit sum of 16 only with more digits, or as 97 or 79. And the number 9799 is bigger than 8899 and 7999 does not work, because another 9 rolls over and the successor is 8000.

889,999,999,999,999,999,999

... is one solution. I can't find a smaller one, is this proof enough? ;)

• Considering that the other answers have a smaller number, it's not proof enough :P
– f''
Feb 15 '16 at 2:26
• I surely agree! Although my difference to the solution is relatively simple, just remove the trailing seventeen $9$s.
– bers
Feb 15 '16 at 14:39

N=458

Because:

4 + 5 + 8 = 17

and:

N + 1 = 459 = 17 * 27