Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 2 down vote favorite

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\}}$$

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

1 Answer

up vote 1 down vote accepted

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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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