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\}}$$
Faster Algorithm for Computing Norm
algorithms;discrete mathematics;number theory
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)$.