I have the following functional equation:

$f(n) = 2 \cdot f\left(\frac{n}{f(n)}\right)$

Under the precondition that $ f(n) = \omega(1) $, monotinic and a initial value $ f(1) = \Theta(1) $ one can show (by induction) that $ \Omega((\log n)^k) = f(n) = O(n^\alpha) $ for arbitrary large $ k $ and small $\alpha$ (see below).

It seems to me that these bounds are very tight so the question is:

Is there a (simple) function that satisfies these conditions?

Proof sketch:

$ f(n) = 2 \cdot f\left(\frac{n}{f(n)}\right) \le 2 \cdot \left(\frac{n}{f(n)}\right)^\alpha = n^\alpha \cdot \left(\frac{2}{f(n)^\alpha}\right) \le n^\alpha \quad $ for sufficient large $ n$.

$ f(n) = 2 \cdot f\left(\frac{n}{f(n)}\right) \ge 2 \cdot \left(\log\left(\frac{n}{f(n)}\right)\right)^k \ge 2 \cdot \left(\log\left(\frac{n}{n^\alpha}\right)\right)^k = 2 \cdot (1 - \alpha)^k \cdot \left(\log n\right)^k \ge \left(\log n\right)^k \quad $ for sufficient large $n$ and small $ \alpha $.

  • $\begingroup$ Is your function defined on integers? Then I don't understand what $\frac{n}{f(n)}$ means. $f(n)$ is always a divisor of $n$? But then by your equation either $f(p)=2f(1)$ if $f(p)=p$ or $f(p)=2f(p)$ if $f(p)=1$... $\endgroup$ – user68061 Jan 13 '14 at 18:28
  • $\begingroup$ @user68061 Given the way the function is written, I don't think assuming it is defined for the integers is reasonable (granted, the OP is using the variable $n$...) $\endgroup$ – Igor Rivin Jan 13 '14 at 18:32
  • $\begingroup$ Well, then what is meant by ``proof by induction''? $\endgroup$ – user68061 Jan 13 '14 at 18:33
  • $\begingroup$ the functional equation in the title is not the same as in the post ... $\endgroup$ – kjetil b halvorsen Jan 13 '14 at 19:13
  • $\begingroup$ @kjetilbhalvorsen Thanks. $ f(n) = f(n)/2 + f(n/f(n)) $ was the original (equivalent) form. It's now simplified in the title, too. $\endgroup$ – Hannes Jan 13 '14 at 20:02





Let $g(n)=\dfrac{n}{f(n)}$ ,

Then $g(g(n))=\dfrac{2(g(n))^2}{n}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.