I am working on Project Euler 390.

The question is about triangles, and finding the area of a triangle with sides $\sqrt{a^2+1}, \sqrt{b^2+1}$ and $\sqrt{a^2+b^2}$, with $a, b \in \mathbb{Z}$. I have narrowed the problem down to solving the equation

$$x^2 \cdot y^2 + x^2 + y^2 = (2\cdot c)^2 \text{ with } x, y, c \in \mathbb{Z}^+$$

This is not a problem for $c \le 10^6$ (brute force), but I have to calculate up to $10^{10}$. I would like to know how to solve these kind of equations, without any brute force attack. I have searched for a few days on Google, but the general solutions to the Diophantine equations I found were never appliable to my problem.

Any suggestions are welcome (even the name of this kind of equation), although I would appreciate not being told the answer to the problem.

  • $\begingroup$ Oops, you're right. I'll delete my comment. $\endgroup$ – celtschk Aug 15 '12 at 12:11
  • $\begingroup$ We do have $(2c)^2+1=(x^2+1)(y^2+1)$ which indicates that both factors on the RHS are odd, and x,y are therefore even. $\endgroup$ – Mark Bennet Aug 15 '12 at 12:12
  • $\begingroup$ @MarkBennet Thanks for the comment, I found that out already. I still require 25 minutes of computing power to calculate all the $(x, y)$ for $c \le 10^6$. $10^{10}$ is just not possible brute force. $\endgroup$ – Hidde Aug 15 '12 at 12:19
  • $\begingroup$ It seems to me that this curve (for a fixed $c$) is closely related to Edwards' curves. May be with a twist (Daniel Bernstein and Tanja Lange have studied the twisted curves)? Anyway, they are birationally equivalent to elliptic curves meaning that parametrizing the rational points may be a tall order. $\endgroup$ – Jyrki Lahtonen Aug 15 '12 at 18:08
  • $\begingroup$ I don't know how much use it is, but another form is $(x+y)^2 + (xy - 1)^2 = 4c^2 + 1$. $\endgroup$ – SiliconCelery Aug 15 '12 at 18:17

It seems like the problem is that you simply can't afford to compute all the solutions for all valid values of $c$. As Mark's comment notes, your equation is equivalent to saying that $(2c)^2+1 = (x^2+1)(y^2+1)$, and trying to factor each $4c^2+1$ for all $c$ in your range is just infeasible. So, why not go the other way? Rather than trying to solve your equation for each $c$, instead iterate over all even $x$ from $1\leq x\leq \approx 2\cdot 10^{10}$ (and it's not hard to find your specific upper bound), and compute your maximum value of $y$ as $\displaystyle{y_{\mathrm{max}} = \sqrt{\frac{4\cdot 10^{20}+1}{x^2+1}-1}}$; then for every even $y\leq y_{\mathrm{max}}$ you can compute $(x^2+1)(y^2+1)-1$ and test whether it's a perfect square (this test should be pretty quick); this will involve doing roughly $\displaystyle{\sum_{i=0}^{10^{10}}\left\lfloor\frac{10^{10}}{i}\right\rfloor}\approx 10^{10}\ln(10^{10})\approx 23\cdot 10^{10}$ tests, but that should be relatively feasible. What's more, with a careful application of symmetry you can shrink your upper bound for $x$ to something more on the order of $10^5$ (since every solution $(x,y,c)$ corresponds to a solution $(y,x,c)$, you can assume $x\geq y$) and shave your total number of tests approximately in half.

  • $\begingroup$ I have read your answer, and I agree a lot. I am letting my mind go over it while I am sleeping, that always helps. The reduction of the range of $x$ is good, it should help. I hope though that something in the range of $10^{11}$ is computable. $\endgroup$ – Hidde Aug 15 '12 at 21:12
  • $\begingroup$ Another thing to consider is sieving, based on the idea that there are only a certain number of values that a square can have mod most primes. For instance, if you consider mod 5, then $1^2=4^2=1, 2^2=3^2=4$, so the possible values for $x^2+1$ are $0,1,2$; in particular, $x$ and $y$ can't both be $\equiv \pm 1\pmod 5$, since then $x^2+1\equiv 2$, $y^2+1\equiv 2$, and $(2c)^2= (x^2+1)(y^2+1)-1$ would have to be $\equiv 3\pmod 5$; this lets you eliminate roughly 15% of all possibilities, and using other primes should let you shave off quite a bit more. $\endgroup$ – Steven Stadnicki Aug 15 '12 at 21:53

Let $y=x+a=>x^2\cdot y^2+x^2+y^2=x^2(x+a)^2+x^2+(x+a)^2=x^4+x^3(2a)+x^2(a^2+2)+x(2a)+a^2$

Let this be equal to $(x^2+px+q)^2$ where p,q are integers, so that $c=x^2+px+q$.

So, $x^4+x^3(2a)+x^2(a^2+2)+x(2a)+a^2=x^4+x^3(2p)+x^2(2q+p^2)+x(2pq)+q^2$

Expanding the RHS and comparing the coefficients of different powers of x,

coefficients of cubic power $=>p=a$

coefficients of square $=>a^2+2=2q+p^2=>q=1$ as $p=a$

coefficients of first degree $=>2pq=2a=>q=1$

constants $=>q^2=a^2=>a=±q=±1=>p=a=±1$

So, $y=x±1$.

The RHS($x^2+px+q$) reduces to $x^2±x+1$ but unfortunately this must be odd as x is even, so can not be equals to 2c.

So, there can be no solution following this approach.

Now, if we arrange $x^4+x^3(2a)+x^2(a^2+2)+x(2a)+a^2=(2c)^2$ as a quadratic equation of a, $a^2(x^2+1)+2a(x^3+x)+x^4+2x^2-4c^2=0$--->(1).

As a=x-y is integer, so the discriminant($D^2$) of (1) must be perfect square.


So, D is even=(2E, say)



As x is integer, the discriminant($D_1^2$) of (2) must be perfect square.

So, $D_1^2=(4c^2-1)^2-4.1.(E^2-4c^2)$

$=>D_1^2+(2E)^2=(4c^2+1)^2$, clearly $D_1$ is odd.

Now $4c^2+1$ can always be expressed as the sum of two squares(not necessarily in a unique way)=($r^2+s^2$, say), where r,s are integers.

If we take $E=rs =>D_1=r^2-s^2$

So,$x^2=\frac{4c^2-1 ± D_1}{2}=\frac{r^2+s^2-2±(r^2-s^2)}{2}=r^2-1\ or s^2-1$

Now, either I have made some mistake or I doubt the existence of a non-trivial solution.

  • $\begingroup$ You're looking for parameterized solutions - while the only way that the quartics can be the same as a polynomial in $x$ is for individual terms to be the same, they can coincidentally be the same at a particular x in any number of ways. (e.g., $3x^2-2x+5$ and $2x^2-x+11$ are not the same polynomial, but they both happen to evaluate to $26$ at $x=3$.) $\endgroup$ – Steven Stadnicki Aug 15 '12 at 17:22
  • $\begingroup$ I do agree with you for the 1st approach, but this method sometimes leads to solution. Acceptably, this method does not ensure the non-existence of the solution. What about the 2nd approach. $\endgroup$ – lab bhattacharjee Aug 15 '12 at 17:37
  • $\begingroup$ To be honest, I didn't look at the second approach closely enough, although I feel like it may suffer from the same problem. More to the point, there's a known non-trivial solution (the one that corresponds to the solution in the original problem statement), so I doubt any mathematics that doubts the existence of a solution that's already known to exist. :-) $\endgroup$ – Steven Stadnicki Aug 15 '12 at 18:00
  • $\begingroup$ I really don't understand what you are trying to do in your solutions. Maybe I am not mathematically educated enough. If it is really a solution to my problem, it would be nice if you could explain a little what you are doing. $\endgroup$ – Hidde Aug 15 '12 at 19:40

To me this is a general equation with many solutions... $$ \begin{align} x^2 \cdot y^2 + x^2 + y^2 &= c^2 \\ x^2 \cdot y^2 + x^2 + y^2 +1 &= c^2 +1 \\ (x^2+1)(y^2+1)&=(c^2+1) \\ \text{substitute to } XY&=C \end{align} $$

So why couldn't we just call this equation $XY=C$, with the only limitation that $C = 1 \pmod 4$ (since really from the problem statement $c\to 2c$)?

So $x,y$ are even ....

I don't know group theory, but all numbers of the form $(2c)^2+1$ may be mutually prime, so there may not be solutions. If I'm mistaken so be it, but forgive me for feeling inspired to add my thoughts.

I'm not sure if you take the set of all numbers of that form, that you can find two that are divisible...

by the way if if $c$ is not even you can have tonnes of solutions (ex $(x,y,c)=(1,2,3)$)


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.