HMMT February

We claim that $44,56,72$ are the only good numbers. It is easy to check that these numbers work. Now we prove none others work. First, remark that as $n=1,2$ fail so we have $\varphi(n)$ is even, thus $n$ is even. This gives us $\varphi(n) \leq n / 2$. Now remark that $\tau(n)<2 \sqrt{n}$, so it follows we need $n / 2+8 \sqrt{n}>$ $n \Longrightarrow n \leq 256$. This gives us a preliminary bound. Note that in addition we have $8 \tau(n)>n$. Now, it is easy to see that powers of 2 fail. Thus let $n=2^{a} p_{1}^{b}$ where $p_{1}$ is an odd prime. From $8 \tau(n)>n$ we get $8(a+1)(b+1)>2^{a} p_{1}^{b} \geq 2^{a} 3^{b}$ from which we get that $(a, b)$ is one of $$(1,1),(1,2),(1,3),(2,1),(2,2),(3,1),(3,2),(4,1)$$ Remark that $p_{1} \leq \sqrt**{\frac{8(a+1)(b+1)}{2^{a}}}$. From this we can perform some casework: - If $a=1, b=1$ then $p_{1}-1+16=2 p_{1}$ but then $p=15$, absurd. - If $a=1, b=2$ then we have $p_{1} \leq 5$ which is obviously impossible. - If $a=1, b=3$ then $p_{1} \leq 4$ which is impossible. - If $a=2, b=1$ then $p_{1} \leq 12$ and it is easy to check that $p_{1}=11$ and thus $n=44$ is the only solution. - If $a=2, b=2$ then $p_{1} \leq 4$ which is impossible. - If $a=3, b=1$ then $p_{1} \leq 8$ and only $p_{1}=7$ or $n=56$ works. - If $a=3, b=2$ then $p_{1} \leq 3$ and $p_{1}=3, n=72$ works. - If $a=4, b=1$ then $p_{1} \leq 1$ which is absurd. Now suppose $n$ is the product of 3 distinct primes, so $n=2^{a} p_{1}^{b} p_{2}^{c}$ so we have $8(a+1)(b+1)(c+1)>$ $2^{a} 3^{b} 5^{c}$ then we must have $(a, b, c)$ equal to one of $$(1,1,1),(1,2,1),(2,1,1),(3,1,1)$$ Again, we can do some casework: - If $a=b=c=1$ then $8 \tau(n)=64>2 p_{1} p_{2}$ but then $p_{1}=3, p_{2}=5$ or $p_{1}=3, p_{2}=7$ is forced neither of which work. - If $a=1, b=2, c=1$ then $8 \tau(n)=96>2 p_{1}^{2} p_{2}$ but then $p_{1}=3, p_{2}=5$ is forced which does not work. - If $a=2, b=1, c=1$ then $8 \tau(n)=96>4 p_{1} p_{2}$ forces $p_{1}=3, p_{2}=5$ or $p_{1}=3, p_{2}=7$ neither of which work. - If $a=3, b=1, c=1$ then $8 \tau(n)=108>8 p_{1} p_{2}$ which has no solutions for $p_{1}, p_{2}$. Finally, take the case where $n$ is the product of at least 4 distinct primes. But then $n \geq 2 \cdot 3 \cdot 5 \cdot 7=210$ and as $2 \cdot 3 \cdot 5 \cdot 11>256$, it suffices to check only the case of 210 . But 210 clearly fails, so it follows that $44,56,72$ are the only good numbers so we are done.