A problem on the largest divisor $d$ of $N$ with $d\leq \sqrt{N}$

Abstract

For a given number $N$, we consider the problem of computing two integers $1\leq r,f<N$ such that the set $$\mathcal{X}(N,r,f) = \{(a+b)-(f+\frac{Nr+1}{f}): ab=Nr\}$$ consists only of positive integers. Computing a solution to the problem is equivalent to finding a pair $(r,f)$ satisfying $l(Nr)<f \leq l(Nr+1)$, where $l(x)$ is the largest divisor of $x$ bounded by $\sqrt{x}$. This requires factoring both $Nr$ and $Nr+1$. We present a simple randomized algorithm that - avoiding factoring - computes pairs $(r,f)$. We give an exact formula for the total number of possible pairs $(r,f)$, and with the aid of empirical data we estimate that the ratio $$\frac{\phi(N)-2}{|\mathfrak{F}(N)|}$$ is approximately about $c*\log \log N$. Here, $\mathfrak{F}(N)$ is the set of unique $r$ appearing among all possible pairs $(r,f)$, $\phi(.)$ is the Euler's Totient function, and $c$ is a constant equal to 2 for prime $N$ and oscillates much for composite $N$. As a separate and independent case, we study the same problem of computing $(r,f)$ with $r>N$. We present a procedure to find such an $r$, which requires finding the least prime in an arithmetic progression.