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.

I am looking for a general way to estimate the number of possible solutions to solve the diophantine equation of the form $xy = n$, where $n$ is a positive integer.

Note that $n$ can be an unusually large number (thousands of digits long), and I am hoping to find a quick algorithm that can be run in reasonable time in a standard machine.

share|improve this question
5  
This is more or less equivalent to factoring $n$; in any case it is at least as hard as deciding if $n$ is prime, and this was only very recently proven to be doable in polynomial time (en.wikipedia.org/wiki/AKS_primality_test). What do you need to do this for? Do you care more about upper or lower bounds? –  Qiaochu Yuan Jan 20 '12 at 4:45
    
I care about the upper bound (Big O complexity). Basically one of the programs I am working on reduces to this. –  Hari Jan 20 '12 at 4:59
    
Okay, but how bad of an upper bound are you willing to settle for? Getting precise information for fixed $n$ requires knowing a lot about the prime factorization of $n$. –  Qiaochu Yuan Jan 20 '12 at 6:12
add comment

1 Answer

up vote 5 down vote accepted

With equality at a number $n$ near $3.309 \cdot 10^{135},$ $$ d(n) \leq n^{ \left( \frac{\log 2}{\log \log n} \right) \left( 1 + \frac{1}{\log \log n} + \frac{4.762350121177...}{\left(\log \log n \right)^2} \right)} $$

This is from the thesis of Guy Robin.

The number giving equality is $$ 2^{11} \cdot 3^6 \cdot 5^4 \cdot 7^3 \cdot 11^2 \cdot 13^2 \cdot 17^2 \cdot 19^2 \cdot 23^2 \cdot 29 \cdot 31 \cdots 293 $$ with about $ \; 3.677 \cdot 10^{21} \;$ divisors.

Once you have a divisor, call that $x,$ then you just have $y=n/x.$

As far as something published that you can actually find, this is on page 230 of On Highly Composite Numbers by Jean-Louis Nicolas, pages 215-244 in a book called Ramanujan Revisited edited by George Andrews, Bruce Berndt and others. I have a pdf if anyone wants to email me, for some reason it does not print out properly but you can read it on the computer screen. The original item is referred to as Guy Robin, These d'etat, Universite de Limoges, France, 1983. See ROBIN

share|improve this answer
    
(+1) I have always found the numbers which appear in Robin's papers are quite amusing and yet quite beautiful! –  JavaMan Jan 20 '12 at 5:50
2  
He is full of whimsy. –  Will Jagy Jan 20 '12 at 5:52
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.