HMMT 十一月 2018 · 冲刺赛 · 第 16 题
HMMT November 2018 — Guts Round — Problem 16
题目详情
- [ 10 ] A positive integer is called primer if it has a prime number of distinct prime factors. A positive integer is called primest if it has a primer number of distinct primer factors. Find the smallest primest number.
解析
- [ 10 ] A positive integer is called primer if it has a prime number of distinct prime factors. A positive integer is called primest if it has a primer number of distinct primer factors. Find the smallest primest number. Proposed by: Yuan Yao Answer: 72 We claim the answer is 72, as it has 6 primer factors: 6 , 12 , 24 , 18 , 36 , 72, and 6 is a primer. We now prove that there is no smaller primer. Suppose there were a smaller primer r < 72. We do casework on the number of distinct prime factors of r . • r has 4 distinct prime factors. Then r 2 · 3 · 5 · 7 = 210, which is larger than 72. • r has 3 distinct prime factors. If each of these factors has multiplicity 1, i.e r = pqs for distinct primes p, q, s , then r has precisely 4 primer factors: pq, qs, sp, pqs , and 4 is not a primer. Thus, 2 r contains at least one factor of multiplicity at least 2. If r is p qs for distinct primes p, q, s , 2 2 2 then r has 7 distinct primer factors: pq, qs, sp, pqs, p q, sp , p qs , and 7 is not a primer. Thus, if a b c 3 r = p q s , a + b + c 5, and r 2 · 3 · 5 = 120, which is 72. a b • r has 2 distinct prime factors. If r = p q , for distinct primts p, q , then r ’s primer factors are i j precisely its divisors of the form p q , where 1 i a and 1 j b , meaning that it has ab 3 2 primer factors. Thus, ab is a primer, meaning that ab 6. Thus r 2 · 3 = 72, where the other possibilities can be ruled out through easy casework. • r has 1 distinct prime factor. Then it doesn’t have any primer factors, and thus cannot possibly have a primer number of them. We conclude that 72 is the smallest primer number.