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$
$\endgroup$
4
1 Answer
$\begingroup$
$\endgroup$
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)$.
answered Mar 25, 2013 at 13:33
for k = 1 to infinity, if n mod k != 0, return k-1? I wonder if I misunderstood your question. $\endgroup$