Let $\tau (n)=k$ $d_1,d_2,d_3,\ldots,d_{k-2},d_{k-1},d_k$ - divisors of $n$ ${{d_k={n\over d_1},d_{k-1}={n\over d_2}},d_{k-2}={n\over d_3}},\ldots,d_3={n\over d_{k-2}},d_2={n\over d_{k-1}},d_1={n\over d_k}$ So if we are looking on the divisors of $n^2$ from the greatest one to the least one we get: $l_1,l_2,l_3,\ldots,l_{k-2},l_{k-1},l_k$ - divisors of $n^2$ $l_1={{n^2}\over d_1},l_2={{n^2}\over d_2},l_3={{n^2}\over d_3},\ldots,l_k={{n^2}\over d_k},\ldots$ $l_k={{n^2}\over d_k}=n$ So all other divisors of $n^2$ are smaller than $n$ so they actually divisors of $n$. From here we get: $\tau ({n^2})=2k-1$ $m={\tau ({n^2})\over \tau (n)}={{2k-1}\over k}$ $km=2k-1$ $k(2-m)=1$ The only solution in positive integers is: $k=1,m=1$ So $m={\tau ({n^2})\over \tau (n)}$ only when $m=1,n=1$

pavel25 wrote: So all other divisors of $n^2$ are smaller than $n$ so they actually divisors of $n$. I don't think so pavel25, try compare with $n=2^5\times3^2$ and $2^6\times3$ I know two sols of it and both seems boring!

pavel25 wrote: Let $\tau (n)=k$ $d_1,d_2,d_3,\ldots,d_{k-2},d_{k-1},d_k$ - divisors of $n$ ${{d_k={n\over d_1},d_{k-1}={n\over d_2}},d_{k-2}={n\over d_3}},\ldots,d_3={n\over d_{k-2}},d_2={n\over d_{k-1}},d_1={n\over d_k}$ So if we are looking on the divisors of $n^2$ from the greatest one to the least one we get: $l_1,l_2,l_3,\ldots,l_{k-2},l_{k-1},l_k$ - divisors of $n^2$ $l_1={{n^2}\over d_1},l_2={{n^2}\over d_2},l_3={{n^2}\over d_3},\ldots,l_k={{n^2}\over d_k},\ldots$ $l_k={{n^2}\over d_k}=n$ So all other divisors of $n^2$ are smaller than $n$ so they actually divisors of $n$. From here we get: $\tau ({n^2})=2k-1$ $m={\tau ({n^2})\over \tau (n)}={{2k-1}\over k}$ $km=2k-1$ $k(2-m)=1$ The only solution in positive integers is: $k=1,m=1$ So $m={\tau ({n^2})\over \tau (n)}$ only when $m=1,n=1$ Why you have taken this as ${{d_k={n\over d_1},d_{k-1}={n\over d_2}},d_{k-2}={n\over d_3}},\ldots,d_3={n\over d_{k-2}},d_2={n\over d_{k-1}},d_1={n\over d_k}$ or there is any rule in such situation s=can you explain it. Really I can not still why you have used as sequence. Abdurashid

Yes, this is a very useful method also for example you can see an imo 2002 if i remember correctly i will check and say later. Explanation : we know that $d_1,d_2,\dots, d_k$ are positive divisors of $n$. Then can't we say that $n=d_1\times d_k=d_2\times d_{k-1}=d_3\times d_{k-2}=\dots$ please try to understand it might be very easy. ex: let n be 12 then we have ${1,2,3,4,6,12}$ as a postitive divisors of n, right ? Then we can say that $1\times 12=12=2\times 6=4\times 3$, now it is yes? davron

your solution above is obviously wrong. answer is: every odd m. you use well-known equality if $n = \prod p_{i}^{\alpha_{i}}$, then $d(n) = \prod (\alpha_{i}+1)$ then by induction we prove that every odd m can be represented as $\frac{\prod (2\alpha_{i}+1)}{\prod (\alpha_{i}+1)}$

Let $t(n)=\frac{\tau(n^{2})}{\tau(n)}$, then t(n) is multiplicative (if $n=n_{1}n_{2}, \ (n_{1},n_{2})=1$, then $t(n)=t(n_{1})t(n_{2})$). Because $\tau(n^{2})$ is odd, if $t(n)$ integer, then $n=m^{2}$ and $t(n)$ is odd. Let $n=p_{1}^{2k}p_{2}^{4k}...p_{s}^{2^{s}k}$, then $t(n)=\frac{2^{s}2k+1}{2k+1}=2^{s}-\frac{2^{s}-1}{2k+1}$. Let $S=\{m|exist \ n: \ m=t(n)\}$ is multiplicative ($m_{1}\in S, \ m_{2}\in S \Longrightarrow m_{1}m_{2}\in S$) subset of odd numbers. Let $m(s,d)=2^{s}-d, \ d|2^{s}-1, d<2^{s}-1$, then $m(s,d)\in S$, because $m(s,d)=t(n), n=p_{1}^{2k}...p_{s}^{2^{s}2k}$, were $k=\frac{2^{s}-1-d}{2d}$. For example $m(2,1)=3,m(3,1)=7,m(4,5)=11,m(4,3)=13,m(4,1)=15$. If $m\in S$ then $2^{s}m-(2^{s}-1)\in S \ \forall s\in N$, because $2^{s}(m-1)+1=t(np_{1}^{m-1}p_{2}^{2(m-1)}...p_{s-1}^{2^{s-1}(m-1)}), \ (n,\prod_{i}p_{i})=1, t(n)=m$. Therefore $5=2*3-1\in S$. I think all odd numbers belongs to S.

Let $S$ be the set of all integers $m$ representable in the form $\frac{\tau(n^2)}{\tau(n)}$. I claim that $S$ is the set of all positive odd integers. First, it is clear that $1 \in S$, as $\frac{\tau(1^2)}{\tau(1)} = 1 \in S$. If $m \in S$, then $m$ is expressible in the form $\frac{(2e_1 + 1)(2e_2 + 1) \ldots (2e_n + 1)}{(e_1 + 1)(e_2 + 1) \ldots (e_n + 1)}$. Since the numerator of this fraction is odd, $m$ must be odd. We now claim that every positive odd integer $m$ greater than 1 can be expressed as a product of (not necessarily distinct) numbers of the form $\frac{4a+1}{2a+1} =\frac{2(2a) + 1}{(2a) + 1}$, then $m = \frac{\tau(\prod p_i^{4a_i})}{\tau(\prod p_i^{2a_i})}$, where $p_i$ is the $i$th prime, which implies that $m \in S$. (It also follows that $m, n \in S$ implies that $mn \in S$.) We shall prove our claim with strong induction. Our base case, $m = 3$ follows from $3 = \frac{5}{3} \cdot \frac{9}{5}$. Now, let $m$ be any odd integer larger than 3, and suppose that all odd integers less than $p$ lie in $S$. Let $p$ be congruent to $2^{b-1} - 1$ modulo $2^b$, for some positive integer $b \geq 2$; then $p = 2^b x + 2^{b-1} - 1$ for some nonnegative integer $x$. If $b = 2$, then $p \equiv 1 \pmod{4}$, so $p = \frac{4x+1}{2x+1} \cdot (2x+1)$, which lies in $S$ since $\frac{4x+1}{2x+1} \in S$ and $2x+1 \in S$ by our inductive hypothesis. If $b > 2$, we shall define the sequences $a_0 = 3 \cdot 2^b$, and $a_{i+1} = \frac{3a_{i+1}}{2}$, and $c_0 = 3 \cdot (2^{b-1} - 1)$ and $c_{i+1} = \frac{3c_i + 3}{2}.$ It is clear that $a_k, c_k$ are all positive integers when $0 \leq k \leq b$, $a_b = 4 \cdot 3^b$, $c_b = 2 \cdot 3^b - 1$, $\lfloor \frac{a_kx + c_k}{2} \rfloor = \frac{a_{k+1}x + c_{k+1}}{3}$ when $0 \leq k \leq b-1$. $a_kx + c_k \equiv 1 \pmod{4}$ when $0 \leq k \leq b$. It follows from the above that each of the numbers $\frac{a_i x + c_i}{\frac{a_{i+1}x + c_{i+1}}{3}}$ for $0 \leq i \leq b-1$ and $\frac{a_b x + c_b}{2 \cdot 3^b x + 3^b}$ are of the form $\frac{4y + 1}{2y + 1}$. Hence, the product $\frac{a_0x + c_0}{\frac{a_1x + c_1}{3}} \cdot \frac{a_1x + c_1}{\frac{a_2x + c_2}{3}} \cdot \ldots \cdot \frac{a_b x + c_b}{2 \cdot 3^b x + 3^b} = \frac{a_0 x + b_0}{3(2x + 1)} = \frac{2^bx + 2^{b-1} - 1}{2x + 1} \in S$. But by our inductive hypothesis, $2x + 1 \in S$ as well, so $2^bx + 2^{b-1} - 1 \in S$, which completes our proof.

I came across that problem yesterday and after I've solved it, I saw the solutions and got confused that all the solutions I've seen where much harder. Maybe my solution is wrong, but anyway here it is: We will prove that each odd positive integer, greater than 1, can be represented as $\frac{d(n^2)}{d(n)}$, for some positive integer $n$. It's well known fact that the number of positive divisors of $P_{1}^{a_{1}}P_{2}^{a_{2}} . . . P_{k}^{a_{k}}$ is equal to $(a_{1}+1)(a_{2}+1) . . . (a_{n}+1)$. So we have to prove that for each odd positive integer $A$ there exist such finite sequence ${a_{i}, 1\leq{i}\leq{n}}$ that $\frac{(2a_{1}+1)(2a_{2}+1)...(2a_{n}+1)}{(a_{1}+1)(a_{2}+1)...(a_{n}+1)}$ is equal to $A$. Let $S$ be the set containing all such numbers $A$. Easy to note that each element of $s$ is an odd integer. First, we show that if $x$ and $y$ both belong to $S$, than their product $xy$ also belong to $S$. Take $a_{i}, 1\leq{i}\leq{m}$ and $b_{j}, 1\leq{j}\leq{k}$ such that $x= \frac {(2a_{1}+1)...(2a_{m}+1)}{(a_{1}+1)...(a_{m}+1)}$ and $y=\frac{(2b_{1}+1)...(2b_{k}+1)}{(b_{1}+1)...(b_{k}+1)}$. It means that $$xy=\frac{(2a_{1}+1)...(2a_{m}+1)(2b_{1}+1)...(2b_{k}+1)}{(a_{1}+1)...(a_{m}+1)(b_{1}+1)...(b_{k}+1)}$$ . It follows that $xy$ is in $S$, as desired. It means that for any two $x,y$ in $S$, $xy$ is also in $S$. (1) So, if we manage to prove that each odd prime number belongs to $S$, than it will follow that each odd number is contained in $S$, which we need to prove. Apply strong induction and prove the following conjecture: If $3=p_{1}<p_{2}<...<p{n}$ are all in $S$, where $p_{i}$-s are first $n$ primes, starting from $3$, than also $p_{n+1}$ belongs to $S$, where $p_{n+1}$ is minimal prime number, greater than $p_{n}$. We have a basis, since $N=2^{4}3^{2}$ imply $\frac{d(n^{2})}{d(n)}=3$ and hence, $3$ is in $S$. Assume now for $3=p_{1}<...<p_{n}$. Than, from (1), each number, whose factorization into primes contains only numbers from ${p_{1},...,p_{n}}$, is contained in $S$. Consider now $L=\frac{p_{n+1}-1}{2}$. Obviously, $L$ is a positive integer and $L+1<p_{n+1}$. So, factorization of $L+1$ into primes is of the form $p_{1}^{x_{1}}...p_{n}^{x_{n}}$, where each $x_{i}$ is a nonnegative integer. By assumption, $L+1$ is in $S$. It means that $2L+1=(L+1) \frac{2L+1}{L+1}$ is in $S$, but $2L+1=p_{n+1}$, completing the proof of our conjecture. So, each odd prime is contained in $S$ and by (1), each odd positive integer is contained in $S$, except for $1$. (Easy to prove).

lasha wrote: Consider now $L=\frac{p_{n+1}-1}{2}$. Obviously, $L$ is a positive integer and $L+1<p_{n+1}$. So, factorization of $L+1$ into primes is of the form $p_{1}^{x_{1}}...p_{n}^{x_{n}}$, where each $x_{i}$ is a nonnegative integer. By assumption, $L+1$ is in $S$. It means that $2L+1=(L+1) \frac{2L+1}{L+1}$ is in $S$, but $2L+1=p_{n+1}$, completing the proof of our conjecture. So, each odd prime is contained in $S$ and by (1), each odd positive integer is contained in $S$, except for $1$. (Easy to prove). I don't particularly understand the bolded part. If $4 | p - 3$, can't $L + 1$ be even?

I hope my solution is correct... this seemed too easy for an IMO 3/6. Call an integer good if there exists a positive integer n such that $\frac{\tau (n^{2})}{\tau (n)}=m$. I claim that all odd positive integers are good. First, any good integer must be expressible in the form $\dfrac {(2a_1 + 1)(2a_2 + 1) \cdots (2a_n + 1)} {(a_1 + 1) (a_2 + 1) \cdots (a_n + 1)}$. Since the numerator is odd, a good integer cannot be an even integer. The case $m = 1$ is obvious. Now we induct to show that all odds are good. The base case $m = 3$ can be expressed as $\dfrac {5} {3} \cdot \dfrac {9} {5}$. Assume that all odds less than an odd number $k$ are good. Case 1: $k \equiv 1 \bmod 4$. Then we take $k = \dfrac {k} {\dfrac {k + 1} {2}} \cdot \dfrac {k+ 1} {2}$. Since $\dfrac {k + 1} {2}$ is odd and less than $k$, it's good. Case 2: $k \equiv 3 \bmod 4$. Let $k = x \cdot 2^a - 1$, where $x$ is odd. Let $r = k(2^a - 1) = 2^{2a} \cdot k - 2^a \cdot (1 + k) + 1$, and let $g(b) = \dfrac {b + 1} {2}$ for all integers $b$. Then we have $\dfrac {b} {g(b)} \cdot \dfrac {g(b)} {g^2 (b)} \cdot ... \cdot \dfrac {g^{a-1} (b)} {g^a (b)} = \dfrac {(2^a \cdot x - 1)(2^a - 1)} {(x) (2^a - 1)}$. Since $x$ is odd, $x$ is good, so $\dfrac {b} {g(b)} \cdot \dfrac {g(b)} {g^2 (b)} \cdot ... \cdot \dfrac {g^{a-1} (b)} {g^a (b)} \cdot x = k$ is also good.

@cwein3 Your case of $k \equiv 1 \pmod{4}$ is correct. However, I don't understand your case of $k \equiv 3 \pmod{4}$, what is $b$? And what does $g^a(b)$ mean? It normally means $g(b)^a$, but it appears it means $g(g(g(...b))...)$ in how you are using it. Can you clarify on these two problems? Then maybe I can understand your proof

cwein3 wrote: Case 2: $k \equiv 3 \bmod 4$. Let $k = x \cdot 2^a - 1$, where $x$ is odd. Let $b = k(2^a - 1) = 2^{2a} \cdot x - 2^a \cdot (1 + x) + 1$, and let $g(b) = \dfrac {b + 1} {2}$ for all integers $b$. Then we have $\dfrac {b} {g(b)} \cdot \dfrac {g(b)} {g^2 (b)} \cdot ... \cdot \dfrac {g^{a-1} (b)} {g^a (b)} = \dfrac {(2^a \cdot x - 1)(2^a - 1)} {(x) (2^a - 1)}$. Since $x$ is odd, $x$ is good, so $\dfrac {b} {g(b)} \cdot \dfrac {g(b)} {g^2 (b)} \cdot ... \cdot \dfrac {g^{a-1} (b)} {g^a (b)} \cdot x = k$ is also good. I think the solution is changed to what he meant and $g^a(b)$ means $g(g( \cdots g(a))))\cdots)$ with $a$ times taken the function $g.$ Also to understand: $g^l (b)= 2^{2a-l}x-2^{a-l}(x+1)+1$ for $l\le a$ meaning, so $g^a(b)=2^a x -x$ and his proof is correct. Nice solution , cwein3!

We can obviously see that it woks for no even number .I will use induction to prove that it works for all odd. As said earlier our target is to prove that any odd number may be represented in the form $\frac{4a_1+1}{2a_1+1}....\frac{4a_r+1}{2a_r+1}$. Assume the result is valid for all $k \le n$ Let $2^x || n+1$ and $n=2^x y-1$ where $y$ is odd . Consider the number $(2^x y-1)(2^x -1)=2^x((2^x-1) y -1)+1$ .Now consider the sequence $A=\frac{2^x((2^x-1) y -1)+1}{2^{x-1}((2^x-1) y -1)+1} .\frac{2^{x-1}((2^x-1) y -1)+1}{2^{x-2}((2^x-1) y -1)+1}....... \frac{2((2^x-1) y -1)+1}{((2^x-1) y -1)+1}$. Which is of the form we required.Above expression is equivalent to $\frac{2^x((2^x-1) y -1)+1}{(2^x-1) y}.=\frac{(2^x y-1)(2^x -1)}{(2^x-1) y}=\frac{(2^x y-1)}{ y}$.Let $[y]$ be the representation of $y$ in the above form .Hence $n$ would be represented in the form $A. [y]$ .Hence the induction is complete

@Rust $5\in S$ is false

orly, $5\not\in S$? what about $n=3600$

The answer is all the odd numbers,when k=1,3, we can just check by hand. Use induction, suppose every odd number not bigger than 2j+1 can be expressed to the requirement. Now we working on 2j+3, if j is even, then there are nothing to prove. If j is odd, we can do conversions on j endless. Finally know that k=1, by our basic inspection, it's true.

Am I missing something? 1998 N6 wrote: For any positive integer $n$, let $\tau (n)$ denote the number of its positive divisors (including 1 and itself). Determine all positive integers $m$ for which there exists a positive integer $n$ such that $\frac{\tau (n^{2})}{\tau (n)}=m$. Fancy way of asking which positive integers greater than $1$ can be written as $\prod^n_{j=1} \frac{2\alpha_j+1}{\alpha_j+1}$ for $\alpha_j \geqslant 1$ and $n \geqslant 1$ integers (for $1=\tau(1^2)/ \tau(1)$ anyway). Clearly, any such number must be odd, as the numerator is odd. Note that $3$ is expressible, simply by $n=2$ and $\alpha_1=1, \alpha_2=4$. Let $m>3$ be the smallest odd number that is not expressible. Suppose $m=2^tx-1$ where $x$ is odd and $x, t \geqslant 1$. Consider $$\frac{2^tx\ell-(2^t-1)}{\ell}=x \frac{2x\ell-1}{x\ell} \cdot \frac{2^2x\ell -3}{2x\ell-1} \dots \cdot \frac{2^tx\ell-(2^t-1)}{2^{t-1}x\ell-(2^{t-1}-1)}$$ and plug $\ell=2^t-1$ to obtain an expression for $m$, since $x<m$ is odd, hence expressible, by assumption, yielding a contradiction! So all odd numbers are expressible. $\blacksquare$

Nice problem! Here's my solution: The answer is all odd $m$. $m=1$ easily follows on taking $n=1$, so from now on assume $m>1$. First let $$n=p_1^{a_1}p_2^{a_2} \dots p_k^{a_k}$$ where the $a_i$'s are positive integers, and $p_i$'s are primes. Then the problem condition translates to $$m=\prod_{i=1}^k \left(\frac{2a_i+1}{a_i+1} \right)$$ Since numerator is odd, so for $m$ to be an integer, the denominator must also be odd (and also $m$ must be an odd integer, so we can effectively ignore even $m$ from now on). This means that $2 \nmid a_i+1$, or equivalently that all $a_i$'s are even. Letting $a_i=2b_i$, we get $$m=\prod_{i=1}^k \left(\frac{4b_i+1}{2b_i+1} \right)$$ Call all integers $m$, which can be written in the fashion above, as expressible numbers. Also, for any expressible number $m$, we let $g(m)$ denote its notation in the above form (note that we have $g(m)=m$ only). We proceed by strong induction to show that all odd $m$ are expressible. For $m=3$, take $b_1=1$ and $b_2=2$. Now, suppose the result is true for all odd numbers less than $m$. We will show that it is true for $m$ as well. If $m \equiv 1 \pmod{4}$, then write $m=4z+1$. Thus, we have $$m=\frac{4z+1}{2z+1} \times g(2z+1)$$ where $2z+1$ is expressible by induction hypothesis. So from now on let $m \not \equiv 3 \pmod{4}$. Suppose there exists some $r \geq 2$ with $m \equiv 2^r-1 \pmod{2^{r+1}}$ (we'll later prove why such an $r$ must exist). Write $m=2^{r+1}x+2^r-1$. Then we have $$(2^r-1)m=4(4^{r-1}(2x+1)-2^{r-1}(x+1))+1 \equiv 1 \pmod{4}$$ This gives $$(2^r-1)m=\frac{4(4^{r-1}(2x+1)-2^{r-1}(x+1))+1}{2(4^{r-1}(2x+1)-2^{r-1}(x+1))+1} \times \frac{4(4^{r-2}(4x+2)-2^{r-2}(x+1))+1}{2(4^{r-2}(4x+2)-2^{r-2}(x+1))+1} \times \dots \times \frac{4(2^{r-1}(2x+1)-(x+1))+1}{2(2^{r-1}(2x+1)-(x+1))+1} \times (2(2^{r-1}(2x+1)-(x+1))+1)$$ Since $2(2^{r-1}(2x+1)-(x+1))+1=(2^r-1)(2x+1)$, so we get that $$m=\frac{4(4^{r-1}(2x+1)-2^{r-1}(x+1))+1}{2(4^{r-1}(2x+1)-2^{r-1}(x+1))+1} \times \frac{4(4^{r-2}(4x+2)-2^{r-2}(x+1))+1}{2(4^{r-2}(4x+2)-2^{r-2}(x+1))+1} \times \dots \times \frac{4(2^{r-1}(2x+1)-(x+1))+1}{2(2^{r-1}(2x+1)-(x+1))+1} \times g(2x+1)$$ where $2x+1$ is expressible by induction hypothesis. Thus, all odd $m$ are expressible if such an $r$ exists. Now we show that such an $r$ exists. Suppose not. Then $m \not \equiv 2^r-1 \pmod{2^{r+1}}$ for any $r \geq 1$ ($r=1$ simply gives $m \equiv 1 \pmod{4}$). This easily converts to the form that $m \not \equiv -1 \pmod{2^a}$ for any $a \geq 1$. But this means that $2 \nmid m+1$, contradicting the fact that $m$ is odd. Thus, such an $r$ exists for all odd $m$. Hence, done. $\blacksquare$ REMARKS: I believe that this was a highly motivated problem, and easily follows if one works according to the direction it gives. The solution above includes the most trivial of details also (like proving $m \equiv 1 \pmod{4}$ seperately, and showing why $r$ exists), and I haven't changed anything coz this is how I discovered the solution. To be completely honest, I had a thinking that maybe just dividing into cases modulo $4$ will work. However, it soon became clear that this wasn't the case, as each case was getting divided into a sub-case. Luckily for us, the whole thing generalized easily (Or maybe the problem was designed in such a way only ).

SnowPanda wrote:

Great solution. Just to prevent possible future confusion, there is a typo in the second fraction in the last big equation, it should be: $$\frac{2(2^ra - a - 1) + 1}{2^ra - a - 1 + 1} \cdot \frac{4(2^ra - a - 1) + 1}{2(2^ra - a - 1)+1} \cdots \frac{2^r(2^ra - a - 1) + 1}{2^{r - 1}(2^ra - a - 1) + 1} = \frac{2^ra - 1}{a}.$$

If $n=\prod p_i^{\alpha_i},$ then $m=\frac{\tau(n^2)}{\tau(n)}=\prod\frac{2\alpha_i+1}{\alpha_i+1}.$ Notice the numerator is always odd, so $m$ is odd. We now claim all odd $m$ work; we proceed by strong induction. Let $m=2^k\ell-1,$ letting $\ell$ be an odd integer less than $m.$ Then $\ell$ is in the form $\prod\frac{2\alpha_i+1}{\alpha_i+1},$ so $$\ell\prod_{i=0}^{k-1}\frac{2\cdot{\color{blue}2^i(2^k\ell-\ell-1)}+1}{{\color{blue}2^i(2^k\ell-\ell-1)}+1}=\ell\cdot\frac{2\cdot 2^{k-1}(2^k\ell-\ell-1)+1}{(2^k\ell-\ell-1)+1}=\ell\cdot\frac{(2^k\ell-1)(2^k-1)}{\ell(2^k-1)}=m$$ is also of the desired form. $\square$

We claim that the answer is all odd positive integers. Note $f(1)=1$, so $1$ is achievable. Let $f(n)=\tfrac{\tau(n^2)}{\tau(n)}$. Let $n=p_1^{e_1}\dots p_k^{e_k}$ be the prime factorization of $n$. Then $\tau(n)=\Pi_{i=1}^k (e_i+1)$ and $\tau(n^2)=\Pi_{i=1}^k (2e_i+1)$. In order for $f(n)$ to be an integer, it is necessary that $\tau(n)$ is odd, since $\tau(n^2)$ is odd. So $f(n)$ is always odd. Note that since $\tau(n)$ is multiplicative, $f(n)$ is also multiplicative. Also, note that $f(p_1^{e_1}\dots p_k^{e_k})=f(p_{k+1}^{e_1}\dots p_{2k}^{e_k})$, in other words, the primes used in the base of the prime factorization of the input "don't matter". So if $f(p_1^{e_1}\dots p_k^{e_k})=m$, and $(p_i)_{i=1}^{\infty}$ is the sequence of primes, then $$f\left(\prod_{j=0}^{\ell-1} \left(\prod_{i=1}^{k} p_{i+jk}^{e_i}\right)\right)=\prod_{j=0}^{\ell-1} f\left(\prod_{i=1}^{k} p_{i+jk}^{e_i}\right)=m^\ell,$$ for any positive integer $\ell$. It follows that if all odd primes are in the range of $f(n)$, then all odd positive integers are in the range of $f(n)$, since we can write every odd positive integer as a product of odd primes. Suppose for contradiction that not all primes are in the range of $f(n)$, and take the least prime $p$ that is not in the range of $f(n)$. Note that $f(2^2 3^4)=3$, so $p>3$. If $p\equiv 1\pmod{4}$ then let $e=\tfrac{p-1}{4}$, so $$f(q^{2e})=\frac{p}{\frac{p-1}{2}+1}=\frac{p}{\frac{p+1}{2}},$$ for any prime $q$. Since $\tfrac{p+1}{2}$ is odd due to $p\equiv 1\pmod{4}$ and $\tfrac{p+1}{2}<p$, there exists an $r$ such that $f(r)=\tfrac{p+1}{2}$, due to minimality of $p$. So $f(q^{2e})f(r)=p$. Since the primes in the prime factorization of $r$ "don't matter", as established earlier, we can make $\gcd(q^{2e},r)=1$, so $f(q^{2e}r)=p$, and thus $p$ must be in the range of $f(n)$, contradiction. If $p\equiv 3\pmod{4}$, then take $e=\tfrac{3p-1}{4}$, so $f(q^{2e})=\tfrac{3p}{(3p+1)/2}$. Note that $\tfrac{3p+1}{2}$ is odd since $p\equiv 3\pmod{4}$. Then taking $d=\tfrac{3p-1}{8}$, we have $f(s^{2d})=\tfrac{(3p+1)/2}{(3p+3)/4}=\tfrac{(3p+1)/2}{3\cdot (p+1)/4}$, for some prime $s$. Note that $\tfrac{p+1}{4}$ is smaller than $p$, so we have some $r$ such that $f(r)=\tfrac{p+1}{4}$. So then $f(s^{2d})f(r)=\tfrac{(3p+1)/2}{3}$, and we can make $\gcd(q^{2e},s^{2d},r)=1$, so $f(s^{2d}r)=\tfrac{(3p+1)/2}{3}$. Then $$f(q^{2e}s^{2d}r)=f(q^{2e})f(s^{2d}r)=\frac{3p}{\frac{3p+1}{2}}\cdot \frac{\frac{3p+1}{2}}{3}=p,$$ so $p$ is achievable. Therefore all odd primes are in the range of $f(n)$, and we are done.

Solved together with, after gatecrashing a groupsolve by mxlcv and mathscrazy We claim all odd numbers work, clearly any such number is odd so it suffices to show a construction for them. Proceed by strong induction with the base case $m = 1$ which works when $n = 1$. Now, if $m+1 = 2^k \cdot \ell$ with $\ell$ odd, then we have $$\frac{(2^k - 1)m}{\frac{(2^k - 1)m + 1}{2}} \cdot \frac{\frac{(2^k - 1)m + 1}{2}}{\frac{(2^k - 1)m+3}{4}} \cdot \frac{\frac{(2^k - 1)m + 3}{4}}{\frac{(2^k - 1)m + 7}{8}} \cdots \frac{\frac{(2^k - 1)m + 2^{k-1} - 1}{2^{k-1}}}{\frac{(2^k - 1)m + 2^k - 1}{2^k}} = \frac{m}{\ell}$$ By induction, since $\ell$ can be represented, we are done.

Let $n=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ for distinct primes $p_1,p_2,\dots,p_k$ and positive integers $e_1,e_2,\dots,e_k.$ Then, we have $$\frac{\tau\left(n^2\right)}{\tau(n)}=\frac{(2e_1+1)(2e_2+1)\dots(2e_k+1)}{(e_1+1)(e_2+1)\dots(e_k+1)}.$$ Since the numerator is odd, the denominator must also be odd, so all $e_i$ are even, and $m$ is odd. It just remains to solve the following equivalent problem: for which odd positive integers $m$ is it possible to find elements that multiply to $m$, not necessarily distinct, from the set $S=\left\{\tfrac{4k+1}{2k+1}\right\}$ where $k$ is a positive integer. Call rational number $m$ good if it satsifies that. Note that (1) $1$ is good by taking no elements at all. An empty product is equal to $1$. $3$ is good by taking $5/3$ and $9/5$. (2) If $m$ and $n$ are good rationals, not necessarily distinct, then $mn$ is good. Take all the elements from the construction for $m$ and then the ones from the one for $n$, and then take the product of them all. (3) If $m$ is a good positive integer, then $2m-1$ is good. In this case, take the elements from the construction for $m$ and add on the element described by $k=\tfrac{m-1}{2}.$ We proceed by strong induction on $m$, for the statement for all odd $m$, $m$ is good. If $m\equiv 1\pmod 4$ then $\tfrac{m+1}{2}$ is an odd positive integer, which must be good. Thus, $2\cdot \tfrac{m+1}{2}-1=m$ is good. $~$ Otherwise, let $m=2^a\cdot b-1$ for $b$ odd. Since $b$ is odd, $b$ must be good, so it suffices to show that $\tfrac{m}{b}$ is good. Indeed, let $c=b(2^a-1)$ then $c$ is odd, so $2c-1\equiv 1\pmod 4.$ Thus, $$\frac{2c-1}{c}\cdot \frac{4c-3}{2c-1}\cdot \dots \cdot \frac{2^a(c)-(2^a-1)}{2^{a-1}(c)-(2^{a-1}-1)}=\frac{2^ac-(2^a-1)}{c}=\frac{m}{b}$$ is good as desired.

Solved with GoodMorning The answer is all odd positive integers. To see that $m$ must be odd, we have $\tau(n^2)$ is odd, so $\frac{\tau(n^2)}{\tau(n)}$ is also odd. It remains to show that all odd numbers work. Since $\tau(n)\mid \tau(n^2)$, $\tau(n)$ is odd, so $n$ must be a perfect square. Write $$n = p_1^{2a_1} p_2 ^{2a_2} \cdots p_l ^{2a_l}$$ for some positive integer $l$, distinct primes $p_1, p_2, \ldots, p_l$, and positive integers $a_1, a_2, \ldots, a_l$. We have $$m = \frac{(4a_1 + 1)(4a_2 + 1)\cdots (4a_l + 1)}{(2a_1 + 1)(2a_2 + 1)\cdots (2a_l + 1)}$$ Note that if we can find $l$ $a_1, a_2,a_3,\ldots, a_l$ such that the expression is equal to $m$, then $m$ is a valid number in the problem. Thus, it suffices to show that all odd positive integers can be expressed as the product of (not necessarily distinct) values in $\left\{\frac{4x+1}{2x+1}\right\}_{x\in \mathbb{N}}$ We do this by induction. The base cases $m=1,3$ work by having no $a_i$ at all, and $\frac{5}{3} \cdot \frac{9}{5}$, respectively. Now fix an odd positive integer $c$. Suppose that all odd positive integers less than $c$ were expressible. We show that $c$ is also expressible. Let $a = \nu_2(c+1)$ and $c = k\cdot 2^{a+1} + 2^a - 1$. Claim: If $f(x) = \frac{x+1}{2}$ for all positive integers $x$, then we have $$f^y(c\cdot (2^a - 1)) = k\cdot 2^{a+1 - y} \cdot (2^a - 1) + 2^{2a - y} - 2^{a+1 - y} + 1$$ for all positive integers $0\le y\le a$. Proof: Induction (base case $y = 0$ is obvious), we see that if $y$ works, then $$\begin{align*} f^{y+1}(c\cdot (2^a - 1)) = \frac{k\cdot 2^{a+1 - y} \cdot (2^a - 1) + 2^{2a - y} - 2^{a+1 - y} + 2}{2} \\ = k\cdot 2^{a+1 - (y+1)} \cdot (2^a - 1) + 2^{2a - (y+1)} - 2^{a+1 - (y+1)} + 1,\\ \end{align*}$$ as desired. So the induction is complete. $\square$ Now notice that $\frac{t}{f(t)} \in \left\{\frac{4x+1}{2x+1}\right\}_{x\in \mathbb{N}}$ for any positive integer $t\equiv 1\pmod 4$. Using the fact that $f^y(c\cdot (2^a - 1) ) \equiv 1\pmod 4$ for $0\le y\le a-1$, we get that the number $$\frac{d}{f(d)} \cdot \frac{f(d)}{f^2(d)} \cdots \frac{f^{a-1}(d)}{f^a(d)} = \frac{d}{f^a(d)} = \frac{k\cdot 2^{a+1} \cdot (2^a - 1) + (2^a - 1)^2}{(2^a - 1)(2k + 1)}$$ is expressible. Since $2k + 1$ is expressible, we can multiply by $2k + 1$ and get that $$\frac{k\cdot 2^{a+1} \cdot (2^a - 1) + (2^a - 1)^2}{2^a - 1} = c$$ is also expressible, which completes the induction. Therefore, all odds are expressible, so we are done.

Shoot... This problem I had to ACTIVELY try and reassure myself that I was not to stray away from hard problems in lieu of improving... Note that $\frac{\tau\left(n^2\right)}{\tau(n)}=\prod\frac{2e_i+1}{e_i+1}$ (where $e_i$ are exponents in the factorization of n). From here, it's obvious evens don't work, all exponents are even, and we prove all odds work by proving you can find elements from the set $S=\left\{\frac{4k+1}{2k+1}\right\}$ (repeating allowed) that multiply to m; call these numbers obtainable. We proceed by induction, manually computing base cases n=1,3; observe that if m is obtainable then 2m-1 is obtainable by also using $\frac{m-1}2$ (1), and if a and b are obtainable then ab is obtainable by combining sets (2); assume henceforth the inductive hypotheses for $k\le m$. In this way, the next minimal number $m_0>m,m_0\equiv1\pmod4$ is obtainable by using (1) and inductive hypothesis. Furthermore, if $m=2^ij-1:i\ge2$ is 3 mod 4, by inductive hypothesis j is obtainable, so by (2) it suffices to prove $\frac mj$ is obtainable. But this is evident, as $\frac{2(2^ij-j)-1}{2^ij-j}\frac{4(2^ij-j)-3}{2(2^ij-j)-1}\dots\frac{2^i(2^ij-j)-(2^i-1)}{2^{i-1}(2^ij-j)-(2^{i-1}-1)}=\frac mj$ is indeed obtained. Motivational remark. The last construction is not so easy to obtain; the way I got it was by solving for a general form in the telescope, if the first term was c, that it would be of the form $\frac{2^dc-(2^d-1)}{c}=\frac mj$ for arbitrary d (i hope i didn't get this wrong, someone pls check), and from there it was easy.

The answer is all odd $m$. Clearly $m=1$ works by taking $n=1$, so suppose $m>1$. Clearly we are being asked to find the positive integers which can be expressed as the product of not necessarily distinct numbers of the form $\tfrac{2e-1}{e}$ for positive integers $e$. Call rational numbers which can be written like this good. Obviously products of good numbers are also good. Observe that each fraction always have nonpositive $\nu_2$, hence $m$ must be odd. We now show that every odd prime $p$ is good, which will finish the problem. To do this, we induct on $p$. Let $\nu_2(k+1)=k>0$, so $p \equiv 2^k-1 \pmod{2^{k+1}}$. Then we consider the identity $$\frac{(2^k-1)p}{\frac{(2^k-1)p+1}{2}}\cdot \frac{\frac{(2^k-1)p+1}{2}}{\frac{(2^k-1)p+3}{4}}\cdots\frac{\frac{(2^k-1)p+(2^{k-1}-1)}{2^{k-1}}}{\frac{(2^k-1)p+(2^k-1)}{2^k}}=\frac{(2^k-1)p}{\frac{(2^k-1)(p+1)}{2^k}}=\frac{2^k}{p+1}p,$$ hence $\tfrac{p+1}{2^k}p$ is good. On the other hand, by the definition of $k$, $\tfrac{p+1}{2^k}$ is odd and strictly less than $k$, hence by inductive hypothesis it is good as well. Thus $p$ is good: done. $\blacksquare$ Remark (motivation): I figured out how to get $1 \pmod{4}$ primes by using $\tfrac{p+1}{2}$, but for $3 \pmod{4}$ primes this doesn't work. When I tried $p=11,19$, I found that we could "start" from $3p$, but again this doesn't work for $p \equiv 7 \pmod{8}$. But for this case "starting" from $7p$ sometimes works. At this point we figure out the solution. Remark: Oh using primes doesn't actually matter and we can generally work with odds instead. But the solution isn't actually made any harder if we only think about primes (nor is it made any easier)