2006 Indonesia MO Problems/Problem 8
Contents
Problem
Find the largest 85-digit integer which has property: the sum of its digits equals to the product of its digits.
Solution
Let be the digit from the left, where . Because we want to maximize the number, we let for .
First we'll prove that . Afterward, we'll find the largest value of and use it to find the 85-digit integer.
Lemma 1:
The sum of the digits of the 85-digit number is at most . If we let , then the product of the digits is at least , which is more than . That means .
Since are all equal to 1, the sum of the digits of the wanted 85-digit number is at most . If we let , then the product of the digits is at least , which is more than . That means
Now we'll consider the largest possible values for . From the Lemma, there are at least ones, so the sum (and product) is at least and at most
Case:
If , then the possible products are since the prime factorization only consists of prime numbers less than 10.
- If the product of the digits is 90, then and . However, the sum of the digits would be , so the product can not be 90.
- If the product of the digits is 108, then . This can be achieved if and , and , or and . The first case results in a sum of , the second case results in a sum of , and the third case results in a sum of . Thus, the product can not be 108.
- If the product of the digits is 126, then and . However, the sum of the digits would be , so the product can not be 126.
- If the product of the digits is 135, then and . However, the sum of the digits would be , so the product can not be 135.
From all the cases, can not equal 9.
Case:
If , then the possible products are since the prime factorization only consists of prime numbers less than 10.
- If the product of the digits is , then . This can be achieved if and , and , or and . The first case results in and the second case results in . However, the third case results in , which works.
- If the product of the digits is , then and . However, the sum of the digits is , so the product can not equal 112.
- If the product of the digits is , then and . However, the sum of the digits is , so the product can not equal 120.
- If the product of the digits is , then . This can be achieved if and , , and , or . The first case results in a sum of , the second case results in a sum of , the third case results in a sum of , and the fourth case results in . Thus, the product can not be 128.
We found one working case where . If , then the numbers are smaller, so the largest 85-digit number where the sum of the digits equals the product of the digits is .
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 for .
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 .
See Also
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 |