Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
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 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
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 7:21
show 2 more comments

1 Answer

up vote 6 down vote accepted

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

share|improve this answer
    
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 6: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 6:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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