A Bijective Function

Great problem!

First note that $f(1)=f(1\cdot 1)=f(1)\cdot f(1)$ , so that $f(1)=1$ . Composite numbers are mapped to composite numbers, and prime numbers are mapped to prime numbers.

$f(2015)=42$ tells us that 5, 13, and 31 are mapped to 2, 3, and 7, in some order.

Since $2000=2^4\cdot5^3$ we need to map 2 and 5 to the smallest possible prime values, namely, $f(5)=2$ (see the last paragraph) and $f(2)=5$ , so that $f(2000)=5^4\cdot 2^3=\boxed{5000}$

This was fun! I'll try to fill in the bijection argument of Otto Bretscher's elegant proof. Let $\mathbb{P}$ be the set of primes. $$

• Note that $f(1)=f(1\cdot 1)=f(1)^2$ , so we must have $f(1)=1$ . Prime numbers $p_k$ must be mapped to numbers greater than 1, otherwise $f$ would not be injective: $f(p_k)\geq 2$ $$
• In the definition, set $y=1$ and replace any $x>1$ by its unique prime factorization. Using the definition repeatedly, we get: $\begin{aligned} x&>1:& x&=p_1^{m_1}\cdot\ldots\cdot p_n^{m_n}&&& \Rightarrow &&&& f(x)&=f(p_1)^{m_1}\cdot\ldots\cdot f(p_n)^{m_n}&&&&&(1) \end{aligned}$ Note that any composite $x>1$ will be mapped to a composite, as it has at least two factors $f(p_k)\geq 2$ . $$

• We guess that primes will be mapped to primes, i.e. $f^{-1}(\mathbb{P})=\mathbb{P}$ . We prove it by showing both inclusions via contradiction:

  Let $x=f^{-1}(p_k)\in f^{-1}(\mathbb{P})$ and assume $x$ is composite. By the above, $f(x)=f(f^{-1}(p_k))=p_k$ is composite - contradiction!

  Let $x\in\mathbb{P}$ and assume $f(x)=y_1y_2$ was composite with $y_k>1$ . We know $f$ is bijective and 1 is already taken, so we find $x_k>1$ with $y_k=f(x_k)$ . By definition, we get $f(x)=y_1y_2=f(x_1)f(x_2)=f(x_1x_2)\underset{f\text{ bijective}}{\qquad\Rightarrow\qquad} x=x_1x_2\not\in\mathbb{P}\qquad\left|\text{ Contradiction!}\right.$

• Factor $2015=5\cdot 11\cdot 13$ and $42=2\cdot 3\cdot 7$ . With the knowledge that primes are mapped to primes bijectively, we get $\begin{aligned} f(2015)&=f(5)\cdot f(11)\cdot f(13)=2\cdot 3\cdot 7&&& \Rightarrow &&&& f(\{5;\:11;\:13\})&=\{2;\:3;\:7\},&&& f(2)&\in\mathbb{P}\setminus\{2;\:3;\:7\} \end{aligned}$ Finally we can estimate $f(2000)=f(2^4\cdot 5^3)=f(2)^4\cdot f(5)^3\leq 5^4\cdot 2^3=\boxed{5000}$