Faster Algorithm for Computing Norm

Question

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

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