Spring 2010 Problem 7: How persistent is your addition?
Let's measure the additive persistence of an integer by the number of times you have to add the number's digits together until you get a one-digit number. For example, starting with 77, you add 7 and 7 to get 14. With 14, you add 1 and 4 to get 5 (a one digit number). Therefore, the additive persistence of 77 is 2 (since we added twice). Similarly, the additive persistence of 123 is 1 and the additive persistence of 5678 is 2.
Find the smallest number with an additive persistence of four. (Hint: find the smallest numbers with additive persistence of one, two, and three first.)
Solution
Roland Womack got the bonus points for the best explanation and first correct answer:
The smallest number with additive persistence 1 is 10. This is true because the number must be at least a two digit number. 10 is the smallest two digit number, and it has an additive persistence of 1. The smallest number with additive persistence 2 is 19. The sum of the two digits must add up to at least another two digit value. To keep the value as low as possible, we can use 1 for the first digit and the second digit follows suit. The smallest number with additive persistence 3 is 199. We want to force the number to require 3 evaluations. Adding the initial values together, we have 19, which from before we know has an additive persistence of 2, so the total additive persistence is 3.
Ignoring the additive persistence of 1, and looking at 2 & 3, the pattern of one less than 20, 200, etc. becomes obvious. However, simply increasing by a factor of ten was not sufficient. Instead, we can look at how the additive persistence of 199 included the additive persistence of 19. Therefore, one could hypothesize that the additive persistence of 4 would need to include 199 as its first evaluation to determine the smallest possible value. Maintaining the pattern of 1 followed by a series of 9s, what number would lead to a first evaluation of 199? We subtract the 1 from the 199 to get 198, and then divide this number by 9 to determine how many 9s are necessary to follow the 1. 198/9 = 22. Therefore, the smallest number with an additive persistence of 4 is 1.9999999999999999999999 x 10^22. This can be confirmed by calculating through the steps necessary to evaluate the additive persistence.