Problem 1363

1. **Define the function $g$:**
Consider a function $g: \mathbb{N} \to \mathbb{N}$ such that $g(g(n)) = 2n$. This function is known to exist. For instance, one can construct such a function using a pairing function or other combinatorial methods.

2. **Prime factorization of $n$:**
Let $n \in \mathbb{N}$ have the prime factorization $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, where $p_1, p_2, \ldots, p_k$ are distinct primes and $e_1, e_2, \ldots, e_k$ are their respective exponents.

3. **Define the function $F$:**
Define the function $F: \mathbb{N} \to \mathbb{N}$ as follows:
$$F(n) = p_1^{g(e_1)} p_2^{g(e_2)} \cdots p_k^{g(e_k)}$$
Note that $F(1) = 1$ since the prime factorization of 1 is trivial (no primes).

4. **Verify that $(F \circ F)(n) = n^2$:**
We need to show that $F(F(n)) = n^2$ for all $n \in \mathbb{N}$.

- Consider $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$.
- Then, $F(n) = p_1^{g(e_1)} p_2^{g(e_2)} \cdots p_k^{g(e_k)}$.
- Now, apply $F$ again:
$$F(F(n)) = F(p_1^{g(e_1)} p_2^{g(e_2)} \cdots p_k^{g(e_k)}) = p_1^{g(g(e_1))} p_2^{g(g(e_2))} \cdots p_k^{g(g(e_k))}$$
- By the definition of $g$, we have $g(g(e_i)) = 2e_i$ for each $i$.
- Therefore,
$$F(F(n)) = p_1^{2e_1} p_2^{2e_2} \cdots p_k^{2e_k} = (p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k})^2 = n^2$$

Thus, we have shown that $(F \circ F)(n) = n^2$ for all $n \in \mathbb{N}$.

$\blacksquare$