the wording is not exact, I will update it once the website uploads the problems (the questions are collected alongside the solutions)

Standard tripling trick: Note that $f(d(n))=d(f(n))$ so $d(f(p))=f(2)$ forall primes $p$. Since $2 \le d(f(2))=f(2)$ we get $f(2)=2$ so $f(p)$ has exactly two divisors, hence, it is a prime. Here we used the fact that $$n=p_1^{\alpha_1}\cdot \dots \cdot p_k^{\alpha_k} \ge (\alpha_1+1)\cdot \dots \cdot (\alpha_k+1) =d(n),$$with equality only at $n=1,2$.

I think you might have missed dealing with $f(2)=1$, unless I misunderstood something. A way to prove that $f(2)\neq 1$: Assume for contradiction that it is true, then $f(f(2))=f(1)=2$ $f(f(3))=2\iff \tau{(f(3))}=f(2)=1\iff f(3)=1$. $f(f(25))=3\iff \tau{(f(25))}=1\iff f(25)=1 \iff 3=f(f(25))=f(1)=2$ contradiction!

Let $d(n)$ denote the number of divisors of $n$. First note that $d(n)=n$ iff $n$ is divisible by all positive integers at most $n$, which is only true when $n\le2$. We have that $f(d(n))=f(f(f(n))=d(f(n))$ for all positive integers $n$. Setting $n\le 2$, we have that $f(n)=f(d(n))=d(f(n))\implies f(n)\le 2$. Setting $n=p$, a prime, we have that $f(2)=f(d(2))=d(f(p))$. If $f(1)=f(2)=1$, then $f(f(2))=1\ne d(2)$, a contradiction. If $f(1)=2$ and $f(2)=1$, then $d(f(p))=f(2)=1\implies f(p)=1$ for all primes $p$. We then have that $1=f(3)=f(d(p^2))=d(f(p^2))\implies f(p^2)=1\implies 3=d(p^2)=f(f(p^2))=2$, a contradiction, If $f(2)=2$, then $d(f(p))=2$, from which the conclusion follows.

InCtrl wrote: I think you might have missed dealing with $f(2)=1$, unless I misunderstood something. A way to prove that $f(2)\neq 1$: Assume for contradiction that it is true, then $f(f(2))=f(1)=2$ $f(f(3))=2\iff \tau{(f(3))}=f(2)=1\iff f(3) = 1$. $f(f(25))=3\iff \tau{(f(25))}=1\iff f(25)=1 \iff 3=f(f(25))=f(1)=2$ contradiction! Here's the other half of the solution (quite literally): Let $p_i$ be the $i^{th}$ prime and the set $K = (k_1, k_2, ... )$ be defined with the formula $f(p_i) = k_i$ Tripling the involution gives us $f(f(k_i)) = k_1$. Specifically, $f(f(k_1) = \tau(k_1) = k_1$. Since $\tau(n) < n$ for n > 2, $k_1 = 1$ or 2. Case 1: $k_1$ = 2. Then $f(f(k_i)) = k_1 = 2 \iff \tau(k_i) = 2 \iff k_i$ is a prime. So $f(p) = k_i$ is a prime for all p, which satisfies the problem statement. Case2: $k_1$ = 1. This case implies that f(p) = 1, and f(1) = 2. Like InCtrl said, we can triple the involution once more to obtain a contradiction for f(1) = 2. So that rules out this case and leaves us with case 1, which is the answer.

Another property of $f$: If $p,q$ are primes then there exist primes $r,s$ such that $f(p^{q-1})=r^{s-1}$.

Use that when $\tau$ is repeated suffisently $\tau \circ \tau \circ ... \tau (p)$ will eventually become constant (equals $2$) which yields $f (2)=2$. Where $\tau (n) $ is the number of positive divisors of $n $

Delray wrote:

How did you get contradiction for $f(2)=1$. I've found a proof but I want to see yours also.

Let p be a prime number. f(p) is prime iff f(f(f(p)))=f(2)=2. f(f(f(2)))=f(2) (f(2) is equal to its number of divisors, so it can be either 1 or 2). Assume that f(2)=1 (which implies 2=f(f(2))=f(1). For every prime p, we have T(f(p)=f(f(f(p)))=f(2)=1). Therefore f(p)=1 for every p. Consider the numbers n=p^(q-1) where p and q are primes. T(f(n))=f(f(f(n)))=f(q)=1 ===> f(n)=1 ====> q=f(f(n))=f(1)=2. Contradiction for q=/=2, so f(2) must be 2 as desired.

InCtrl wrote: Define a function $f(n)$ from the positive integers to the positive integers such that $f(f(n))$ is the number of positive integer divisors of $n$. Prove that if $p$ is a prime, then $f(p)$ is prime. Solution: We have $$f(f(n))=\tau(n)$$for all $n\in \mathbb{N}$, where $\tau(n)$ denotes the number of positive divisors of $n$. Set $n=p$, a prime, and we get, $$f(f(p))=\tau(p)=2$$$$\Longrightarrow f(f(f(p)))=f(2)$$$$\Longrightarrow \tau(f(p))=f(2)$$Now if we set $p=2$, we get $$\tau(f(2))=f(2)$$But we know that $\tau(m)=m$ (where $m\in\mathbb{Z^+}$) iff $m=2$ or $1$. Suppose $f(2)=1$ Then we will have $$f(p)=1$$for all prime $p$. So $f(3)=1$. We know that $$f(f(9))=3\Longrightarrow \tau(f(9))=f(3)=1\Longrightarrow f(9)=1\Longrightarrow f(f(9))=f(1)=2$$A contradiction! So, $\boxed{f(2)=2}$. Hence we deduce that $$\tau(f(p))=2$$for all prime $p$. But we also know that $f(m)=2$ (where $m\in\mathbb{Z^+}$) only if $m$ is a prime. Thus we conclude that $f(p)$ is a prime for all prime $p$. $\blacksquare$ @below Thanks for pointing out the flaw in my solution. Hopefully it is correct now.

hansu wrote: InCtrl wrote: Define a function $f(n)$ from the positive integers to the positive integers such that $f(f(n))$ is the number of positive integer divisors of $n$. Prove that if $p$ is a prime, then $f(p)$ is prime. Solution: We have $$f(f(n))=\tau(n)$$for all $n\in \mathbb{N}$, where $\tau(n)$ denotes the number of positive divisors of $n$. Set $n=p$, a prime, and we get, $$f(f(p))=\tau(p)=2$$$$\Longrightarrow f(f(f(p)))=f(2)$$$$\Longrightarrow \tau(f(p))=f(2)$$Now if we set $p=2$, we get $$\tau(f(2))=f(2)$$But we know that $\tau(m)=m$ (where $m\in\mathbb{Z^+}$) iff $m=2$. So, $\boxed{f(2)=2}$. Hence we deduce that $$\tau(f(p))=2$$for all prime $p$. But we also know that $f(m)=2$ (where $m\in\mathbb{Z^+}$) only if $m$ is a prime. Thus we conclude that $f(p)$ is a prime for all prime $p$. $\blacksquare$ $\tau(m)=m$ $\Longleftrightarrow$ $m=1$ or $m=2$

You will have to consider a case taking $f(2)=1$

Consider $f(f(2))$; we obviously can have $f(2)=2$, and if $f(2)=k$ for $k\neq 2$, then we need $f(k)=2$ and $f(f(k))=k$ which can only hold when $k=1$. Now note that $f(f(f(p)))=f(\tau (p))=f(2)=\tau (f(p))$; if $f(2)=2$ this yields that $f(p)$ has 2 divisors which makes it a prime. If $f(2)=1$, we know that $f(p)=1$ and hence $f(f(f(4)))=f(\tau (4))=f(3)=1=\tau (f(4))$ which gives $f(4)=1$ as well, though that also means that $f(f(4))=f(1)=2=\tau (4)=3$ which is a contradiction.

We will proceed by contradiction. First assume $f(p)=c$ for some composite $c$. We know $f(f(p))=f(c)=2$. Now, let $f(f(c))=d$ where $d\geq 3$. Substituting $f(c)=2$, we get $f(2)=d$. Taking $f$ of both sides, $f(f(2))=f(d)=2$. Taking $f$ again, we have $f(f(d))=f(2)=d$, which is a contradiction since for $d \geq 3$, $d$ cannot have $d$ factors. Now assume $f(p)=1$. We have $f(f(p))=f(1)=2$. Now consider any composite $c$ with a prime number $p>2$ of positive divisors. We have $f(f(c))=p$. This means that $f(f(f(c)))=f(p)=1.$ Looking at $f(f(f(c)))=1$, we see that $f(c)$ must have 1 divisor, so $f(c)=1$. Taking $f$ of both sides, $f(f(c))=f(1)=2,$ which is a contradiction since $c$ does not have 2 divisors. Hence, $f(p)$ is prime.

First, a few lemmas about the divisor function, $\tau(n)$, that we will accept without proof. $\textbf{1. }\tau(n)\le2\sqrt n$ $\textbf{2. }\tau(n)=1\Leftrightarrow n=1$ $\textbf{3. }\tau(n)=2\Leftrightarrow n$ is prime Now for the actual proof. Let $P(n)$ be the assertion $f(f(n))=\tau(n)$. $\textbf{4. }\tau(n)=n\Rightarrow n=\{1,2,3\}$ Since $\tau(n)\le2\sqrt n$ and $\tau(n)=n$, so $n\le2\sqrt n$, thus $n\in\{1,2,3,4\}$. If $n=4$ then we get $\tau(4)=4$, contradiction. $\blacksquare$ $\textbf{5. }f(1)=1,f(2)\in\{1,2,3\}$ Simply, $P(1)\Rightarrow f(f(1))=\tau(1)=1$, so $f(1)=1$. $\blacksquare$ We have $f(f(n))=\tau(n)$, so $f(f(f(n)))=f(\tau(n))=\tau(f(n))$. Let the latter equality be $Q(n)$. Thus $Q(p)\Rightarrow f(2)=\tau(f(p))$. In particular, $f(2)=\tau(f(2))$, thus $f(2)\in\{1,2,3\}$. $\blacksquare$ $\textbf{6. }f(2)=2$ Case 1: $f(2)=1$ We have $P(2)\Rightarrow f(f(2))=2$, thus $f(1)=2$, contradiction. Case 2: $f(2)=3$ As before, $f(f(2))=2$, so $f(3)=2$, but $P(3)\Rightarrow f(f(3))=2\Rightarrow f(2)=2$, contradiction. $\blacksquare$ We get $\tau(f(p))=2$, thus $f(p)$ is prime. $\square$

Since $f(f(2)) = 2$ we have $f(f(f(2))) = f(2)$, so $f(2)$ has $f(2)$ divisors. In particular, $f(2) - 1 | f(2)$, so $f(2)\in\{1,2\}$. Case 1: $f(2) = 2$. Then for prime $p$, $f(f(f(p))) = f(2) = 2$, so $f(p)$ has 2 divisors, as desired. Case 2: $f(2) = 1$. Then $f(1) = 2$. For prime $p$, $f(f(f(p))) = f(2) = 1$, so $f(p) = 1$. But then $f(f(f(4))) = f(3) = 1$, so $f(4) = 1$, implying $f(1) = f(f(4)) = 3$, a contradiction.

We have $f(f(2))=2$, so $f(f(f(2)))=f(2)$. Thus, $f(2)$ has $f(2)$ divisors, which implies $f(2)\in \{1,2\}$ because $f(2)-1\mid f(2)$. Case 1: $f(2)=1$. Then we have $f(1)=2$. For primes, $p$, we have $f(f(p))=2$, so $f(f(f(p)))=1\implies f(p)=1$. However $f(f(f(4)))=f(3)=1\implies f(4)=1$ Now $f(f(4))=f(1)=2$, a contradiction. Case 2: $f(2)=2$. For primes $p$, we have $f(f(p))=2$, so $f(f(f(p)))=2$. This implies $f(p)$ has $2$ divisors, as desired.

Note that $f(1)=1$ it follows that $f(2)\neq 1.$ Let $f(x)=2.$ It follows that $\tau (x)\geq x.$ It forces $x=2$ and the claim is obvious.

Let $d(n)$ denote the usual. $f(f(n))=d(n)$ $f(f(f(n)))=f(d(n))$ But $f(f(n))=d(n)$, so $f(f(f(n)))=d(f(n))$ $f(d(n))=d(f(n))$ $f(f(2))=d(2)=2$ $f(f(f(2)))=f(2)=d(f(2))$ $d(n)=n$ for $n=1,2$ $f(2)$ is $1$ or $2$. $f(f(p))=2$ $f(f(f(p)))=f(2)=d(f(p))$ If $f(p)$ is prime, then $d(f(p))=2 \implies f(2)=2$. Consider $f(2)=1$. $f(f(2))=f(1)=2$. $f(f(f(p)))=d(f(p))=f(2)=1$, so $f(p)=1$ Then, $f(f(f(4)))=f(3)=d(f(4))=1$, and $f(4)=1$. But $f(f(4))=d(4)=3$, contradicting $f(f(4))=f(1)=2$. Therefore, $f(2)=2$, and $f(p)=p$.

We begin by the following claim. Claim: $f(2)=2$ Proof: Assume that $f(2)=x$, then \begin{align*} f(x)=2\implies f(f(x))=f(2)\implies f(f(x))=x \end{align*}Since $f(f(x))\leq 2\sqrt{x}$, we have $x\leq 2\sqrt{x}$, thus $x\leq 4$. But $f(f(3))=2$ and $f(f(4))=3$, so the possible values of $x$ are $1$ and $2$ If $f(2)=1$, then $f(1)=2$. So \[f(f(3))=2=f(1)\implies f(3)=1\]Since $f(f(4))=3\implies f(f(f(4)))=f(3)=1$, thus $f(4)=1\implies f(1)=3$. As $f$ is a function, it cannot have 2 maps. So $f(2)\neq 1$, $\blacksquare$ Let $p$ be a prime, then \begin{align*} f(f(p))=2\implies f(f(f(p)))=f(2)=2 \end{align*}So the number of divisors of $f(p)$ is 2. Thus $f(p)$ is a prime.

Notice \[d(f(p))=f^3(p)=f(d(p))=f(2)\quad(*)\]for all primes $p$, so $d(f(2))=f(2)$. Hence, $f(2)=1,2$ and suppose FTSOC that $f(2)=1$. Then, $f(p)=1$ for all primes $p$ so \[d(f(4))=f^3(4)=f(3)=1\]so $3=f(f(4))=f(1)=2,$ a contradiction. Therefore, by $(*)$, we see $d(f(p))=2$ for all primes $p$, as desired. $\square$

Note that $f(f(2)) = 2 \implies f(f(f(2))) = f(2)$, and $f(f(f(2)))$ is the number of positive integer divisors of $f(2)$, so $f(2)$ is the number of positive integer divisors of $f(2)$. If $f(2) - 1 \nmid f(2)$, then we will have at most $f(2) - 1$ divisors of $f(2)$, a contradiction. Hence, $f(2) - 1 \mid f(2) \implies f(2) - 1 \mid 1 \implies f(2) = 1, 2$. Case 1: $f(2) = 2$ We have $f(f(p)) = 2 \implies f(f(f(p))) = f(2) = 2$, and since $f(f(f(p)))$ is just the number of divisors of $f(p)$, $f(p)$ has 2 divisors, which means it's prime and we're done. Case 2: $f(2) = 1$ We have $f(f(f(p))) = f(2) = 1 \implies f(p) = 1$. We have $f(f(p)) = 2 \implies f(1) = 2$. Note that $f(f(4)) = 3 \implies f(f(f(4))) = f(3) = 1 \implies f(4) = 1 \implies f(1) = 3$, a contradiction. So, $f(2) = 2$ and hence, $f(p)$ must be prime.

Let the value of $f(2)$ be $y$ Now $f(f(p))=2$ for any prime $p$(As $p$ has $2$ divisors) So $f(f(2))=2$ $f(y)=2$ $f(f(y))=f(2)=y$ it means $y$ has $y$ divisors which is only possible when $y \leq 2$ Let $f(2)$ be $1$ f Let $x$ be a number such $f(x)=2$ Now $f(f(x))=f(2)=1$ That means $x$ only has one factor and so $x$=1 As $f(f(p))=2$ so $f(p)=1$ Now $f(f(4))=3$ $f(f(f(4)))=1$ that means $f(4)$ has one factor so $f(4)=1$ and thus $f(1)=3$ Contradiction So $f(2)=2$ and $f(f(f(p)))=2$ which means $f(p)$ has two factors and such it is a prime. $\square$

The problem itself is easy to solve, but you may wonder: does a function $f:\mathbb{N}\mapsto\mathbb{N}$ actually exist?($\mathbb{N}$ refers to the set of positive integers, as usual.) We cannot say that, for any function $g:\mathbb{N}\mapsto\mathbb{N}$, there exists a function $f:\mathbb{N}\mapsto\mathbb{N}$ such that $f(f(n))=g(n)$ for all $n$. For example, it is easy to show that there is no function $f:\mathbb{N}\mapsto\mathbb{N}$ such that $f(f(n))=n+1$. So, does a function $f$ satisfying the condition given in the problem actually exist? For anyone who is curious, I will provide a proof that such a function exists, and that we can construct it inductively. So we start by defining $f(1)=1$ and $f(2)=2$. Assume we have defined the values of $f$ for some set $A\subset\mathbb{N}$, so that $f(n)\in A$ for all $n\in A$, and $f(f(n))=\tau{(n)}$ is satisfied for all $n\in A$.($\tau{(n)}$ refers to the number of positive integer divisors of $n$, as usual.) Let $k$ be the smallest positive integer that is not in $A$. Note that $k>2$ because we already defined $f(1)$ and $f(2)$. We will define the value of $f$ for $k$ and some $m>k$ that is not in $A$. Assume we define $f(k)=m$ for some $m>k$. Then we need $f(m)=f(f(k))=\tau{(k)}$ and $\tau{(m)}=f(f(m))=f(\tau{(k)})$. So we will choose $m$ such that $m$ is not in $A$ and $\tau{(m)}=f(\tau{(k)})$. We know that: (1) $f(\tau{(k)})$ has already been defined, because $\tau{(k)}<k$.(This is because $k>2$) (2) $f(\tau{(k)})>1$, because if $f(\tau{(k)})=1$ then $1<\tau{(\tau{(k)})}=f(f(\tau{(k)}))=f(1)=1$, contradiction. Since $f(\tau{(k)})>1$, there exist infinitely many positive integers $m$ such that $\tau{(m)}=f(\tau{(k)})$. We choose one such that $m>k$ and $m$ is not in $A$. We then define $f(k)=m$ and $f(m)=\tau{(k)}$. Now if we look at the set $A'=A\cup\{ k,m\}$, we can see that $f(k)$ and $f(m)$ are in $A'$, and $f(f(k))=f(m)=\tau{(k)}$, and $f(f(m))=f(\tau{(k)})=\tau{(m)}$. Therefore we have added the values $k,m$ to the set of positive integers such that the value of $f$ has been defined well. Repeating this process, we can inductively define the value of $f$ for all positive integers $n$, so that $f(f(n))=\tau{(n)}$ for all $n$. For example, after defining $f(1)=1$ and $f(2)=2$, to define $f(3)$ we need to find $m>3$ such that $\tau{(m)}=f(\tau{(3)})=f(2)=2$ and $f(m)$ has not been defined. $m=5$ is such a number, so we define $f(3)=5$ and $f(5)=2$. Next, to define $f(4)$, we need to find $m>4$ such that $\tau{(m)}=f(\tau{(4)})=f(3)=5$. $m=16$ is such a number, so we define $f(4)=16$ and $f(16)=3$. We already defined $f(5)(=2)$, so we move on to define $f(6)$. We need to find $m>6$ such that $\tau{(m)}=f(\tau{(6)})=f(4)=16$. $m=2^{15}$ is such a number, so we define $f(6)=2^{15}$ and $f(2^{15})=4$. Next, to define $f(7)$, we need to find $m>7$ such that $\tau{(m)}=f(\tau{(7)})=f(2)=2$. $m=11$ is such a number, so we define $f(7)=11$ and $f(11)=2$. Next, to define $f(8)$, we need to find $m>8$ such that $\tau{(m)}=f(\tau{(8)})=f(4)=16$. $m=2^{15}$ is such a number; however, we have already defined $f(2^{15})(=4)$, so we choose a different $m$. We can choose $m=3^{15}$, so that $f(8)=3^{15}$ and $f(3^{15})=4$. We can repeat this process so that $f$ will be defined well for all $n$.

@above unfortunately your solution is wrong for many reasons: 1) from $f(composite)=2$ you cannot jump to $f(6)=2$, because you have $f(n)=2$ for a specific composite number $n$(namely, $f(p)$), and not any composite number $n$. So you can't plug in $n=6$. 2) Even if you somehow get a contradiction after assuming $f(p)$ is composite, you still have to deal with the case when $f(p)=1$. 3) I don't understand why $f(2)=4$ contradicts that $f(p)$ is composite.(The method you reached $f(2)=4$ is wrong anyway though, as I explained above) 4) You cannot conclude that $f(p)=p$, that is not true for this problem. You have to prove that $f(p)=q$ for some prime $q$, given any prime $p$. You can read a correct solution in the forum to understand how to approach the problem, for example ABCDE's solution seems correct.