Can anyone suggest an algorithm faster than $\Theta(n^{2})$ for computing the following function:

$$||n||:=\frac{1}{\max\{k \in \mathbb{N}: 1|n, 2|n,\ldots,k|n\}}$$

  • $\begingroup$ Why is it $O(n^2)$? Don't you just need to do for k = 1 to infinity, if n mod k != 0, return k-1? I wonder if I misunderstood your question. $\endgroup$ Commented Mar 25, 2013 at 6:47
  • $\begingroup$ What have you tried? Also, "faster than $O(n^2)$" makes no sense. $\endgroup$
    – Raphael
    Commented Mar 25, 2013 at 10:32
  • $\begingroup$ If the weird notation means select the largest $k$ that divides $n$, it is just $n$. $O(1)$. $\endgroup$
    – vonbrand
    Commented Mar 25, 2013 at 11:10
  • 1
    $\begingroup$ Of course $O(n^2)$ means $n^2$ is an upper bound, but I think you knew what I meant. @vonbrand The "weird" notation is standard and that is not what that means. It asks for the largest $k$ such that $i | n$ for all $1 \le i \le k$. For instance, $||n||=1$ for $n$ odd. $\endgroup$ Commented Mar 25, 2013 at 13:27

1 Answer 1


Store a list of all "factorials" (least common multiplies of $\{1,\ldots,k\}$) and use binary search. That reduces the number of divisions in the worst case. If the numbers $n$ you are getting are "random" then you might want to start with smaller trial divisions, or perhaps with an exponentially growing $k$, i.e. try $1,2,4,8,\ldots$ until you find some $k$ for which the LCM does not divide $n$, then take it from there using binary search.

By the way, since the LCM grows exponentially, even your algorithm only requires $\log n$ divisions. Each division takes time $\tilde{O}(n)$, so in total both your algorithm and mine are $\tilde{O}(n)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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