Crazy function

Throughout this solution, $f^{n}(x) = f(f(...f(x))...)$ , where the function $f$ is applied $n$ times.

$f$ is a function from the set of positive integers to itself such that

$(1)$ $f(x) \le x^2$

$(2)$ $f(f^2(x)f^2(y)) = xy$

for all positive integers $x, y$ .

$(1)$ implies $f(1) = 1$ . Substituing $y = 1$ in $(2)$ together with $f(1) = 1$ gives $f^3(x) = x$ for all positive integers $x$ .

Step 1. $f$ is bijective

If $f(x) = f(y)$ , then $x = f^3(x) = f^3(y) = y$ , so $f$ is injective. Since $f^3(x) = x$ , for every $x$ there exists $y = f^2(x)$ such that $f(y) = x$ , so $f$ is surjective. Thus, $f$ is bijective.

Step $1$ implies $f^{-1} = f^2$ is defined.

Step 2. $f(x)f(y) = f(xy)$ and $f^{-1}(x)f^{-1}(y) = f^{-1}(xy)$

By $(2)$ , $f(f^{-1}(x)f^{-1}(y)) = f(f^2(x)f^2(y)) = xy$ . Thus, by applying $f^{-1}$ to both sides, we get the second identity. Similarly, $f(x)f(y) = f(f^{-1}(f(x)f(y))) = f(f^{-1}(f(x))f^{-1}(f(y))) = f(xy)$ .

Step 3. If $p$ is prime, then $f(p)$ is prime.

Suppose $f(p) = qr$ for some prime $p$ and some product $qr$ with $q, r \ge 2$ . Then, $p = f^{-1}(qr) = f^{-1}(q)f^{-1}(r)$ , so $p$ is the product of two numbers greater than $1$ , a contradiction. (Since $f(1) = 1$ and $f$ is bijective.)

Thus, we can describe all possible $f$ as a set of ordered triples of primes $(p , q, r)$ , such that $f(p) = q, f(q) = r, f(r) = p$ , (WLOG, $p < q , r$ ), and with every prime appearing in at most one triple and for all triples $p^4 \ge q^2 \ge r$ . If a prime $s$ appears in no triples, then $f(s) = s$ .

Step 4. All such sets of triples describe a valid $f$ .

Consider any $x = \prod p_i$ where each $p_i$ is prime. Then, $f(x) = f(\prod p_i) = \prod f(p_i) \le \prod p_i^2 = x^2$ (by $(1)$ ). So, $f$ satisfies $(1)$ . Let $y = \prod q_i$ where each $q_i$ is prime. Then, $f(x)f(y) = \prod f(p_i) \prod f(q_i) = f(xy)$ (because $p_i$ and $q_i$ together are the prime factors of $xy$ .) Thus, $f$ satisfies $(2)$ .

Now, consider $f(30) = f(2)f(3)f(5)$ . We know that $f(2) \in \{2, 3\}$ . If $f(2) = 3$ , then $f(3) \in \{5, 7\}$ . If $f(3) = 5$ , then $f(5) = 2$ , giving $f(30) = 30$ ; if $f(3) = 7$ , then $f(5) \in \{5, 11, 13, 17, 19, 23\}$ , each of them giving a new value of $f(30)$ . Now, we have $7$ values, all of which are odd except for $30$ .

If $f(2) = 2$ , then $f(3) \in \{3, 5, 7\}$ . Either way, $f(5) \in \{5, 7, 11, 13, 17, 19, 23\}$ . Except

a) $f(5) \neq 5$ if $f(3) = 5$ .

b) $f(5) \neq 7$ if $f(3) = 7$ .

c) If $f(3) = 3$ and $f(5) = 5$ , then $f(30) = 30$ , which we already counted.

d) We count $f(30) = 2 \cdot 5 \cdot 7$ twice.

That's gives a total of $7 \cdot 3 - 4 = 17$ more values, all of which are even and not $30$ .

This gives a total of $7 + 17 = \boxed{24}$ possible values.