First, let $ f(1) = 1$. Let $ S\subseteq\mathbb{N}$ be the set of numbers that aren't perfect squares. Take the two smallest elements of $ S$, and remove them. Call them $ a,b$. Define for all nonnegative integers $ n$, $ f(a^{2^{n}}) = b^{2^{n}}$, and $ f(b^{2^{n}}) = a^{2^{n+1}}$. Thus $ f(f(a^{2^{n}})) = a^{2^{n+1}}$, and $ f(f(b^{2^{n}})) = b^{2^{n+1}}$ as desired. Continue this procedure of removing the two smallest elements of $ S$ and pairing them up in this way ad infinitum. By examining the exponents in prime factorizations, we can see that for any two elements $ a,b\in S$, we have that $ a^{2^{n}}\neq b^{2^{k}}$ regardless of $ n$ and $ k$, so there won't be any multiple outputs for this function. Additionally, $ \{a^{2^{n}}| a\in S, n\in\mathbb{N}\cup\{0\}\}=\mathbb{N}$, so we have defined the function for all natural numbers.

Correct, except that I think that you should remove all powers of $ a$ and $ b$ in the next $ S$.

None of the numbers of the form $ a^{2^{n}}, b^{2^{n}}$ are in $ S$ if $ n\geq 1$, so I think we only have to remove $ a$ and $ b$. For instance, if one of $ a$ and $ b$ is $ 2$, we don't want to remove $ 8$, as $ f(8)$ has yet to be defined.

Good point!

This problem is very easy Frist , choose an arbitrary odd prime $ p$ . Define the function $ g : \mathbb{N} \to \mathbb{N}$ as follows : $ g(n) \ = \ \frac {n}{p}$ if $ 2 \not |v_p(n)$ and $ g(n) \ = \ 2np$ if $ 2 | v_p(n)$ An easy check can verify that : $ g(g(n)) \ = \ 2n \ \forall n \ \in \ \mathbb{N}$ Then , we can construct the function $ f$ as follows : $ f(1) \ = \ 1 \ = \ 1^2$ For the positive integer $ n > 1$ , assume that it's prime fractorization is $ p^{\alpha_1}_1 \cdot p^{\alpha_2}_2 \cdots p^{\alpha_k}_k$ With $ p_1 ; p_2 ; ...; p_k$ are distinct pimes , $ \alpha_1 ; \alpha_2 ; ...; \alpha_k$ are positive integers . Then , we can choose $ f(n) \ = \ p^{g(\alpha_1)}_1 \cdot p^{g(\alpha_2)}_2 \cdots p^{g(\alpha_k)}_k$ So that $ f(f(n)) \ = \ p^{g(g(\alpha_1))}_1 \cdot p^{g(g(\alpha_2))}_2 \cdots p^{g(g(\alpha_k))}_k$ $ \rightarrow f(f(n)) \ = p^{2\alpha_1}_1 \cdot p^{2\alpha_2}_2 \cdots p^{2\alpha_k}_k \ = \ n^2$ In conclusion , $ f(n) = n^2 \ \forall \ n \ \in \ \mathbb{N}$ , Done

I had the same solution as MellowMelon, but also proved that the function is unique by choice (you can arbitrarily pair the nonsquare numbers up, but that's it). Here it goes: First note that f(1) = 1. For the rest of the problem, none of the variables equal 1. Suppose that f(n) = k. It follows that $k \neq n$ since that would imply f(f(n)) = n, a contradiction. Iterating the function shows us that $f(n^{2^m}) = k^{2^m}$ and $f(k^{2^m}) = n^{2^{m+1}}$. We can prove this inductively. Moreover, group all such elements in sets $S_{n,k}$ = {$f^m(n), f^m(k)$} of basis f(n) = k. Now suppose $f(n^2) = k$ and f(n) = p. Iterating the function gives $f(n^2) = p^2$. Hence, $k = p^2$, and we can write the basis for this pair as f(n) = p. Running this procedure until completion eventually results in n not being a perfect square. Hence all $S_{n,k}$ must be derived from a nonsquare n (regarding basis f(n) = k). Now suppose $f(n) = k^2$. Since f(f(k)) = $k^2$, we have f(n) = f(f(k)). Since f is injective, it follows that f(k) = n. Hence, we can rewrite the set $S_{n,k}$ in terms of f(k) = n. Applying the above procedure yields that k is nonsquare in basis f(n) = k. Hence all $S_{n,k}$ must have bases that satisfy n, k are not perfect square numbers. Since $\mathbb{N}$ is partitioned into sets $S_{n,k}$ by arbitrarily pairing nonsquare n, k, this function is unique. (MellowMelon showed this through uniqueness of prime factorization).

nguyenvuthanhha wrong solution.