Good luck guessing

Number Theory Level 5

Let $N$ be the smallest positive integer that is divisible by $128$ and has digit sum equal to $128.$ In decimal notation, $N$ consists of $a$ $8$ 's, $b$ $9$ 's and possibly some other digits. What is $a \times b$ ?

Details and assumptions

In decimal notation, $128289$ consists of $2$ $8$ 's, $1$ $9$ 's and some other digits.

The answer is 40.

4 solutions

Zi Song Yeoh
Sep 30, 2013

Firstly, note that the number must have more than $7$ digits. Secondly, any positive integer divisible by $2^7 = 128$ has its last seven digits divisible by $128$ . Now, to minimize $N$ , we have to maximize the sum of digits of the last $7$ digits of $N$ . Let the maximum value of the sum of the last $7$ digits of $N$ be $S$ . We first claim that $S < 60$ . Clearly, $S \le 9 \cdot 7 = 63$ . Obviously $S = 63$ is impossible as $32 \nmid 9999999$ , while $S = 62$ isn't possible either because $32 \nmid 9999998$ . (The other 7-digit numbers are odd). For $S = 61$ , none of $9999988, 9999898, 9998998, 9989998, 9899998, 8999998$ are divisible by $128$ . (the rest are odd.). Finally, for $S = 60$ , the numbers $9999996, 9999888, 9998988, ...$ (any permutation of $3$ $8$ s and $4$ $9$ s.) $, 7999998, 9799998, 9979998, 9997998, 9999798, 9999978$ aren't divisble by $128$ .

Now we show that $S = 59$ is possible. For this, consider $9989888 = 128 \cdot 78046$ .

So, the first few digits of $N$ must sum up to $128 - 59 = 69$ . We want to minimize the number of digits, so we use as many $9$ s as possible and put the remainder as the first digit. Thus, we arrive at $N = 699999999989888$ , with $10$ $9$ s and $4$ $8$ s. So, $a = 10, b = 4$ and (ab = 40).

Moderator note:

Nicely done!

Much of my solution was the same as yours, but I did one part differently. Namely the question of whether there are 7-digit multiples of 128 with a sum of digits $S\ge 59$ .

I decided not to try all the possibilities one at a time, so I proceeded as follows: Supposing there is such a number, it would be of the form $10^7-\sum_{j=0}^4 x_j$ where:

$\bullet$ each $x_j$ is either zero or a power of ten

$\bullet$ $x_0=1$

$\bullet$ $x_j | x_{j+1}$ (for each $j=1,2,3$ )

(The zeros, if any, will be at the end, and the number of them will be $S-59$ .) We want $X=\sum_{j=0}^4 x_j$ to be a multiple of 128.

For X to be even, $x_1=1$ , and if $x_2=1$ then $x_3=1$ as well. That would mean $x_4$ is divisible by 4 but not 8, i.e. $x_4=100$ . But then $X=104$ is not a multiple of 128.

So we must have $x_1=1 \ne x_2$ . Then $x_2=10$ (for X to be divisible by 4) and if $x_3=10$ then $x_4=10$ as well. But then $X=32$ is not a multiple of 128.

So $x_3=100$ (for X to be divisible by 8) and $x_4=X-112\equiv 16 \mod 128$ . Exactly one value works, namely $x_4=10000.$ That is to say, there is exactly one 7-digit multiple of 128 with a sum of digits $S\ge 59$ , namely $10^7-10112=9989888$ .

Peter Byers - 7 years, 8 months ago

sorry, should be $ab = \boxed{40}$

Zi Song Yeoh - 7 years, 8 months ago

Can you explain why the last 7 digits must be divisible by 128? Some kind of theorem involved?

Papa John - 7 years, 8 months ago

Well, since $10^7 = 2^7 * 5^7$ , the last seven digits are periodic with period of $5^7$ . Therefore, the digits to the left of the seven last digits can be whatever we want them to be, and since they have no bearing on the last seven digits, then the last seven digits must be divisible by 128, if that makes more sense.

Michael Tong - 7 years, 8 months ago

128 divides 10^7 so if you find the 7 digit number that divides 128 with the biggest digit sum, you can just keep adding 9 at the start (to get the digit sum to 128) until you get a reminder (which in this case is a 6) and by that get the smallest number that divides 128 and has a digit sum of 128.

Daniel Magen - 7 years, 8 months ago

Ha! same approach!

敬全钟 - 7 years, 4 months ago

Hi. Would someone be able to tell me why N doesn't equal 399999999999998. I thought this was the answer because the digits add to 128 and it also divides by 128 and it is smaller than everyone else's answers? Thanks

Melissa Quail - 6 years, 5 months ago

it doesnt. That was my first answer and I was getting real excited but than I realized it doesnt divide :/

CS ಠ_ಠ Lee - 6 years, 1 month ago

Philips Zephirum Lam
Oct 2, 2013

For the divisor 128, the whole number either divisible or not is determined by the last seven digits such that there are 78 125 seven-digit numbers and among of these, the number should be an even number and last three digits should be divisible by 8. The number must be more than 10 000 000 because the maximum sum of the seven digits, 9 x 7 = 63. The last three digits numbers, 898, 988 and 998 are out because they does not satisfies the conditions. 10 000 000 - 128 = 9 999 872 less than 9 999 888 also not satisfies the following conditions. Let's try sum of seven digits = 59. 9 989 888 divide by 128 = 78 046 So the remaining sum, 128 - 59 = 69 69 = 7 x 9 + 6, such that the largest number is 999,999,969,989,888 We found that there are 10 9's and 4 8's Therefore, 10 x 4 = 40.

I believe you meant the smallest possible number, so the 6 must come at the left or most-significant digit. That is 699,999,999,989,888.
The count of 9's and 8's is the same, of course.

Steven Perkins - 7 years, 8 months ago

Wei Jie Tan
Oct 4, 2013

Note that $128 = 2^7$ and $10000000 = 2^7 * 5^7$ Hence $128|10000000$ Counting down from 10000000, we find the number with the largest possible digit sum. We find that the number is 9989888 Let $g$ be an integer $\overline{g9989888}$ must be a multiple of 128 as $\overline{g9989888} = g* 10000000 + 9989888 = 128(g*5^7 + 7806)$

Hence, the digits of $g$ can be chosen at will.

Thus, for $N$ to be the smallest, $g = 69999999$ Hence $N = 699999999989888$ $a = 10$ $b = 4$

$a*b = 10* 4 = 40$

Piyushkumar Palan
Oct 5, 2013

29999 99999 99999 is smallest number with digit sum 128. For divisibility by 128 i focused on last 7 digits. (100 00000 - 128) = 99 99872 and further down. Got interesting combinations like 99 98976, 99 89888, 97 97888, 89 97888, 88 99968, 79 89888.. So 99 89888 works best as sum only 4 less than 99 99999.... so 29999 99999 99999 becomes 69999 99999 89888 [my Answer]

Eager to get better solution, sorry for mistakes if any...Thanks to all :)

Hello sir! :)

Vikram Waradpande - 7 years, 8 months ago

Good luck guessing

The answer is 40.

4 solutions

Moderator note:

0 pending reports