Efficiently finding the largest divisor of N less than sqrt(N)

Question

Suppose you have a number $$ N = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} $$ and are looking for the largest divisor $d|N$ such that $d^2<N$ (that is, A060775$(N)$.) How can I efficiently find this $d$?

If $N$ has a small number of divisors, you can just iterate through them all (keeping the best at each step). If $e_i$ is large for some $i$, then you can search the divisors $d$ of $N/p_i^{e_i}$ less than $\sqrt{N}$ and find $$ e=\min\left(\left\lfloor\frac{\log(\lfloor\sqrt{N-1}\rfloor/d)}{\log p_i}\right\rfloor, e_i\right) $$

(this would be

s=sqrtint(N-1);
f=factor(N);
e=min(logint(s\d, f[i,1]), f[i,2])

in PARI/GP; presumably lots of languages have efficient implementations)

giving $p_i^ed$ as the number to test. But for the general case where $k$ is large neither is practical. Is there some method which takes significantly fewer than $\tau(N)$ steps? You can assume that the factorization is given.

Answer 1

I believe the Schroeppel & Shamir algorithm [1] can be adapted for use here, with time something like $O\left(\sqrt{\tau(n)}\omega(n)\right)$ and space something like $O\left(\sqrt[4]{\tau(n)}\right)$. The basic idea is splitting the prime powers into four sets with roughly the same number of divisors each, listing the divisors, and generating divisors from two pairs of two sets dynamically using min-heaps, and combining as expected.

[1] Richard Schroeppel and Adi Shamir, A $T = O(2^{n/2})$, $S = O(2^{n/4})$ algorithm for certain NP-complete problems, SIAM Journal on Computing, Vol. 10, Iss. 310, pp. 456–464.

Answer 2

I believe the problem is actually a special case of a knapsack problem --- for $\vec c = (\log p_1,\dots,\log p_k)$, you have to maximize $\langle \vec x, \vec c\rangle$ subject to the constraints

1. $\forall i : 0\leq \vec x_i \leq \vec e_i$, and
2. $\langle \vec x, \vec c\rangle < \langle \vec e, \vec c\rangle/2$.

Written in this way, it is simple to see that this is a "special case" of a "bounded knapsack problem" (the bounded knapsack problem allows the constraint labelled 2 above to be of the form $\langle \vec x, \vec c\rangle < W$ for arbitrary $W$). This is to say that it is at least closely related to an NP hard problem, but the above does not allow us to conclude that it is NP hard.

If you are fine with efficient approximate answers, being an instance of the bounded knapsack problem is good. This is because the bounded knapsack problem admits an FPTAS, so for any $\epsilon > 0$, there is an algorithm that finds solutions within an $(1-\epsilon)$ factor of optimal in time $\mathsf{poly}(k, 1/\epsilon)$, so quite efficiently. If you let $\vec x_{opt}$ be the optimal solution, this will approximation algorithm will return some $\vec x$ such that

$$(1-\epsilon)\langle \vec x_{opt}, \vec c\rangle \leq \langle \vec x, \vec c\rangle \leq \langle \vec x_{opt}, \vec c\rangle.$$ Rewriting back in terms of the inital problem, if $d_{opt} = \exp(\langle \vec x_{opt}, \vec c\rangle)$ is the optimal divisor, we will get a divisor $d$ such that

$$d_{opt}^{1-\epsilon} \leq d\leq d_{opt}.$$

This is already good enough to get an extremely accurate approximation to your problem. In particular, choosing $\epsilon = \frac{1}{\log_2 N}$ (which will still yield a poly-time computation), we get that $\left(N/2\right)^{\frac{\log_2 d_{opt}}{\log_2 N}}$. Under the (to me reasonable) assumption that $\log_2 d_{opt}\approx \frac{1}{2}\log_2 N$, we therefore get a divisor lower-bounded by the quantity $\sqrt{N/2}$, meaning nearly optimal. I don't know if a high-quality approximation is sufficient for your purposes though.