We assume that the standard input contains a sequence of non-zero integers between – 121 and 121, which ends with 0. This sequence will be given by the user. 1. Write an algorithm, called Decomposition_Powers_Three, which produces the decomposition of each integer using powers of 3, namely 1, 3, 9, 27, and 81, and the + and operators. Each power of 3 should appear at most once in the decomposition. Examples: 1 = 1 2 = 3 1 3 = 3 4 = 3 + 1 7 = 9 3 + 1 14 = 27 9 3 1 43 = 81 27 9 3 + 1 121 = 81 + 27 + 9 + 3 + 1 2. Show that the algorithm Decomposition_Powers_Three is correct using an informal proof (i.e., discussion). 3. Give a program corresponding to Decomposition_Powers_Three, using any of your favorite programming languages. Observation: The intervals [-121,-41], [-40,-14], [-13,-5], [-4,-2], [-1,-1], [1,1], [2,4], [5,13], [14,40], and [41,121] play a particular role
