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$ – Karolis Juodelė Mar 25 '13 at 6:47
  • $\begingroup$ What have you tried? Also, "faster than $O(n^2)$" makes no sense. $\endgroup$ – Raphael Mar 25 '13 at 10:32
  • $\begingroup$ If the weird notation means select the largest $k$ that divides $n$, it is just $n$. $O(1)$. $\endgroup$ – vonbrand Mar 25 '13 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$ – J. G. Walters Mar 25 '13 at 13:27

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, privacy policy and cookie policy

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