2
$\begingroup$

Given the Diophantine equation $$ x^2(8x-3)=y^2z, $$ is there a way to efficiently count the number of solutions that satisfy $x+y+z\leq n$, where $n$ is a fixed given integer?

Also, for any fixed $x$, is it possible to count all such solutions $(x,y,z)$ without having to explicitly find all the divisors of $x^2(8x-3)$?

A hint or a reference (if this is, in fact, easy) would be quite helpful.

I asked this on MSE, but got no responses.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Considering how closely the number of solutions is tied to the factorization of $x^2(8x-3)$, I'd be surprised if there were any way to count solutions that wouldn't be more or less equivalent to factoring $x^2(8x-3)$. Note, for example, that determining whether a number is squarefree is about as hard as factoring. $\endgroup$
    – Gerry Myerson
    Commented Aug 2, 2013 at 22:54
  • $\begingroup$ @Gerry Myerson: That's the solutions for a given $x$, not for all $x,y,z$ with $x+y+z=n$. You can estimate the number of positive integer solutions of $x=yz$ with $x\leq n$ without factoring each $x$. $\endgroup$
    – Noam D. Elkies
    Commented Aug 3, 2013 at 4:36
  • $\begingroup$ @Noam, yes, I was responding to the second question, about fixed $x$. $\endgroup$
    – Gerry Myerson
    Commented Aug 3, 2013 at 12:06
  • $\begingroup$ Is that meant to be $8x-3z$ (so that we get a homogenous cubic)? $\endgroup$
    – David E Speyer
    Commented Aug 3, 2013 at 20:53
  • $\begingroup$ @DavidSpeyer No, it has the form $p(x)=y^2z$, not homogeneous. $\endgroup$
    – Kirill
    Commented Aug 3, 2013 at 23:46

3 Answers 3

Reset to default
2
$\begingroup$

Dan Bernstein has developed an algorithm which might be relevant to your situation.

Bernstein - Enumerating solutions to p(a)+q(b)=r(c)+s(d). http://cr.yp.to/papers/sortedsums.pdf

The algorithm explained in the paper has been very successful in counting solutions to equations of the given type. Admittedly your equation is not exactly of the form considered in the paper, but you might be able to adapt his algorithm to your setting.

I vaguely remember that one essentially creates a list of all possible values on both sides then compares these lists looking for matches. Bernstein however does something clever with heaps which saves on the storage space.

Improve this answer
$\endgroup$
1
$\begingroup$

The equation implies $8 x - 3, z = p q^2, p r^2$, in which we can assume gcd(q, r) = 1.

Then $x q = y r$, from which gcd(q, r) = 1 implies that $r$ divides $x$.

So denoting $x = r t$, so that $y = q t$, the condition $x + y + z \le n$ is equivalent to:

$ p (q^2 + 8 r^2) + 8 q t \le (8 n - 3) $

which may be slightly more manageable for searches

Improve this answer
$\endgroup$
1
$\begingroup$

How about brute force? This consists of $O(n^3)$ steps (the verification of positive integers $x,\, y,\, z\, $ s. t. $x+y+z \le n$) in your case.

Improve this answer
$\endgroup$
7
  • $\begingroup$ The question said "efficiently", which must mean "better than brute force". A trivial improvement over $O(n^3)$ is to try all $(x,y)$ with $x+y \leq n$ and test whether $z = (8x-3)(x/y)^2$ is an integer that does not exceed $z-x-y$. That's $O(n^2)$, and it's easy to improve on that too. $\endgroup$
    – Noam D. Elkies
    Commented Aug 3, 2013 at 19:23
  • $\begingroup$ Polynomial complexity algorithms are considered as efficient. I think you mean $n-x-y$ instead of $z-x-y$ above. $\endgroup$
    – user64494
    Commented Aug 3, 2013 at 19:48
  • 1
    $\begingroup$ Yes, $n-x-y$, sorry. But it's not polynomial complexity in the usual sense because both the input (namely $n$) and the output (total count) take only $O(\log n)$ bits, so "polynomial" should mean polynomial in $\log n$, and both $n^3$ and $n^2$ are "exponential". $\endgroup$
    – Noam D. Elkies
    Commented Aug 3, 2013 at 20:01
  • $\begingroup$ I wrote a Maple procedure to this end. It counts 71 solutions for $n=400$ in 7s. See that here rapidshare.com/files/1769398012/counter.pdf as an exported PDF file. $\endgroup$
    – user64494
    Commented Aug 3, 2013 at 20:38
  • $\begingroup$ The bruteforce way to do this is to use a sieve of Eratosthenes to factor all integers up to $8n$, loop over all $x$'s up to $n$ and look at all factorizations $y^2z$. That's approximately $O(n)$ and I can do $n=10^8$ in a few minutes. $\endgroup$
    – Kirill
    Commented Aug 3, 2013 at 23:49

You must log in to answer this question.

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