7
$\begingroup$

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}$?

  • 0
    Yes, I believe so. Analogously, under the same 'almost all' conditions as Maier-Tenenbaum, that size of the gap |a-b| is almost always $O(\sqrt{n})$ size. (The upper bound, $n-1$, is tight at the primes, the lower bound, zero, is tight at the squares.)2012-07-23

1 Answers 1

7

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.]

This was proved, in a strengthened form, in Maier and Tenenbaum, On the set of divisors of an integer, Invent. Math. 76 (1984), no. 1, 121–128, MR0739628 (86b:11057).

Many other papers have taken the Maier-Tenenbaum paper as a starting point for further investigations. There's a whole book, Hall and Tenenbaum, Divisors, Cambridge Tracts in Mathematics, 90, Cambridge University Press, Cambridge, 1988, MR0964687 (90a:11107).

  • 0
    Between th$i$s answer and WimC's reference to Fermat's factorization method, I feel much better acquainted with the nuances of this problem. Thanks!2012-07-23