1
$\begingroup$

TL;DR: Is there a name for the largest value of $f$ for which $f|n$ and $n/f \ge f$? Or a name for the smallest value of $f$ for which $f|n$ and $n/f < f$?

Additional clarification. This question occurred to me while writing a very short piece of code to find the factors of a number and making a small optimisation to it. When you try to find the factors of a number $n$ you can simply take each element of the sequence $1, 2, 3, ..., n$ and check if $n$ is divisible by it. A first optimisation is to limit yourself to possible factors $f$ for which $f <= n/2$ (yielding only the proper divisors) and add $n$ itself to the set. A second optimisation is to stop at the first $f$ for which $n/f < f$. At that point the remainder of the factors can be found by dividing $n$ by each already found factor. I'm interested in knowing whether there's a name for this "pivot" element and its properties.

Examples:

  • For 12 the largest such $f$ is 3, since the remaining factors can be found by dividing 12 by 1, 2 and 3. The smallest "pivot" would be 4 as at that point $12/4 < 4$
  • For any prime number $p$ the largest $f$ so that $f|p$ and $p/f \ge f$ is 1, and the smallest $f$ so that $f|p$ and $p/f < f$ is $p$.
$\endgroup$
  • 2
    $\begingroup$ You could stop checking for factors at the square root of $n$: for example $\sqrt{12} \approx 3.46$. If you are restricted to integers, stop trying at the first potential factor $f$ where $f\times f \gt n$ $\endgroup$ – Henry Apr 2 at 20:01
  • $\begingroup$ @Henry Thanks mate. I suppose stopping at the first $f$ where $n/f < f$ is kind of equivalent. It would imply one extra check which I'll consider negligible. $\endgroup$ – G_H Apr 2 at 21:28
1
$\begingroup$

not sure about names; however, this leads directly into what we call Fermat's method of factoring. Given odd $n,$ find $ w =\lfloor \sqrt n \rfloor.$ Then increase $w$ one by one, and just check whether $w^2 - n$ is a square. If $w^2 - n = t^2,$ then $w^2 - t^2 = n,$ and $n = (w+t)(w-t).$

Your desired number, the largest factor below $\sqrt n,$ would appear as the first $(w-t).$

Fermat's is, among really elementary methods, the opposite of checking small prime factors. It is quick if $n$ is the product of two numbers (possibly prime) of very similar size

https://en.wikipedia.org/wiki/Fermat%27s_factorization_method

$\endgroup$
  • $\begingroup$ Thanks for the explanation and link. Optimisation and algorithms aside though, I'm just wondering if there's a specific term for this point at which the remaining factors are derivative of the ones already found. $\endgroup$ – G_H Apr 2 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.