Maths Olympiad Prep

Library / /37 of 740

, 2015

Number theory Difficulty 4.4 AIME Find the answer United States

Problem:
Let nn be the smallest positive integer with exactly 20152015 positive factors. What is the sum of the (not necessarily distinct) prime factors of nn? For example, the sum of the prime factors of 7272 is 2+2+2+3+3=142+2+2+3+3=14.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
Answer: 116116

Note that 2015=5×13×312015 = 5 \times 13 \times 31 and that N=23031254N = 2^{30} \cdot 3^{12} \cdot 5^{4} has exactly 20152015 positive factors. We claim this is the smallest such integer. Note that N<266N < 2^{66}.

If nn has 33 distinct prime factors, it must be of the form p30q12r4p^{30} q^{12} r^{4} for some primes p,q,rp, q, r, so n23031254n \geq 2^{30} \cdot 3^{12} \cdot 5^{4}.

If nn has 22 distinct prime factors, it must be of the form peqf>2e+fp^{e} q^{f} > 2^{e+f} where (e+1)(f+1)=2015(e+1)(f+1) = 2015. It is easy to see that this means e+f>66e+f > 66 so n>266>Nn > 2^{66} > N.

If nn has only 11 prime factor, we have n22014>Nn \geq 2^{2014} > N.

So NN is the smallest such integer, and the sum of its prime factors is 230+312+54=1162 \cdot 30 + 3 \cdot 12 + 5 \cdot 4 = 116.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.