A problem on the largest divisor d of N with d≤ √N

@misc{cherukupally2026problem,
  title = {{A problem on the largest divisor $d$ of $N$ with $d\leq \sqrtN$}},
  author = {Srikanth Cherukupally},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.08596},
  eprint = {2609.08596},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.08596},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - A problem on the largest divisor d of N with d≤ √N
AU  - Srikanth Cherukupally
PY  - 2026
DA  - 2026/09/16
PB  - arXiv
DO  - 10.48550/arxiv.2609.08596
UR  - https://arxiv.org/abs/2609.08596
AB  - For a given number N, we consider the problem of computing two integers 1≤ r,f < N such that the set 𝒳(N,r,f) = {(a+b)−(f+(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 ≤ l(Nr+1), where l(x) is the largest divisor of x bounded by √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 (ϕ(N)−2)/|F(N)| is approximately about c*log log N. Here, F(N) is the set of unique r appearing among all possible pairs (r,f), ϕ(.) 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.
ER  -