6
$\begingroup$

I'm trying to know if there is an efficient way to find the smallest (i.e lexicographically) triplet $(a,b,c)$ of integers verifying $$a^2+b^2+c^2 = x$$ $$a^3+b^3+c^3=y$$ $$a^4+b^4 + c^4 = z$$ if $(x,y,z)$ is known.

We assume that a solution exists for that triplet $(x,y,z)$.

Originally, this question is part of an algorithmic problem. So what I want is a fast way to find the triplet without having to brute-force.

What I've tried (the brute-force approach): going through all the possible values of $a$ since we can deduce an upper bound for its value, we remain with three equations where it's easy to find $b$ and $c$ and see if they are integers.

EDIT: We may assume as well that $a<b<c$.

$\endgroup$
1
$\begingroup$

If $a,b,c$ are integers such that

$$a^2 + b^2 + c^2 = x$$ $$a^3 + b^3 + c^3 = y$$ $$a^4 + b^4 + c^4 = z$$

then the following divisibility conditions must hold:

$$ \left( a + b + c \right) \mid \left( x^2 - 2z \right) $$

$$ \left( 4\left(ab + bc + ca\right) \right) \mid \left( x^4 + 6x^2z - 16xy^2 + 9z^2 \right) $$

$$ \left( 2abc \right)^2 \mid \left( x^6 - 4x^3y^2 - 3x^2z^2 + 12xy^2z - 4y^4 - 2z^3 \right) $$

Of these, the last will cut down your search considerably.

$\endgroup$
  • $\begingroup$ Can you please provide a quick hint how did you get these divisibility conditions ? $\endgroup$ – Blencer Dec 31 '16 at 2:24
  • $\begingroup$ @Guru: I used Maple's Groebner basis package to "solve" for the elementary symmetric functions of $a,b,c$ in terms of $x,y,z$ $\endgroup$ – quasi Dec 31 '16 at 2:27
  • 1
    $\begingroup$ Besides, these conditions do not solve the problem since with the condition $a<b<c$ we get $4a^6 < RHS$ but RHS can be very big, the range of searching for a is still large. Algorithmically, I start searching a beginning from 0, and whenever I get a solution for $a$ I stop the loop. Therefore, reducing the upper bound does not make any change. Finding a lower bound or a lower bound for $a$ would be more helpful. $\endgroup$ – Blencer Dec 31 '16 at 2:30
  • $\begingroup$ For given integers $x,y,z$, Just factor the RHS (integer factors). $\endgroup$ – quasi Dec 31 '16 at 2:34
  • $\begingroup$ Doesn't look like a simple task .. $\endgroup$ – Blencer Dec 31 '16 at 2:37
0
$\begingroup$

If you have software to find real roots, the following result provides another way to find qualifying triples $a,b,c$ ...

Proposition: If $a,b,c$ satisfy $a^2 + b^2 + c^2 = x$, $a^3 + b^3 + c^3 = y$, $a^4 + b^4 + c^4 = z$, then $a,b,c$ are roots of the following 12'th degree polynomial:

$$ p(t) = \left(12\right)\left(t^{12}\right) -\left(24x\right)\left(t^{10}\right) -\left(16y\right)\left(t^9\right) +\left(24x^2-12z\right)\left(t^8\right) +\left(48xy\right)\left(t^7\right) $$ $$ -\left(24x^3+8y^2\right)\left(t^6\right) -\left(24x^2y-24yz\right)\left(t^5\right) $$ $$ +\left(15x^4+6x^2z-24xy^2+3z^2\right)\left(t^4\right) +\left(8x^3y-24xyz+16y^3\right)\left(t^3\right) $$ $$ -\left(6x^5-12x^2y^2-6xz^2+12y^2z\right)\left(t^2\right) +\left(x^6-4x^3y^2-3x^2z^2+12xy^2z-4y^4-2z^3\right) $$

$\endgroup$
  • $\begingroup$ I'm meant to solve just an algorithmic problem ... I mean just submitting some lines of code, so no, I don't think I'll be able to find the roots $\endgroup$ – Blencer Dec 31 '16 at 3:17
  • $\begingroup$ wouldn't it be simpler to first get the degree $4$ polynomial of which $a+b+c$ is a root ? $\endgroup$ – mercio Jan 1 '17 at 0:20
  • $\begingroup$ Yes, I did that as well -- didn't post it. Apparently it's a live programming contest problem. I wasn't aware of that when I posted my repsonses. $\endgroup$ – quasi Jan 1 '17 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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