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.

$\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$ 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$ Aug 3, 2013 at 4:36
  • $\begingroup$ @Noam, yes, I was responding to the second question, about fixed $x$. $\endgroup$ Aug 3, 2013 at 12:06
  • $\begingroup$ Is that meant to be $8x-3z$ (so that we get a homogenous cubic)? $\endgroup$ Aug 3, 2013 at 20:53
  • $\begingroup$ @DavidSpeyer No, it has the form $p(x)=y^2z$, not homogeneous. $\endgroup$
    – Kirill
    Aug 3, 2013 at 23:46

3 Answers 3

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.

$\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

$\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.

$\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$ 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
    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$ 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
    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
    Aug 3, 2013 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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