Maths Olympiad Prep

Library / /163 of 348

Number theory Difficulty 4.9 AIME Find the answer

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. Spacing and $ signs are ignored.

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.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.