João wrote all the powers of 2, 3, and 5 greater than 1 and less than 2017 on a sheet of paper. Then, he performed all possible products of two distinct numbers from this sheet and wrote them on another sheet of paper. What is the number of integers that João recorded on the second sheet?

#
Solution

Initially, we need to find the powers of 2, 3, and 5 recorded on the first sheet. Since $2^{10}<2017<2^{11}, 3^{6}<2017<3^{7}$, and $5^{4}<2017<5^{5}$, the powers written on the first sheet can be divided into three sets:

$$
P_{2}=\left\{2^{1}, 2^{2}, \ldots, 2^{10}\right\}, P_{3}=\left\{3^{1}, 3^{2}, \ldots, 3^{6}\right\} \text { and } P_{5}=\left\{5^{1}, 5^{2}, 5^{3}, 5^{4}\right\}
$$

Due to the unique factorization into prime numbers, the products obtained by multiplying powers from different sets are also distinct. Thus, by the Multiplication Principle, there are $10 \cdot 6 + 10 \cdot 4 + 6 \cdot 4 = 124$ distinct products of powers. Now we need to count how many products exist between powers of the same base. Given a prime number $q$ and the set $P_{q}=\left\{q^{1}, q^{2}, \ldots, q^{k}\right\}$, the smallest product of distinct powers is $q^{1} \cdot q^{2} = q^{3}$ and the largest is $q^{k-1} \cdot q^{k} = q^{2k-1}$. We will now verify that all powers $q^{t}$ with exponent $t$ between 3 and $2k-1$ can be obtained as a product of two numbers from this set. If $t$ is even, we can write $t = 2m$ and given that $3 < t < 2k-1$, we have $1 < m < k-1$. Therefore, it suffices to multiply the powers $q^{m-1}$ and $q^{m+1}$, which are part of the set $P_{q}$, to obtain $q^{m-1} \cdot q^{m+1} = q^{2m} = q^{t}$. If $t$ is odd, we can write $t = 2m+1$ and given that $3 < t < 2k-1$, we have $0 < m < k-1$. It then suffices to multiply $q^{m}$ and $q^{m+1}$, which are also part of $P_{q}$, to obtain $q^{m} \cdot q^{m+1} = q^{2m+1} = q^{t}$. This shows that there are exactly $2k-3$ distinct products of powers obtained by multiplying two elements of $P_{q}$. Applying this count with $q=2, 3$, and 5, we can conclude that there are $17 + 9 + 5 = 31$ more distinct powers of the same base on the second sheet. Therefore, the total number of numbers on the second sheet is $124 + 31 = 155$.