# Is there a name for the “most square” factorization of an integer?

For the definition that follows, I'm curious to know if there's a known name (to enable a literature search relating to algorithms).

Definition. Given an integer $n$, the maximally square factorization consists of the integers $\{a,b\}$ such that $n=ab$ and the difference $|a-b|$ is minimized. Formally:

$$\{a,b\} = \arg \min_{\{x,y : x|n, y|n, xy=n\}} |x-y|.$$

Examples:

• For $n=16$, we get $\{a,b\}=\{4,4\}$.

• For $n=1300$, we get $\{a,b\}=\{26,50\}$.

Questions:

1) Does this concept have a name? Any closely related concepts are also of interest. Number theory is not my strength.

2) Is there some clever way for finding $\{a,b\}$ that doesn't require fully factorizing $n$ and taking the two integers closest to $\sqrt{n}$?

-
Fermat's factorization method is based on finding this pair. – WimC Jul 23 '12 at 5:12
Interesting, many thanks! Fermat's factorization method was not on my radar. From what I'm gathering, the method is very inefficient compared to modern factorization algorithms. I'm still curious if more direct results related to this question exist. – Johan Jul 23 '12 at 5:33
If you don't knnow the factors of $n$, then for all you know $n$ could be a product of two primes, and in that case finding $a$ and $b$ is equivalent to factoring $n$. In general, if you had a way to find $a$ and $b$ you could apply it repeatedly to factor $n$ completely, so there is no clever way to find $a$ and $b$ unless there is a clever way to factor $n$ completely. – Gerry Myerson Jul 23 '12 at 5:43
Integers $n$ with factorizations $n=ab$ with $0\lt a\le b\le2a$ are tabulated at oeis.org/A071562, but not much useful information is given there. – Gerry Myerson Jul 23 '12 at 5:48
Is this method 'clever' enough? Set $a=\lfloor \sqrt{n} \rfloor$. If $a|n$ then return $(a,n/a)$. Else set $a\leftarrow a-1$ and repeat. By the Maier-Tenenbaum theorem (see Gerry's answer) this will find the pair in average $O(\sqrt{n})$ time. – Chris Taylor Jul 23 '12 at 7:21

Erdos conjectured that almost all integers have a pair $d,d'$ of divisors satisfying $d\lt d'\le2d$. ["Almost all" means that if you take the number of integers less than $n$ having this property, and divide by $n$, and then let $n$ go to infinity, the quotient will approach 1.]