Suppose that from some point $ x_0$ onwards the function becomes monotonic. It's easy to see that it must be increasing. Indeed take a prime $ p$ of the form $ 4k + 1$. It is both well-known and elementary (Thue's Lemma)that there are $ x,y\in\mathbb{Z}$ s.t. $ x^2 + y^2 = p$, or that $ (xy')^2 + 1\equiv0\pmod p$, from where there is $ r$ s.t. $ p|r^2 + 1$. Now take primes $ s_1,\ldots, s_d$ of the form $ 4k + 1$. Let $ r_i$ s.t. $ s_i|r_i^2 + 1$, and using Chinese Remainder Theorem take $ N$ to be $ \equiv r_i\pmod{s_i}$ for every $ i = 1,\ldots,d$. Then $ (p_1\ldots p_s)|N^2 + 1$ and $ (N^2 + 1)^2$ has as many divisors as we want (because $ d$ can be made very large). So $ f$ can't be monotonically decreasing from some point onwards. So suppose $ f$ is increasing. Let $ f_n = f(n) = d\left((n^2 + 1)^2\right)$. Using the identity $ [a^2 + 1][(a - 1)^2 + 1] = (a^2 - a + 1)^2 + 1$, and the fact that $ \gcd(a^2 + 1,(a - 1)^2 + 1) = 5$ if $ 5|a + 2$, and $ 1$ otherwise; We get the inequality $ f_af_{a - 1}\le f_{a^2 - a + 1}$, for $ a$ such that $ 5\not|a + 2$. Take an $ x > x_0$ such that $ 5\not| x + 2$. Then $ f_{x - 1}^2\le f_xf_{x - 1}\le f_{x^2 - x + 1}\le f_{4(x - 1)^2}$, from the monotony of $ f$. So we have established the inequality $ f_t^2\le f_{4t^2}$, where $ t = x - 1$, and $ 5\not|t + 3$. Because $ 5\not|4t^2 + 3$, we further get $ f(t)^4\le f(4t^2)^2\le f(4(4t^2)^2)$, and so on, by an easy induction we get $ f(t)^{2^k}\le f\left(4^{2^k - 1}t^{2^k}\right)\le f\left([4t]^{2^k}\right)$. Let $ c = f(t)$. Define $ g(x)$ as the positive integer satisfying $ (4t)^{2^{g(x)}}\le x < (4t)^{2^{g(x) + 1}}$. Then from the above inequality and the monotony of $ f$ for big enough $ x$ we have $ \boxed{c^{2^{g(x)}}\le f(x)}$. Now we'll find an upper estimate for $ f(x)$. For this, let $ p_1 = 2,p_2 = 3,p_3 = 5,\ldots$ the sequence of prime numbers. Let's analyze $ f(n) = f(p_1\ldots p_k)$. Let $ (p_1\ldots p_k)^2 + 1 = \displaystyle\prod_{i = 1}^sq_i^{\alpha_i}$. Clearly $ q_i > p_j$ for all $ i = \overline{1,k}$ and $ j = \overline{1,s}$. This implies $ \displaystyle\sum_{i = 1}^s\alpha_i\le 2k$. $ f(n) = d\left(\left[(p_1\ldots p_k)^2 + 1\right]^2\right) = (2\alpha_1 + 1)(2\alpha_2 + 1)\ldots(2\alpha_s + 1) = h(\alpha_1,\ldots,\alpha_s)$. Using the fact that $ 2a + 1 < 3(2a - 1)$ for $ a > 1$, we see that $ h(\alpha_1,\ldots,\alpha_s)\le h(\alpha_1 - 1,\alpha_2,\ldots,\alpha_s,1)$, if WLOG $ \alpha_1 > 1$. Ok, this unrigurous line (which is, in fact, really simple) was just to show that $ h(\alpha_1,\ldots,\alpha_s)\le h\left(\underbrace{1,1,\ldots,1}_{\sum\alpha_i}\right)\le3^{2k}$, because $ \displaystyle\sum_{i = 1}^s\alpha_i\le 2k$. Introduce $ l(x)$ to be the index $ v$ for which $ p_1\ldots p_v\le x < p_1\ldots p_vp_{v + 1}$. Using again the monotony of $ f$ we get $ \boxed{f(x)\le 9^{l(x)}}$, for big enough $ x$. Now let's finish. From the definition of $ g$ we get $ g(x) = \lfloor \log_2\lfloor\log_{4t}x\rfloor\rfloor$. So $ 2^{g(x)} > 2^{\log_2\lfloor\log_{4t}x\rfloor - 1} = \frac12\lfloor\log_{4t}x\rfloor$, from where $ c^{2^{g(x)}} > (\sqrt c)^{\lfloor\log_{4t}x\rfloor}$. As we can choose $ c$ as large as we want, we are left with showing that for big enough $ x$, $ \lfloor\log_{4t}x\rfloor$ becomes larger than $ l(x)$, as then the two boxed inequalities will contradict each other. This results from the fact that for large enough $ x$ we have $ (4t)^{l(x)} < p_1\ldots p_{l(x)} < x$, as $ 4t$ is constant, but prime numbers grow very big. Hope the solution is correct...please notify me on mistakes / typos within the next 24 hours so that I can fix them without multiple-posting @Peter: BTW, I haven't found this problem in Russia 1998. Are you sure about its source?

freemind wrote: Hope the solution is correct...please notify me on mistakes / typos within the next 24 hours so that I can fix them without multiple-posting Is it not possible to edit after 24 hours? Strange, I didn't know that. Thanks for pointing out. But in any case it's no problem to multi-post (I'll probably just edit your post and delete the double-post anyway ). freemind wrote: @Peter: BTW, I haven't found this found in Russia 1998. Are you sure about its source? Absolutely not sure. You have any idea what is the correct source?