1
$\begingroup$

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.

  • 0
    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$.2012-01-20

1 Answers 1

5

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

  • 2
    He is full of whimsy.2012-01-20