Problem 1809

1. Claim: The function $f$ maps prime power inputs to prime power outputs. Specifically, if $f(p)$ is a power of a prime $q$ (where $p$ is a prime), then $f(p^k)$ is also a power of $q$ for all $k \in \mathbb{N}$.

2. Proof of Claim:
- By the Chinese Remainder Theorem (CRT), we can find 2012 consecutive numbers, none of which are prime powers. For instance, set $N \equiv -i \pmod{p_i q_i}$ for some distinct primes $p_i$ and $q_i$. This ensures that there are arbitrarily large runs of non-prime power numbers.
- Let $N$ be a prime power such that $N+1, \ldots, N+2012$ are all non-prime powers.
- Consider all the prime powers in $\{1, \ldots, N\}$, partitioned into boxes as follows:
$$\begin{array}{c} \boxed{2, 2^2, \ldots, 2^i, \ldots} \\ \boxed{3, 3^2, \ldots, 3^i, \ldots} \\ \vdots \\ \boxed{p_k, p_k^2, \ldots, p_k^i, \ldots} \end{array}$$
There are $k$ boxes here, corresponding to the $k$ primes $\leq N$.
- Consider the set $A = \{2, 3, \ldots, p_k\}$. These $k$ numbers are pairwise relatively prime, so their images under $f$ are also pairwise relatively prime.
- Since $f(p_k) \leq N + 2012$ and the numbers $N, N+1, \ldots, N+2012$ do not introduce any new primes, the image of each $p \in A$ must be divisible by a unique prime among $\{2, \ldots, p_k\}$.
- Therefore, for any $p \in A$, $f(p) = \sigma(p)^k$, where $\sigma$ is some permutation on $A$.
- If $f(p^i)$ had a prime divisor other than that assigned to $f(p)$, it would clash with another prime in a different box, which is impossible since they are in different boxes.
- This proves our claim, as $N$ can be as large as we like.

3. Mapping of Primes to Their Own Powers:
- Suppose $f(p) = q^m$ for some prime $q \neq p$.
- Then for any $k$, $f(p^k) = q^\ell$ for some $\ell$ depending on $k$.
- This implies:
$$p^k < q^\ell \leq p^k + 2012 \implies \ell \in \left( \frac{\log p^k}{\log q}, \frac{\log (p^k + 2012)}{\log q} \right]$$
- The length of this interval is:
$$\frac{\log \left(1 + \frac{2012}{p^k}\right)}{\log q}$$
which becomes arbitrarily small as $k \to \infty$.
- The leftmost point of this interval is $k \log_q p$, whose fractional part can be made arbitrarily small for some large $k$, since $\{ k \alpha \}$ is dense in $(0,1)$ for $\alpha \in \mathbb{R} \setminus \mathbb{Q}$.
- Therefore, we can choose $k$ such that the interval fails to contain an integer, creating a contradiction for $\ell$.

4. Final Step:
- Suppose there exists $n \in \mathbb{N}$ and a prime $p$ such that $p \mid f(n)$ but $p \nmid n$.
- Then $(n, p) = 1 \implies (f(n), f(p)) = 1$, which contradicts $p \mid f(n)$ and $f(p) = p^k$.

Thus, we have shown that if $p$ divides $f(n)$, then $p$ must divide $n$.

$\blacksquare$