2006 Indonesia MO Problems/Problem 8

Problem

Find the largest 85-digit integer which has property: the sum of its digits equals to the product of its digits.

Solution

Let $a_n$ be the $n^\text{th}$ digit from the left, where $1 \le n \le 85$ . Because we want to maximize the number, we let $a_n \ge a_{n+1}$ for $1 \le n \le 84$ .

First we'll prove that $a_8 = 1$ . Afterward, we'll find the largest value of $a_1$ and use it to find the 85-digit integer.

Lemma 1: $a_8 = 1$
The sum of the digits of the 85-digit number is at most $85 \cdot 9 = 765$ . If we let $a_10 = 2$ , then the product of the digits is at least $1024$ , which is more than $765$ . That means $a_{10} = 1$ .

Since $a_{10}, a_{11}, \cdots a_{85}$ are all equal to 1, the sum of the digits of the wanted 85-digit number is at most $76 + 9 \cdot 9 = 157$ . If we let $a_8 = 2$ , then the product of the digits is at least $256$ , which is more than $157$ . That means $a_8 = 1. \blacktriangleright$

Now we'll consider the largest possible values for $a_1$ . From the Lemma, there are at least $78$ ones, so the sum (and product) is at least $85$ and at most $78 + 9 \cdot 7 = 141.$

Case: $a_1 = 9$
If $a_1 = 9$ , then the possible products are $90, 108, 126, 135$ since the prime factorization only consists of prime numbers less than 10.

If the product of the digits is 90, then $a_2 = 5$ and $a_3 = 2$ . However, the sum of the digits would be $82 + 9 + 5 + 2 = 98$ , so the product can not be 90.
If the product of the digits is 108, then $\prod_{i=2}^7 a_i = 12$ . This can be achieved if $a_2 = 6$ and $a_3 = 2$ , $a_2 = 4$ and $a_3 = 3$ , or $a_2 = 3$ and $a_3 = a_4 = 2$ . The first case results in a sum of $82 + 9 + 6 + 2 = 99$ , the second case results in a sum of $82 + 9 + 4 + 3 = 98$ , and the third case results in a sum of $81 + 9 + 3 + 2 + 2 = 97$ . Thus, the product can not be 108.
If the product of the digits is 126, then $a_2 = 7$ and $a_3 = 2$ . However, the sum of the digits would be $82 + 9 + 7 + 2 = 100$ , so the product can not be 126.
If the product of the digits is 135, then $a_2 = 5$ and $a_3 = 3$ . However, the sum of the digits would be $82 + 9 + 5 + 3 = 99$ , so the product can not be 135.

From all the cases, $a_1$ can not equal 9.

Case: $a_1 = 8$
If $a_1 = 8$ , then the possible products are $96, 112, 120, 128$ since the prime factorization only consists of prime numbers less than 10.

If the product of the digits is $96$ , then $\prod_{i=2}^7 a_i = 12$ . This can be achieved if $a_2 = 6$ and $a_3 = 2$ , $a_2 = 4$ and $a_3 = 3$ , or $a_2 = 3$ and $a_3 = a_4 = 2$ . The first case results in $82 + 8 + 6 + 2 = 98$ and the second case results in $82 + 8 + 4 + 3 = 97$ . However, the third case results in $81 + 8 + 3 + 2 + 2 = 96$ , which works.
If the product of the digits is $112$ , then $a_2 = 7$ and $a_3 = 2$ . However, the sum of the digits is $82 + 8 + 7 + 2 = 99$ , so the product can not equal 112.
If the product of the digits is $120$ , then $a_2 = 5$ and $a_3 = 3$ . However, the sum of the digits is $82 + 8 + 5 + 3 = 98$ , so the product can not equal 120.
If the product of the digits is $128$ , then $\prod_{i=2}^7 a_i = 16$ . This can be achieved if $a_2 = 8$ and $a_3 = 2$ , $a_2 = a_3 = 4$ , $a_2 = 4$ and $a_3 = a_4 = 2$ , or $a_2 = a_3 = a_4 = a_5 = 2$ . The first case results in a sum of $82 + 8 + 8 + 2 = 100$ , the second case results in a sum of $82 + 8 + 4 \cdot 2 = 98$ , the third case results in a sum of $81 + 8 + 4 \cdot 3 = 101$ , and the fourth case results in $80 + 8 + 2 \cdot 4 = 96$ . Thus, the product can not be 128.

We found one working case where $a_1 = 8$ . If $a_1 \le 7$ , then the numbers are smaller, so the largest 85-digit number where the sum of the digits equals the product of the digits is $\boxed{8322\underbrace{111 \cdots 1}_{81\text{ ones}}}$ .

Python Code

Although Python programs are not allowed in the Indonesia MO, we can run a computer program that prints out the first 7 digits of all numbers where the product of the digits equals the sum of the digits and $a_n = 1$ for $8 \le n \le 85$ .

number = [1,1,1,1,1,1,1]
for i in range(0,8888889): #Number of iterations
   number[6] += 1 #Adds one to a_7
   for j in range(0,6): #Regroups if necessary
      if number[6-j] == 10:
         number[6-j] = 0
         number[5-j] += 1

   s = 78 #Sum of numbers from a_8 to a_85
   for k in number: #Calculate sum
      s += k

   product = 1 #Product of numbers from a_8 to a_85
   for n in number: #Calculate product
      product *= n

   if s == product: #Checks if sum equals product
      print(number)

The computer program verifies that the largest 85-digit number that meets the criteria is $\boxed{8322\underbrace{111 \cdots 1}_{81\text{ ones}}}$ .

2006 Indonesia MO (Problems)
Preceded by Problem 7	1 • 2 • 3 • 4 • 5 • 6 • 7 • 8	Followed by Last Problem
All Indonesia MO Problems and Solutions

Page

Toolbox

Search

2006 Indonesia MO Problems/Problem 8

Contents

Problem

Solution

Python Code

See Also