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.

$\endgroup$
3
  • 5
    $\begingroup$ 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? $\endgroup$
    – Qiaochu Yuan
    Jan 20, 2012 at 4:45
  • $\begingroup$ I care about the upper bound (Big O complexity). Basically one of the programs I am working on reduces to this. $\endgroup$
    – Hari
    Jan 20, 2012 at 4:59
  • $\begingroup$ 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$. $\endgroup$
    – Qiaochu Yuan
    Jan 20, 2012 at 6:12

1 Answer 1

Reset to default
5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ (+1) I have always found the numbers which appear in Robin's papers are quite amusing and yet quite beautiful! $\endgroup$
    – JavaMan
    Jan 20, 2012 at 5:50
  • 2
    $\begingroup$ He is full of whimsy. $\endgroup$
    – Will Jagy
    Jan 20, 2012 at 5:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .