Maths Olympiad Prep

Track / Stage 4 / 259 of 340 #999 of 2444

Problem 999

AMC 12 late, AIME early
Number theory Difficulty 4.9 Find the answer HMMT November

For a positive integer nn, let, τ(n)\tau(n) be the number of positive integer divisors of nn. How many integers 1n501 \leq n \leq 50 are there such that τ(τ(n))\tau(\tau(n)) is odd?

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

Next problem →

Official solution

Note that τ(n)\tau(n) is odd if and only if nn is a perfect square. Thus, it suffices to find the number of integers nn in the given range such that τ(n)=k2\tau(n)=k^{2} for some positive integer kk. If k=1k=1, then we obtain n=1n=1 as our only solution. If k=2k=2, we see that nn is either in the form pqp q or p3p^{3}, where pp and qq are distinct primes. The first subcase gives 8+4+1=138+4+1=13 solutions, while the second subcase gives 2 solutions. k=3k=3 implies that nn is a perfect square, and it is easy to see that only 62=366^{2}=36 works. Finally, k4k \geq 4 implies that nn is greater than 50, so we've exhausted all possible cases. Our final answer is 1+13+2+1=171+13+2+1=17.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.