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

  • 1
    Fermat's factorization method is based on finding this pair.2012-07-23
  • 0
    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.2012-07-23
  • 2
    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.2012-07-23
  • 0
    Integers $n$ with factorizations $n=ab$ with $0\lt a\le b\le2a$ are tabulated at http://oeis.org/A071562, but not much useful information is given there.2012-07-23
  • 0
    https://oeis.org/A0336762012-07-23
  • 1
    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.2012-07-23
  • 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

6

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
    This is an interesting result that very much captures the flavor of what I'm looking for. I also agree completely with your comment that a 'clever algorithm' would in general need to find 2 integer prime factorizations, which is of course unlikely.2012-07-23
  • 0
    Between this 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