7

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

Johan
  • 127
  • 1
    Fermat's factorization method is based on finding this pair. – WimC Jul 23 '12 at 05: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 05:33
  • 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. – Gerry Myerson Jul 23 '12 at 05:43
  • 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. – Gerry Myerson Jul 23 '12 at 05:48
  • https://oeis.org/A033676 – Charles Jul 23 '12 at 06:14
  • 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. – Chris Taylor Jul 23 '12 at 07:21
  • 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.) – Johan Jul 23 '12 at 18:41

1 Answers1

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

Gerry Myerson
  • 179,216
  • 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. – Johan Jul 23 '12 at 06:11
  • Between this answer and WimC's reference to Fermat's factorization method, I feel much better acquainted with the nuances of this problem. Thanks! – Johan Jul 23 '12 at 06:13